C#实现二叉排序与平衡二叉树.doc

《C#实现二叉排序与平衡二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本科生数据结构实验报告封面（2012至2012学年度第二学期）题目C#实现二叉排序与平衡二叉树科目数据结构姓名李艳玫学号2班级11级地理信息系统实验成绩：授课教师签字：C#实现二叉排序与平衡二叉树1.根据所给一组数如何构造一棵二叉树。一棵二叉排序树满足二叉树的性质：1>若他的左子树非空，则它的左子树上记录的所有结点的值都小于根记录的值。2>若他的右子树非空，则它的右子树上记录的所有结点的值都大于根记录的值。3>左右子树本身又是一颗二叉树。根据给定的一组数如：{50,30,20,10,60,70}构造二叉树的算法：首先取到50作为根节点，然后在取到30，

2、用30和50比较，发现30小于50，则30为50的左孩子，再取20,20又小于30，固又为30的左孩子，取10，做20的左孩子，60做50的右孩子，70做60的右孩子。这样一棵二叉树就构造完了。如下：503060207010下面我们就实现该算法：首先我们有一个数，我们先看是否根节点为NULL：如果为空，则该节点即为根节点，并使他的左右孩子均为NULL，既有：publicBsTravInsert(intX,BsTravT)//函数if(T==null){T.Element=X;T.Left=T->Right=null;}如果头结点不为空，则和头结点进行比

3、较，如大则为右孩子，否则为左孩子。if(XT.Element)T.Right=Insert(X,T.Right);最后在返回T即可。2.平衡二叉树平衡二叉树的特点:1>他的左子树和右子树都是平衡二叉树。2>左子树和右子树的高度差不超过2.我们先来解决第一个问题：如何求一棵二叉树的高度。我们定义：当前结点的高度、是取左右孩子高度最大值再加1，所以对一下的结点，有：我们在来计算高度差：30(1)(1)1257(1)(0)3(1)23(1)96(0)18(1)75(0)83下面我们

4、设计来计算高度差:就是在比较大小的过程。privateintMax(inta,intb){if(aLL调整。对于图一插入5有：50K1K230602070105有他们的高度差为2，在这种条件下，我们需要进行调整。我们发现失去平衡的点是50在这是就要调整k1,k2的位置。LL调整：找到不平衡的点，这里是K1,然后找到k1的左孩子K2，然后将k2的右孩子给给K1的左孩子，其他节点按照原先的连接方式连接。调整后为：30K22050k110605这70具体的就是：K1=K2.Lef

5、t;K2.Left=K1.Right;K1.Right=K2;在这我们还需要比较一下k1和k2的高度差，即：K2.Height=Max(HEIGHT(K2.Left),HEIGHT(K2.Right))+1；K1.Height=Max(HEIGHT(K1.Left),K2.Height)+1;RR调整：对于图一插入75有：50K13060K27075RR调整和LL调整雷同，就是将左节点换成右节点，在进行调整。具体的就是：调整后为：60K250K17030752.LR调整：60K15070305251需要进行LR调整。我们先断开失去平衡的点左子树。进行R

6、R调整。50523052-----RR------->50513051则有：60K152K252K270------LL--->5060k2503051703051LR调整就是先进行RR调整在进行LL调整。即：privateAVlNodeLR(AVlNodeK3){K3.Left=RR(K3.Left);returnLL(K3);}2.RL调整：他的过程同LR调整。在这掌握了就不在讲了。privateAVlNodeRL(AVlNodeK1){K1.Right=LL(K1.Right);returnRR(K1);}我们会算高度也会调整后，我们就将整体穿在

7、一起。我们将所有程序在刚开始的Insert函数中。当我们插入一个数时，我们在判断这个数与源节点的大小时，就要加入判断是否平衡，不平衡是就要进行调整，在要进行什么调整。这样就可以了。如下是具体程序;publicAVlNodeInsert(intX,AVlNodeT){if(T==null

8、

9、T.Element==-1){T=newAVlNode();T.Element=X;}if(X

10、(X