《数据结构》课程设计--二叉排序树调整为平衡二叉树.doc

计算机与信息工程系 数据结构课程设计报告学号2013-2014学年 第一学期1208020228数据结构课程设计报告题目：二叉排序树调整为平衡二叉树专业：网络工程班级：二姓名：汪杰指导教师：刘义红成绩：计算机与信息工程系2013年 1 月 2日目录1、 问题描述2、 设计思路(数学模型的选择) 3、 二叉排序树和平衡二叉树定义4、 程序清单5.程序功能说明5.运行与调试分析 6.总结1. 问题描述输入带排序序列生成二叉排序树，并调整使其变为平衡二叉树，运行并进行调试。2. 设计思路平衡二叉树的调整方法平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下： 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点； 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点； 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整； 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；3. 二叉排序树和平衡二叉树定义二叉排序树二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2） 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3） （3）左、右子树也分别为二叉排序树；平衡二叉树平衡二叉树（Balanced Binary Tree 或Height-Balanced Tree）又称AVL树，它或者是一棵空树，或者是具有以下性质的二叉；它的左子树右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，平衡二叉树上的任何节点的左子树和右子树的深度的差值只能是1、0或1。4. 程序功能说明void preorder(bintree t)/*前序遍历*/void midorder(bintree t)/*中序遍历*/lastorder(bintree t)/*后序遍历bintree a;int j,k;clrscr();textcolor(2);printf(*欢迎您使用本二叉树操作系统*n);printf(建造一棵二叉树请您输入各个结点的元素值,()表示一个空格键:n);printf(输入示例:abc()()de()g()()f()()()回车:n);a=createbitree();printf(您输入的二叉数嵌套法表示如下:n);printree(a);printf(n);printf(树的深度为:n);j=treedepth(a);printf(%dn,j);printf(二叉数的叶子接点个数为:n);k=treeleaf(a);printf(%dn,k);printf(您所输入的二叉树的前序遍历顺序输出如下:n);if(!a) printf(二叉树为空n);elsepreorder(a);printf(n);printf(您所输入的二叉树的中序遍历顺序如下输出:n);if(!a) printf(二叉树为空n);elsemidorder(a);printf(n);printf(您所输入的二叉树的后序遍历顺序输出如下:n);if(!a) printf(二叉树为空n);elselastorder(a);printf(n);printf(您所输入的二叉树的层次顺序遍历输出如下:n); if(!a) printf(二叉树为空n);else translevel(a);5.程序清单#include stdio.h#include conio.h#include stdlib.h#define NULL 0int leftdep,rightdep;typedef struct bitnodechar data;struct bitnode *lchild,*rchild;bintnode,*bintree;bintree createbitree()bintree t;char x;scanf(%c,&x);if(x= ) t=NULL;elset=(bintnode *)malloc(sizeof(bintnode); t-data=x; t-lchild=createbitree(); t-rchild=createbitree();return(t);void preorder(bintree t)/*前序遍历*/if(t)printf(%2c,t-data);preorder(t-lchild);preorder(t-rchild);void midorder(bintree t)/*中序遍历*/if(t)midorder(t-lchild); printf(%2c,t-data); midorder(t-rchild);void printree(bintree t)if(t!=NULL)printf(%c,t-data); if(t-lchild!=NULL|t-rchild!=NULL) printf();printree(t-lchild); if(t-rchild!=NULL) printf(,); printree(t-rchild); printf();int treedepth(bintree t) if(t=NULL) return 0; elseleftdep=treedepth(t-lchild); rightdep=treedepth(t-rchild); if(leftdeprightdep)return (leftdep+1);elsereturn(rightdep+1);int treeleaf(bintree t)if(t=NULL)return0;else if(t-lchild=NULL&t-rchild=NULL) return1;else return(treeleaf(t-lchild)+treeleaf(t-rchild);void lastorder(bintree t)/*后序遍历*/if(t)lastorder(t-lchild);lastorder(t-rchild);printf(%2c,t-data);void translevel(bintree t)struct bitnodebintree vec30; int f,r;q;q.f=0;q.r=0;if(t!=NULL) printf(%2c,t-data); q.vecq.r=t;q.r=q.r+1; while (q.flchild!=NULL) printf(%2c,t-lchild-data); q.vecq.r=t-lchild; q.r=q.r+1;if(t-rchild!=NULL) printf(%2c,t-rchild-data); q.vecq.r=t-rchild; q.r=q.r+1; printf(n);main()bintree a;int j,k;clrscr();textcolor(2);printf(*欢迎您使用本二叉树操作系统*n);printf(建造一棵二叉树请您输入各个结点的元素值,()表示一个空格键:n);printf(输入示例:abc()()de()g()()f()()()回车:n);a=createbitree();printf(您输入的二叉数嵌套法表示如下:n);printree(a);printf(n);printf(树的深度为:n);j=treedepth(a);printf(%dn,j);printf(二叉数的叶子接点个数为:n);k=treeleaf(a);printf(%dn,k);printf(您所输入的二叉树的前序遍历顺序输出如下:n);if(!a) printf(二叉树为空n);elsepreorder(a);printf(n);printf(您所输入的二叉树的中序遍历顺序如下输出:n);if(!a) printf(二叉树为空n);elsemidorder(a);printf(n);printf(您所输入的二叉树的后序遍历顺序输出如下:n);if(!a) printf(二叉树为空n);elselastorder(a);printf(n);printf(您所输入的二叉树的层次顺序遍历输出如下:n); if(!a) printf(二叉树为空n);else translevel(a);5. 运行与调试分析输入几个数据进行运行调试，观察运行结果是否达到预期的目的，运行中可能出现逻辑错误，输入数据合适与否以及相关细节都可能会影响程序的运行，可以试着