二叉排序树的实现(最终版)

实验报告课程名称数据结构课程设计题目名称二叉树的实现学生学院应用数学学院专业班级14信安1班学号3114008224学生姓名阮志敏指导教师刘志煌2016年12月9日二叉排序树的实现一、内容和要求。1)编程实现二叉排序树，包括生成、插入、删除；2)对二叉排序树进行先根、中根和后根非递归遍历；3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4)分别用二叉排序树和数组去存储一个班（50人以上）的成员信息（至少包括学号、姓名、成绩3项），对比查找效率，并说明在什么情况下二叉排序树效率高，为什么？5)格式按照作业的要求，对数据测试，分析，总结和改进的工作要做详细一点。二、解决方案和关键代码1.二叉排序树的实现。1)首先定义二叉树的结构体，代码如下：structTreeNode;typedefstructTreeNode*TreePosition;typedefstructTreeNode*SearchTree;typedefstructTreeNode*Tree;typedefintTreeElementType;structTreeNode{//二叉树TreeElementTypeelement;//节点中的元素SearchTreeleft;//左儿子SearchTreeright;//右儿子intleght;//节点的深度，用于打印intposition;//节点的位置，用于打印};2)实现插入和生成二叉树节点的方法。在这里用到了递归插入的方法。SearchTreeinsertTreeNode(TreeElementTypex,SearchTreetree){if(tree==NULL){tree=makeTree(x,NULL,NULL);//插入在该处}elseif(xtree-element){tree-left=insertTreeNode(x,tree-left);}elseif(xtree-element){tree-right=insertTreeNode(x,tree-right);}//如果相等，什么也不做returntree;}当tree==NULL时，就是递归终止的条件，也是插入该节点的地方，在这里，用makeTree()方法创建一个节点，其代码如下：staticSearchTreemakeTree(TreeElementTypex,SearchTreeleft,SearchTreeright){SearchTreenode=(SearchTree)malloc(sizeof(structTreeNode));if(node==NULL){printf(makeTreeNodefail!\n);}else{node-element=x;node-left=left;node-right=right;}returnnode;}3)实现二叉树节点删除的方法。删除节点时有3种情况：情况一：被删除的节点同时含有左儿子和右儿子。在这种情况下，必须找出一个合适的节点来替代被删除的节点。由于二叉树的特性，被删除节点右子树中的节点都比左子树节点大，因此，可以替代原节点的节点必然在被删除节点的右子树中，并且是右子树的最小节点。所以，在这种情况下，应该把被删除节点的右子树中最小节点替代被删除节点。情况二：被删除节点只有一个子节点。显然，应该把它的子节点替代它。情况三：被删除节点没有子节点。此时，直接删除它。具体代码如下,同样使用递归删除的方法：SearchTreedeleteTreeNode(TreeElementTypex,SearchTreetree){TreePositiontmpNode;if(tree==NULL){//到叶节点了，还没找到可以删除的printf(notfound!\n);}elseif(xtree-element){tree-left=deleteTreeNode(x,tree-left);}elseif(xtree-element){tree-right=deleteTreeNode(x,tree-right);}elseif(x==tree-element){if(tree-left&&tree-right){tmpNode=findMin(tree-right);//找出右子树中最小的tree-element=tmpNode-element;//把右子树中最小的值给当前树节点//把tree右子树中最小值的节点删除了,那个要删除的节点不可能有左儿子tree-right=deleteTreeNode(tree-element,tree-right);}else{//只有一个子节点，或者没有子节点tmpNode=tree;if(tree-left==NULL){//0个子节点也包含在内tree=tree-right;}elseif(tree-right==NULL){tree=tree-left;}free(tmpNode);}}returntree;}其中的findMin()方法为找出以某个节点为根的树的最小节点，在这里可以用循环遍历tree-left来实现，也可以用递归来实现，代码如下：TreePositionfindMin(SearchTreetree){//递归实现if(tree==NULL){returnNULL;}if(tree-left!=NULL){returnfindMin(tree-left);}else{returntree;}}2.对二叉排序树进行先根、中根和后根非递归遍历1)先根遍历先根遍历先访问根，再访问左儿子，接着访问右儿子。上图中的树，如果用先根遍历，顺序则是A-B-E-F-C要实现非递归遍历，必须使用循环来进行遍历。这就需要使每次循环时，都有一致的操作。为了一致性，先定义每次循环中的一致性操作：每次循环只处理一个节点，也就是打印当前节点，其左节点要等到下次循环再打印，这时，如果当前节点有左右节点，则需要储存当前节点的左节点和右节点，以便下次循环时取出打印，如果没有左右节点，则直接进入下次循环。在这里，有两种数据结构可用于储存待打印节点，一个是队列，一个是栈。先尝试队列，队列的特性是先进先出，我们希望在访问完当前节点后，储存当前节点的左节点和右节点，以便下次循环进取出进行打印，因此，节点储存的顺序必须为先储存左节点，再储存右节点。以上图的树为例：当用队列时，会先访问A节点，然后储存B到队列，再储存C到队列，此时，队列中的元素为BC。下次循环时，会把B出列，访问完B后，再储存E和F，此时，队列中的元素为CEF。下次循环时，会把C出列进行访问。显然，这种访问顺序A-B-C不是正确的访问顺序，正确的应该是A-B-E，因此队列并不能满足要求。接下来用栈进行储存尝试。当使用栈时，由于栈的特性为后进先出，故在第一次循环时，先访问A，然后把C入栈，再把B入栈，这时栈中的元素为CB。下次循环时，把B出栈进行访问，然后把F入栈，再把E入栈。这时，访问顺序为A-B-E-F-C，因此，我们可以用栈来作为循环遍历时的储存数据结构。此时，每轮循环的步骤就很清晰了：如果栈非空，出栈一个元素作为当前节点，先访问或者打印当前节点，接着，如果当前节点有左儿子或者右儿子，则先把右儿子入栈，再把左儿子入栈然后进入下次循环。如果当前节点没有儿子，则直接进入下次循环。具体代码如下：voidpreorderTraversal(Treetree){Stackstack=createStack(10);push(tree,stack);while(!isStackEmpty(stack)){TreePositionnode=pop(stack);printf(%d,node-element);if(node-right!=NULL){push(node-right,stack);}if(node-left!=NULL){push(node-left,stack);}}}2)中根遍历中根遍历中，先访问当前节点的左儿子，再访问当前节点，最后访问右儿子。上图的树中，中根遍历的顺序为D-B-F-E-A-C。在中根遍历过程中，要访问当前节点，首先要访问当前节点的左节点，而如果左节点又有左节点，则会一直向左下去。比如要访问A，则首先要访问B，要访问B则要先访问E。因此，在循环遍历开始前，可以先将A以及其左边的节点全部压入栈中，此时，栈中的元素为ABD，然后开始循环遍历。在循环中，先从栈中弹出一个节点，访问该节点，然后判断该节点是否有右节点，如果有右节点，则把其右子树中右节点开始的所有左节点压入栈中，这样，下一次循环就能访问到右节点所在子树的最左边节点了。因为要访问右节点，必须先访问右节点的左子树中的最左边的元素。比如上图的树中，在弹出B的时候，访问B，然后B有右节点E，因此，把EF都入栈，然后开始下一次循环。下一次循环开始时，就能取出F进行访问了。具体代码如下：/***中序遍历*/voidinorderTraversal(Treetree){Stackstack=createStack(30);if(tree==NULL){printf(thetreeisNULL,can'ttraversal\n);}else{pushLeftToStack(tree,stack);while(!isStackEmpty(stack)){TreePositionnode=pop(stack);printf(%d,node-element);if(node-right){pushLeftToStack(node-right,stack);}}printf(\n);}}其中的pushLeftToStack()方法从该节点开始，一直向左，把左节点全部压入栈中，代码如下：staticvoidpushLeftToStack(Treetree,Stackstack){while(tree){push(tree,stack);tree=tree-left;}}3)后根非递归遍历后根遍历中，先访问当前节点的左儿子，再访问右儿子，最后才访问当前节点。在上图的树中，访问的顺序为D-F-E-B-C-A。要实现非递归遍历，必须明确每一次循环中要进行的操作。和中根遍历相似，在循环开始前应该先把根节点开始，一直向左的节点压入栈中。然后再开始循环，循环开始时先出栈一个节点，如果该节点没有右儿子，那么就可以直接访问该节点了，但如果该节点有右儿子，那么就还不能访问该节点，必须先访问完该节点的右子树。如上图中，先弹出D，由于D没有右儿子，则可以直接访问，进入下一次循环。但弹出B时，由于B有右儿子E，那么此时还不能访问B，因此要将B重新压回栈中，然后再把EF入栈。这里的问题在于，当访问完FE后，又回把B重新出栈。如果按照刚才的做法，由于B还是有右儿子，这样，B又会重新压入栈，同时EF也会再次入栈，这样就会造成无限循环。一种解决这种无限循环的方式是：访问完D后，出栈B，由于B有右儿子，为了避免后面的无限循环，可以在把B重新入栈时，先用临时变量T保存B的右儿子，然后设置B的右儿子为空，然后再把B入栈，接着再把临时变量T作为原B的右儿子入栈，这样，再次弹出B时，由于B的儿子为空了，所以这次会直接访问B，从而避免了无限循环。但是这样破坏了树的结构，显然是不好的。因此要寻找另外的办法来避免无限循环，现在的重点是标识出B已经被重新压入过一次栈了，也就是说B被压了两次栈了。如果可以标识出来，则在访问完FE时，B重新出栈时，由于B已经两次入栈了，故可以直接访问B了。在这里采取的做法是：创建多一个栈，设其为T，第一次弹出B时，由于B有右儿子。则把B压回到原本的栈中，同时也把B压入栈T中。这样，每次弹出一个节点时，如果这个节点有右儿子则先和栈T中的最顶元素做下对比，如果和栈T中的最顶元素相同，则证明这个有右儿子的节点在之前已经被压入多一次栈了。因此，可以直接访问这个节