二叉树排序树建立及平衡处理

１本程序在vc++6.0编译通过并能正常运行。 ２主界面 程序已经尽量做到操作简便了，用户只需要根据提示一步步进行操作就行了。 六思考和总结： 这个课程设计的各个基本操作大部分都在我的综合性实验中实现了，所以做这个主要攻克插入和删除这两个算法！其中插入在书本上已经有了，其中的右平衡算法虽然没有给出，但通过给出的左平衡算法很容易就可以写出右平衡算法。所以最终的点就在于删除算法的实现！做的过程中对插入算法进行了非常非常多次的尝试！花了非常多的时间，这其中很多时候是在对程序进行单步调试，运用了ＶＣ６。０的众多良好工具，也学到了很多它的许多好的调试手段。 其中删除算法中最难想到的一点是：在用叶子结点代替要删除的非叶子结点后，应该递归的运用删除算法去删除叶子结点！这就是整个算法的核心，其中很强烈得体会到的递归的强大，递归的最高境界（我暂时能看到的境界）！ 其它的都没什么了。选做的那两个算法很容易实现的： １合并两棵平衡二叉排序树：只需遍历其中的一棵，将它的每一个元素插入到另一棵即可。 ２拆分两棵平衡二叉排序树：只需以根结点为中心，左子树独立为一棵，右子树独立为一棵，最后将根插入到左子树或右子树即可。 BSTreeEmpty(BSTree T) 初始条件：平衡二叉排序树存在。 操作结果：若T为空平衡二叉排序树，则返回TRUE,否则FALSE. BSTreeDepth(BSTree T) 初始条件：平衡二叉排序树存在。 操作结果：返回T的深度。 LeafNum(BSTree T) 求叶子结点数，非递归中序遍历 NodeNum(BSTree T) 求结点数，非递归中序遍历 DestoryBSTree(BSTree *T) 后序遍历销毁平衡二叉排序树T R_Rotate(BSTree *p) 对以*p为根的平衡二叉排序树作右旋处理，处理之后p指向新的树根结点 即旋转处理之前的左子树的根结点 L_Rotate(BSTree *p) 对以*p为根的平衡二叉排序树作左旋处理，处理之后p指向新的树根结点， 即旋转处理之前的右子树的根结点 LeftBalance(BSTree *T) 对以指针Ｔ所指结点为根的平衡二叉排序树作左平衡旋转处理， 本算法结束时，指针Ｔ指向新的根结点 RightBalance(BSTree *T) 对以指针Ｔ所指结点为根的平衡二叉排序树作右平衡旋转处理， 本算法结束时，指针Ｔ指向新的根结点 Insert_AVL(BSTree *T, TElemType e, int *taller) 若在平衡的二叉排序树Ｔ中不存在和e有相同的关键字的结点， 则插入一个数据元素为e的新结点，并返回OK,否则返回ERROR. 若因插入而使二叉排序树失去平衡，则作平衡旋转处理 布尔变量taller反映Ｔ长高与否 InOrderTraverse(BSTree T) 递归中序遍历输出平衡二叉排序树 SearchBST(BSTree T, TElemType e, BSTree *f, BSTree *p) 在根指针Ｔ所指的平衡二叉排序树中递归的查找其元素值等于e的数据元素， 若查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p 指向查找路径上访问的最后一个结点并返回FALSE，指针f指向Ｔ的双亲， 其初始调用值为NULL Delete_AVL(BSTree *T, TElemType e, int *shorter) 在平衡二叉排序树中删除元素值为e的结点,成功返回OK,失败返回ERROR PrintBSTree_GList(BSTree T) 以广义表形式打印出来 PrintBSTree_AoList(BSTree T, int length) 以凹入表形式打印,length初始值为0 Combine_Two_AVL(BSTree *T1, BSTree T2) 合并两棵平衡二叉排序树 Split_AVL(BSTree T, BSTree *T1, BSTree *T2) 拆分两棵平衡二叉树 } (2)存储结构的定义： typedef struct BSTNode { TElemType data; int bf; //结点的平衡因子 struct BSTNode *lchild, *rchild;//左.右孩子指针 }BSTNode, *BSTree;