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

本科生数据结构实验报告封面（2012至2012学年度第二学期）题 目 C#实现二叉排序与平衡二叉树 科 目 数据结构 姓 名 李艳玫 学 号 201175040112 班 级 11级地理信息系统 实 验 成 绩：授课教师签字： C#实现二叉排序与平衡二叉树1.根据所给一组数如何构造一棵二叉树。 一棵二叉排序树满足二叉树的性质：1若他的左子树非空，则它的左子树上记录的所有结点的值都小于根记录的值。2若他的右子树非空，则它的右子树上记录的所有结点的值都大于根记录的值。3左 右子树本身又是一颗二叉树。 根据给定的一组数如： 50, 30, 20, 10, 60, 70 构造二叉树的算法：首先取到50作为根节点，然后在取到30，用30和50比较，发现30小于50，则30为50的左孩子，再取20,20又小于30，固又为30 的左孩子，取10，做20的左孩子，60做50的右孩子，70做60的右孩子。这样一棵二叉树就构造完了。如下： 50 30 60 20 70 10 下面我们就实现该算法：首先我们有一个数，我们先看是否根节点为NULL：如果为空，则该节点即为根节点，并使他的左右孩子均为NULL，既有：public BsTrav Insert (int X,BsTrav T) /函数if(T=null) T.Element=X; T.Left=T-Right= null; 如果头结点不为空，则和头结点进行比较，如大则为右孩子，否则为左孩子。 if(XT.Element) T.Right = Insert(X,T.Right);最后在返回T即可。 2. 平衡二叉树平衡二叉树的特点:1他的左子树和右子树都是平衡二叉树。2左子树和右子树的高度差不超过2.我们先来解决第一个问题：如何求一棵二叉树的高度。我们定义：当前结点的高度、是取左右孩子高度最大值再加1，所以对一下的结点，有：我们在来计算高度差： 30(1) (1) 12 57 (1) (0) 3 (1) 23 (1) 96 (0) 18 (1) 75 (0) 83下面我们设计来计算高度差:就是在比较大小的过程。 private int Max(int a, int b) if (a LL调整。对于图一插入5有： 50 K1 K2 30 60 20 70 10 5 有他们的高度差为2，在这种条件下，我们需要进行调整。我们发现失去平衡的点是 50 在这是就要调整k1,k2的位置。LL调整：找到不平衡的点，这里是K1,然后找到k1的左孩子K2，然后将k2的右孩子给给K1的左孩子，其他节点按照原先的连接方式连接。调整后为： 30 K2 20 50 k1 10 60 5 这 70具体的就是： K1 = K2.Left; 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有： 50 K1 30 60 K2 70 75 RR调整和LL调整雷同，就是将左节点换成右节点，在进行调整。具体的就是：调整后为： 60 K2 50 K1 70 30 753. LR调整： 60 K1 50 70 30 52 51需要进行LR调整。我们先断开失去平衡的点左子树。进行RR调整。 50 52 30 52 -RR- 50 51 30 51则有： 60 K1 52 K2 52 K2 70 -LL- 50 60 k2 50 30 51 70 30 51 LR调整就是先进行RR调整在进行LL调整。即： private AVlNode LR(AVlNode K3) K3.Left = RR(K3.Left); return LL(K3); 4. RL调整：他的过程同LR调整。在这掌握了就不在讲了。 private AVlNode RL(AVlNode K1) K1.Right = LL(K1.Right); return RR(K1); 我们会算高度也会调整后，我们就将整体穿在一起。 我们将所有程序在刚开始的Insert函数中。当我们插入一个数时，我们在判断这个数与源节点的大小时，就要加入判断是否平衡，不平衡是就要进行调整，在要进行什么调整。这样就可以了。如下是具体程序; public AVlNode Insert(int X, AVlNode T) if (T = null | T.Element = -1) T = new AVlNode(); T.Element = X; if (X T.Element) T.Left = Insert(X, T.Left); if (HEIGHT (T.Left) - HEIGHT(T.Right) = 2) /判断是否要进行调整 if (X T.Element) T.Right = In