C#实现二叉排序树定义、插入、构造

本文讲解C#实现二叉排序树定义、插入、构造 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。 步骤：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，递归查左子树。 若大于根结点的关键字值，递归查右子树。 若子树为空，查找不成功。 平均情况分析（在成功查找两种的情况下）： 在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6 注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数 （二叉树图中应为左子树P(3)，右子树P(2)） P(3) = （1+2+2）/ 3 = 5/3 P(2) = （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n ∴ P（n）= P（n,i）/ n key) { return BST_Insert(ref T.lchild,key); } else { return BST_Insert(ref T.rchild, key); } } /// /// 二叉排序树的构造 /// /// /// /// static void Creat_BST(ref BSTNode T,int[] str,int n) { T = null; int i = 0; bool ggg; while (i