二叉树操作

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称二叉树操作专业计算机科学与技术班级10计本2班学号10012078姓名陶健联系方式15156587981指导教师江家宝2011年12月29日目录1、数据结构课程设计任务书..............................................................................................１1.1、题目.....................................................................................................................１1.2、要求.....................................................................................................................１2、总体设计.......................................................................................................................１2.1、功能模块设计......................................................................................................１3、详细设计...........................................................................................................................3.1、程序中所采用的数据结构及存储结构的说明........................................................１3.2、算法的设计思想...................................................................................................１4、调试与测试：................................................................................................................３4.1、调试方法与步骤：...................................................................................................4.2、测试结果的分析与讨论：....................................................................................３4.3、测试过程中遇到的主要问题及采取的解决措施：.......................错误!未定义书签。5、时间复杂度的分析：.....................................................................................................６6、源程序清单和执行结果.................................................................................................６7、C程序设计总结........................................................................................................１９8、致谢..........................................................................................................................１９9、参考文献...................................................................................................................１９第１页1、数据结构课程设计任务书1.1、题目二叉树操作1.2、要求1．已知二叉树的后序、中序序列，恢复此二叉树；2．求二叉树高度、分支结点数和叶子结点数；3．插入结点到指定位置、删除指定结点；4．将二叉树中所有结点的左右子树交换。5．对二叉树进行层序、非递归中序遍历。2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：3.1、程序中所采用的数据结构及存储结构的说明#includestdlib.h#includestdio.htypedefstructLNode{structLNode*lchild;structLNode*rchild;chardata;}Tree,*Ptree;3.2、算法的设计思想已知二叉树的后序、中序序列，恢复此二叉树比方说有这么个二叉树，如图：对于这样一颗树，后序遍历和中序遍历得到的结点序列分别为：后序：DECBIGHFA……………（式1）中序：DCEBAGIFH……………（式2）后序和中序遍历满足的规则是：后序：左-右-根创建二叉树二叉树中序zhoongxu恢复二叉树创建二叉树二叉树高度二叉树分支节点数二叉树叶子节点数创建二叉树插入节点到指定位置删除指定节点创建二叉树结点左右互换创建二叉树二叉树层序遍历二叉树中序遍历退出二叉树后序第２页中序：左-根-右所以，后序遍历的最后一个结点一定是整棵树的根结点即A另外，(式2)中A的左边一定是A的左子树上的结点（因为只有左子树遍历结束了才会轮到A），同理（式2）中A的右边一定是右子树上的结点（只有A遍历过了才会轮到右子树），如果在（式2）中一个结点的左边结点（右边结点）为空或者是已经访问过的，则该结点只有左子树（右子树）对于（式1）我们可以总结出相似的结论（自己总结）我把我总结的算法思想写出来，理解下吧。设某一个结点变量N初始化为后序遍历表中的最后一个结点（在这里N=A）Function(结点N){If（N在（式2）的右子树=TRUE）{则N在（式1）中的前一个结点=N的右子树根结点If(N在N在（式2）的左子树=TRUE){则N在（式2）中的前一个结点=N的左子树根结点递归function（N-Left）}递归function（N-Right）}Elseif(N在（式2）的左子树=TRUE){N在（式1）中的前一个结点=N的左子树根结点递归function（N-Right）}return..}求二叉树高度、分支结点数和叶子结点数二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。一、叶子数=[n/2],(向上取整）令度为0的结点数n0，度为1的结点数n1，度为2的结点数n2则n=n0+n1+n2；由二叉树性质三知：n2=n0-1；带入得n=2*n0+n1-1；由完全二叉树的定义可以看出，n1只可能取两个值0和1第３页所以有2*n0-1=n=2*n0即n0-1/2=n/2=n0由于n/2为整数，所以n0=[n/2],(向上取整）二、分支结点数=[n/2],(向下取整）由于分支结点数=n-n0利用一的结论显然分支结点数=[n/2],(向下取整）插入结点到指定位置、删除指定结点直接找到那个你所要插入的的节点，然后在后面插入，改变next的指针方向，指向被插入的节点上，然后把被插入的节点的next指向被插入节点的前节点以前的next所指的方向。将二叉树中所有结点的左右子树交换交换过程中需要用一个指针站来实现。对二叉树进行层序、非递归中序遍历二叉树的层次遍历，借助队列来实现，这里用数组实现队列1、先设一个栈s和一个指向树根的指针p，用p指指向结点的lchild并顺其而下直到p==NULL跳出循环，在这一过程中把每个节点入栈，则此时的p指向的是树的最左结点。2、栈顶元素出栈以访问最左结点。（此步很重要，是为了实现按栈内元素的顺序后入先出访问结点访问最左结点的根结点。栈内元素逐一退栈即为中序遍历的元素顺序。）3、访问最左结点的根结点。4、由于将右子树理解为一个子树，对其的遍历也是采用中序遍历的方法，故将右子树的根结点理解为开始遍历树时的根结点，故可用语句p=p-rchild，则又开始了对一个树的遍历，p指针又会走遍右子树的每一个结点。4、调试与测试：4.1、测试结果的分析与讨论：（测试要写出测试用例及每个用例结果的的截图）第４页第５页第６页5、时间复杂度的分析：O(n)6、源程序清单和执行结果已知二叉树的后序、中序序列，恢复此二叉树.#includestdlib.h#includestdio.htypedefstructLNode{structLNode*lchild;structLNode*rchild;chardata;}Tree,*Ptree;charMid[20],hind[20];PtreeInsert(chardata,Ptreetree);intLocatation(chara,charb);voidDisplay(Ptreetree);voidmain(){chardata;inti=0;PtreeT;T=NULL;printf(请输入中序序遍历序列:\n);data=getchar();第７页while(data!='\n'){Mid[i++]=data;data=getchar();}Mid[i]='\0';printf(请输入后序遍历序列：\n);data=getchar();i=0;while(data!='\n'){hind[i++]=data;data=getchar();}while(i0){T=Insert(hind[--i],T);}Display(T);}PtreeInsert(chardata,Ptreetree){if(tree==NULL){tree=(Ptree)malloc(sizeof(Tree));tree-data=data;tree-lchild=tree-rchild=NULL;}elseif(Locatation(data,tree-data)0){tree-rchild=Insert(data,tree-rchild);}else{tree-lchild=Insert(data,tree-lchild);}returntree;}voidDisplay(Ptreetree){if(tree==NULL){return;}else{printf(%c,tree-data);Display(tree-lchild);Display(tree-rchild);}}intLocatation(chara,charb){intc,d;for(inti=0;Mid[i];i++){if(Mid[i]==a)c=i;if(Mid[i]==b)d=i;}returnc-d;求二叉树高度、分支结点数和叶子结点数#includestdio.h#includestdlib.h#includemath.h/*二叉树