二叉平衡排序树Word文档下载推荐.docx

1、 node* right; int balance; /左右子树高度之差 int key;2、主要函数说明int searchNode（int key, node* root, node* parent） ：按key查找结点node* minNode（node* root） ：树root的最小结点node* maxNode（node* root） ：树root的最大结点node* preNode（node* target） ：求前驱结点node* nextNode（node* target） ：求后继结点node* adjustAVL（node* root, node* parent, nod

2、e* child） ：调整，保证二叉树的平衡性node* insertNode（int key, node* root） ：插入node* deleteNode（int key, node* root） ： 删除node* createAVL（int *data, int size） ：建造新的二叉树void interordertraverse（node* root） ：中序遍历void preordertraverse（node* root） ：先序遍历3、二叉排序树的插入和删除 a. 二叉排序树的插入在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。插入过程：若二叉排

3、序树已存在，则返回根节点；当节点不存在时，将待插结点关键字key和树根关键字parent-key进行比较，若keykey，则插入到根的左子树中，否则，则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。并且注意二叉树的平衡性，时刻调整。 b. 二叉排序树的删除假设在二叉排序树上被删结点为*tp，其双亲结点为*parent，且不失一般性，可设* *parent是* parent-left;的左孩子。 下面分3种情况进行讨论：（1）若*parent结点为叶子结点，即PL和PR均为空树。由

4、于删去叶子结点不破坏整棵树的结构，则只需要修改其双亲结点的指针即可。（2）若*parent结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。（3）若*parent结点的左子树和右子树均不空。4、中序遍历和先序遍历void interordertraverse（node* root） /中序遍历 if （root != NULL） interordertraverse（root-left）; printf（%d, %dn, root-key, root-balance）;right）; void preorder

5、traverse（node* root） /先序遍历 preordertraverse（root-5、调整二叉树的平衡性node* adjustAVL（node* root, node* parent, node* child）主要有四种调整类型根据平衡因子主要有LR、LL、RL、RR（1）、根据parent-balance的值为2时，child-balance = -1 时是LR型，否则为LL型；if （child-balance = -1） /LR型 cur = child-right; cur-parent = parent-parent; child-right = cur- if （

6、cur-left !left-parent = child; parent-left = cur-right !right-parent = parent;left = child;parent = cur;right = parent; if （parent-parent !left = parent）left = cur; else parent-right = cur; else root = cur;balance = 0）balance = 0; else if （cur-balance = -1） balance = 1; balance = -1; else /LL型left =

7、 child- if （child-right = child; root = child;balance = 1） /插入时 else /删除时 break;（2）、parent-balance的值为-2时，child-balance = 1时是RL型，否则为RRbalance = 1） /RL型left = parent;balance = 1） else /RR型right = child-balance = -1） /插入时6、主函数void main（）给出了一组数据1, 13, 7, 4，对数据中序遍历和先序遍历，然后是插入、删除、查询、退出操作。三、系统实现运行环境Windows

8、 7 操作系统，Microsoft Visual C+ 6.0。四、程序#include string.hstdlib.herrno.hassert.h / assert用于调试声明宏，用于定位程序开发中的逻辑 /错误当参数expression为false时程序执行被中断 node* parent; /平衡因子（左右子树高度之差）extern void interordertraverse（node* root）; /中序遍历extern void preordertraverse（node* root）; /前序遍历int searchNode（int key, node* root, no

9、de* parent） /按key查找结点 node* temp; assert（root != NULL）; temp = root; *parent = root- while （temp !=NULL） if （temp-key = key） return 1; else *parent = temp;key key） temp = temp- return 0;node* minNode（node* root） /树root的最小结点 if （root = NULL） return NULL; while （root- root = root- return root;node* ma

10、xNode（node* root） /树root的最大结点node* preNode（node* target） /求前驱结点 if （target = NULL） if （target- return maxNode（target- while （target-parent!=NULL） & （target!=target-right） target = target- return target-node* nextNode（node* target） /求后继结点 return minNode（target-left）node* adjustAVL（node* root, node* p

11、arent, node* child）/调整旋转操作/保持二叉排序树的平衡性 node *cur; assert（parent != NULL）&（child != NULL）; switch （parent-balance） case 2:/平衡因子由1增至2balance = -1） /LR型双向旋转（先左后右）平衡处理 cur- if （parent- parent- else parent- root = cur; child- else /LL型单向右旋平衡处理 root = child; case -2:/平衡因子由-1变为-2 if （child-balance = 1） /RL

12、型双向旋转（先右后左）平衡处理 cur = child- if （cur- cur- if （parent- else parent- else root = cur; parent- child- else if （cur- else /RR型单向左旋平衡处理 parent- root = child; else /删除时 break;node* insertNode（int key, node* root）/插入 node *parent, *cur, *child; assert （root ! if （searchNode（key, root, &parent） /结点已存在 return root; else/节点不存在 cur = （node*）malloc（sizeof（node）;key = key;left = NULL;right = NULL; if （key while （parent != NULL） /查找需要调整的最小子树 if （child = parent-left） return root; else if （parent-balance = 2; break; else