《实习六：平衡二叉树.docx》由会员分享，可在线阅读，更多相关《实习六：平衡二叉树.docx（21页珍藏版）》请在三一文库上搜索。
1、实习六：平衡二叉树实验报告题目：平衡二叉树操作的演示一.需求分析利用平衡二叉树实现一个动态查找表。实现动态查找表的三种基本功 能：查找、插入和删除。测试数据：13,24,37,90,53二.详细设计#include #include #include #include #include #define SUCCESS 0#define ERROR -1#define max(a,b) (a)(b)?(a):(b)#define NOT_FOUND 1using namespace std;typedef int Status;typedef struct _AVLint data, count
2、;inth;struct _AVL *lch, *rch;Status Init(int d)data = d;h = count = 1;Ich = rch = NULL; return SUCCESS;) AVL, *PAVL;int GetHeight(PAVL p)if (p = NULL)return 0;return p-h;void UpdateHeight(PAVL &p)p-h = max(GetHeight(p-Ich), GetHeight(p-rch) + 1;void L_Rotate(PAVL &p)if (p-rch != NULL)PAVL tmp = p-rc
3、h;p-rch = tmp-lch;tmp-lch = p;p = tmp;UpdateHeight(p-lch);UpdateHeight( p);)void R_Rotate(PAVL &p)if (p-lch != NULL)PAVL tmp = p-lch;p-lch = tmp-rch;tmp-rch = p;p = tmp;UpdateHeight(p-rch);UpdateHeight(p);void RightBalance(PAVL &p)if (p != NULL)if (GetHeight(p-rch) - GetHeight(p-lch) 1)/ 左旋(if (GetH
4、eight(p-rch-lch) GetHeight(p-rch-rch) /双旋R_Rotate(p-rch);L_Rotate(p);void LeftBalance(PAVL &p)if(p != NULL)if (GetHeight(p-lch) - GetHeight(p-rch) 1) / 右旋if (GetHeight(p-Ich-rch) GetHeight(p-lch-lch) / 双L_Rotate(p-Ich);R_Rotate(p);Status AVLInsert(PAVL &p, int elem)(if(p = NULL)p = new AVL;if(!p)ret
5、urn ERROR;p-Init(elem);return SUCCESS;)elseif (elem p-data)if (AVLInsert(p-rch, elem) = ERROR) return ERROR;RightBalance(p);)else if (elem data)if (AVLInsert(p-lch, elem) = ERROR) return ERROR;LeftBalance(p);)elsep-count+;)UpdateHeight(p);return SUCCESS;)PAVL FindSuccession(PAVL &p)PAVL r = p;if (p-
6、lch != NULL)r = FindSuccession(p-lch);UpdateHeight(p);RightBalance(p);)elsep = p-rch;return r;)Status AVLDelete(PAVL &p, int elem)Status status = SUCCESS;if (NULL = p)return NOT FOUND;if (elem p-data)status = AVLDelete(p-rch, elem);if (status = SUCCESS)UpdateHeight(p);LeftBalance(p);else if (elem da
7、ta)status = AVLDelete(p-lch, elem);if (status = SUCCESS)UpdateHeight(p);RightBalance(p);)else /找到待删除元素if (p-lch != NULL & p-rch != NULL)(PAVL succ = FindSuccession(p-rch); / 寻找后继结点PAVL tmp = p;succ-lch = p-lch;succ-rch = p-rch;P = succ; /移动后继结点到当前结点UpdateHeight(p);delete tmp;elseif (p-lch != NULL) p
8、 = p-lch;elsep = p-rch;)LeftBalance(p);)return status;Status AVLFind(PAVL T, int elem, int &depth) (depth = 1;while (T != NULL)if (elem T-data)T = T-rch;else if (elem data)T = T-lch;elsereturn SUCCESS;depth+;return NOT FOUND;zint Msg()int r;cout “*“ w endl;coutcout1 .插入元素2 .删除元素vv endl;vv endl;cout3
9、.查找元素 endl;cout0.退出程序 endl;cout “*“ endl;coutvv”请选择：”；cin r;return r;)void print_proc(PAVL T, int &now, int depth, int m100)if (NULL = T)return;print_proc(T-rch, now, depth + 1, m);mnow+ depth = T-data;print_proc(T-lch now, depth + 1, m);)void print_avl(PAVL T)int m100100, num = 0;memset(m, OxFF, si
10、zeof(m);print_proc(T, num, 0, m);for (int i = 0; i+)int lev num = 0;for (int j = 0; j num; j+)if (miU != -1)lev num+;printf(,%3d,mij);elseprintf(ft ft);printf(f,nft);if (lev_num = 0)break;void cmd_insert(PAVL &T)intd;coutvv”输入待插入的元素值：”；cin d;if (AVLInsert(T, d) = ERROR)cout ”插入元素失败!” vv endl;elsecou
11、t ”插入元素成功!” VV endl;print_avl(T);void cmd_delete(PAVL &T)int d, status;COUt 输入待删除的元素值：Tcin d;status = AVLDelete(T, d);switch (status)case SUCCESS:cout ”删除元素成功!” endl;print_avl(T);break;case NOT_FOUND:cout ”没有找到输入的元素” endl;break;case ERROR:cout ”删除元素失败!” endl;break;void cmd_find(PAVL &T)int d, status
12、, depth;COUt 输入待查找的元素值：T cin d;status = AVLFind(T, d, depth);switch (status)case SUCCESS:cout ”在深度 vv depth ”找到该元素！ ” endl;break;case NOT_FOUND:cout ”没有找到输入的元素” endl;break;case ERROR:cout ”查找元素失败!” vv endl;break;int main()int cmd;PAVL avl = NULL;while (cmd = Msg()switch (cmd)(case 1:cmd_insert(avl);
13、break;case 2:cmd_delete(avl);break;case 3:cmd_find(avl);break;default:cout 指令错误!” endl;break;)return 0;测试结果1.2.元素3十坛到素9.退出程序请选报1蒯八特里:用元素值：13插入元素成功？131.2.匹索 7LJ 3 _.v, 0-退出程序X-X-X-X-X-*-X-X-X-X-X-*-X-X-X-X-X-*X-X-X-X-X-*-?C?C)C)C*搐辘媪wx-x-*-x-x-x-x-x-*x-x-x-x-x-*x-x-x-x-x-*-x-x-x-x-*1.3 _7LB0.退出程序值素元？ 的功 1人成 :插索 篝兀24 选入入 请g*1.*2.* 3.* 0-退出程序请选择：1 揄A在产入一专力: 素 元？1人成 :插素 霄元3? 选入入素素素序元元兀程入鬟出12 3 0: 素 元？1人成0.插素 霄元 选入入素素素序元元兀程入鬟出12 3 0: 素 元？1人成0.插素 霄元 选入入3