二叉树操作

二叉树操作二叉树操作 Visual C++课程设计报告二叉树操作材料科学与工程专业姓名:xxx 学号:xxxxxxxx 一( 程序功能简介带枚举值的二叉树的实现，利用枚举值使二叉树的组成尽量平衡，即左右子树的级数相差不多。可以完成二叉树结点数据的插入、删除、查找和输出功能。二( 程序设计说明 1( 用类的形式来编写程序。虽然这个程序中只定义了一个类，但这个类就是贯穿整个程序的灵魂。该类的结构如下: class RBtree //二叉树类 , privare: class RBnode...

二叉树操作 Visual C++课程设计报告二叉树操作材料科学与工程专业姓名:xxx 学号:xxxxxxxx 一( 程序功能简介带枚举值的二叉树的实现，利用枚举值使二叉树的组成尽量平衡，即左右子树的级数相差不多。可以完成二叉树结点数据的插入、删除、查找和输出功能。二( 程序设计说明 1( 用类的形式来编写程序。虽然这个程序中只定义了一个类，但这个类就是贯穿整个程序的灵魂。该类的结构如下: class RBtree //二叉树类 , privare: class RBnode //二叉树类 { T vaule; //数据 Color color; //枚举变量 RBnode *p; //前序指针 RBnode *left; //左支指针 RBnode *right; //右支指针 RBnode() : value(0) , color(Red) , p(NULL) , left(NULL) , right(NULL){}; //缺省构造 RBnode(const T & val) : value(val) , color(Red) , p(NULL) , left(NULL) , right(NULL) {}; //数据初始化 frieng class RBtree; //二叉树类是其友元类 public : void print( int level); //输出 }; RBnode *ROOT; //二叉树根结点指针 RBnode *NIL; //二叉树梢末结点指针值(标志) int alive; //结点个数 public: enum Color(Red,Black); //枚举类型 RBtree() : ROOT(new RBnode(val) ) , NIL(ROOT) , alive(0) //缺省构造 RBtree(const T & val) : ROOT(new RBnode, NIL(new RBnode()) , alive(1) //用数据初始化 ~ RBtree() {if(ROOT!=NIL) DeleteAll(ROOT); delete NIL;} //析构函数 void Insert (const T &); //向二叉树添加新数据 void Delete(const T &); //从二叉树中删除数据 RBnode *RBFind(const T & val); //从二叉树中查找数据 void Print(); //输出二叉树形状 void SortB(); //从小到大输出 void BortS(); // 从大到小输出 void Average(); //求平均数 } . 2.该程序的成员函数比较多，且比较难懂。以下为书上已有的源程序: (1)二次二叉树数据的插入函数 void RBtree::Insert(const T &val){ RBnode* x=new RBnode(val),*y; if(NodeInsert(x)==1) { cout<p->color==Red)) { if (x->p==x->p->p->left) // if x parent is left son { y=x->p->p->right; // checking x uncle if (y->color==Red) // if red case 1 { x->p->color=Black; y->color=Black; x->p->p->color=Red; x=x->p->p; } else { if (x==x->p->right) //if x right the case 2 { x=x->p; RotateLeft(x); } x->p->color=Black; // case 3 x->p->p->color=Red; RotateRight(x->p->p); } } else { y=x->p->p->left; // checking x uncle if (y->color==Red) // if red case 4 { x->p->color=Black; y->color=Black; x->p->p->color=Red; x=x->p->p; } else { if (x==x->p->left) //if x right the case 5 { x=x->p; RotateRight(x); } x->p->color=Black; // case 6 x->p->p->color=Red; RotateLeft(x->p->p); } } } ROOT->color=Black; return; } (2)二叉树数据的删除函数 void RBtree::Delete(const T &val) { RBnode *z,*y,*x; z=RBFind(val); if(z==NIL) { cout<left == NIL)||(z->right==NIL)) // delteing from leaves y=z; else y=RBSucc(z); if (y->left!=NIL) x=y->left; else x=y->right; x->p=y->p; if (y->p==NIL) { ROOT=x; x->p=NIL; } else { if (y==y->p->left) y->p->left=x; else y->p->right=x; } if (y!=z) // if we changed the successor with z z->value=y->value; if (y->color==Black) FixDel(x); // if we delted a Black node we have to rearrange the tree delete y; if (x==NIL) x->p=NIL; return; } (3)二叉树数据的查找 RBnode *RBFind(const T &val) // finding value in tree if found // returnes node otherwise return NIL { RBnode *tmp=ROOT; while((tmp!=NIL)&&(tmp->value!=val)) tmp=valvalue ? tmp->left : tmp->right; return tmp; } bool Find(const T &val) // the same as above but returns true if found false if not { RBnode *tmp=RBFind(val); return (tmp!=NIL); } (4)二叉树的输出 void RBtree::Print() { int depth=-1; RBnode *x=ROOT; RBPrint(x,depth); return; } // the printing will be done so that the root will be on the level // and the tree will expend to the right template void RBtree::RBPrint(RBnode *x,int level) { if (x==NIL) return; ++level; RBPrint(x->right,level); x->Print(level); cout<<"---|"<left,level); return; } 以下为需要添加的程序: 二叉树的升序遍历 void RBtree::Ascend(RBnode *strpP) { if(strpP==NIL) return ; Ascend(strpP->left); cout<value<<'_'; Ascend(strpP->right); } 二叉树上结点中的数据由小到大输出 void RBtree::SortB() { Ascend(ROOT); cout<::Descend(RBnode *strpP) { if(strpP==NIL) return ; Descend(strpP->right); cout<value<<'-'; Descend(strpP->left); } 二叉树上结点中的数据由大到小输出 void RBtree::SortS() { Descend(ROOT); cout<::Ave(T &Sum,RBnode *strpP,int &num) { if(strpP==NIL) return ; Sum+=strpP->value; num++; Ave(Sum,strpP->left,num); Ave(Sum,strpP->right,num); } 求平均值 void RBtree::Average() { T sum = 0; int num = 0; Ave(sum,ROOT,num); cout< 总结 : 这道题目中，我觉得主要是二叉树操作的不断深化，首先是构造普通的二叉树作为数据存储的集合，然后是将二叉树深化为二叉搜索树，根据节点的key值调整节点在树中的位置，得到的效果是左子树上任意节点的key值小于根节点，右子树上所有节点的key值大于根节点key值。左右子树也是一棵二叉搜索树。通过这样的设计，二叉树中的数据不再是杂乱无章，提高了查找，删除，插入的效率(或者说是提高了二叉树维护的效率)，效率主要取决与树的深度。不过，对于二叉搜索树存在退化的情形，极端情况是退化成一个有序的单链，为了进一步提高维护的效率，需要尽可能的控制树的深度，使得其尽量的小，所以增加了枚举量Red&&Black，用红黑来限定二叉树的形态，从而使得二叉树趋于平衡，而不是一端高，一端低。总结而言整个优化过程是普通二叉树-〉二叉搜索树-〉红黑树

                    本文档为【二叉树操作】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

二叉树操作

你可能还喜欢