二叉树层次遍历

内蒙古科技大学本科生课程设计说明书题目：数据结构课程设计——二叉树的遍历和应用学生姓名：学号：专业：班级：指导教师：2013年5月29日内蒙古科技大学课程设计说明书内蒙古科技大学课程设计任务书I内蒙古科技大学课程设计说明书目录内蒙古科技大学课程设计任务书..............................................................错误！未定义书签。

目录 (II)第一章需求分析 (3)1.1课程设计目的 (3)1.2任务概述 (3)1.3课程设计内容 (3)第二章概要设计 (5)2.1设计思想 (5)2.2二叉树的遍历 (5)2.3运行界面设计 (6)第三章详细设计 (7)3.1二叉树的生成 (7)3.2二叉树的先序遍历 (7)3.3 二叉树的中序遍历 (8)3.4二叉树的后续遍历 (8)3.5主程序的设计 (8)第四章测试分析 (11)4.1二叉树的建立 (11)4.2二叉树的先序、中序、后序遍历 (11)第五章课程设计总结 (12)附录：程序代码 (13)致谢 ···········································································································错误！未定义书签。

数据结构与算法系列研究五——树、⼆叉树、三叉树、平衡排序⼆叉树AVL树、⼆叉树、三叉树、平衡排序⼆叉树AVL⼀、树的定义树是计算机算法最重要的⾮线性结构。

树中每个数据元素⾄多有⼀个直接前驱，但可以有多个直接后继。

树是⼀种以分⽀关系定义的层次结构。

a.树是n(≥0)结点组成的有限集合。

{N.沃恩}(树是n(n≥1)个结点组成的有限集合。

{D.E.Knuth})在任意⼀棵⾮空树中：⑴有且仅有⼀个没有前驱的结点----根(root)。

⑵当n>1时，其余结点有且仅有⼀个直接前驱。

⑶所有结点都可以有0个或多个后继。

b. 树是n(n≥0)个结点组成的有限集合。

在任意⼀棵⾮空树中：⑴有⼀个特定的称为根（root）的结点。

⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的⼦集T1，T2，…，Tm。

每个集合本⾝⼜是⼀棵树，并且称为根的⼦树（subtree）树的固有特性---递归性。

即⾮空树是由若⼲棵⼦树组成，⽽⼦树⼜可以由若⼲棵更⼩的⼦树组成。

树的基本操作1、InitTree(&T) 初始化2、DestroyTree(&T) 撤消树3、CreatTree(&T,F) 按F的定义⽣成树4、ClearTree(&T) 清除5、TreeEmpty(T) 判树空6、TreeDepth(T) 求树的深度7、Root(T) 返回根结点8、Parent(T,x) 返回结点 x 的双亲9、Child(T,x,i) 返回结点 x 的第i 个孩⼦10、InsertChild(&T,&p,i,x) 把 x 插⼊到 P的第i棵⼦树处11、DeleteChild(&T,&p,i) 删除结点P的第i棵⼦树12、traverse(T) 遍历树的结点：包含⼀个数据元素及若⼲指向⼦树的分⽀。

●结点的度: 结点拥有⼦树的数⽬●叶结点: 度为零的结点●分枝结点: 度⾮零的结点●树的度: 树中各结点度的最⼤值●孩⼦: 树中某个结点的⼦树的根●双亲: 结点的直接前驱●兄弟: 同⼀双亲的孩⼦互称兄弟●祖先: 从根结点到某结点j 路径上的所有结点（不包括指定结点）。

一、基础知识题6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。

【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立n= n0+n1+n2+…+nm (1)n=B+1= n1+2n2 +…+mnm+1 (2)由(1)和(2)得叶子结点数n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉树上有1001个结点，求叶子结点的个数。

【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则n= n0+ n1+ n2n=2n0+n1-11002=2n0+n1由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。

本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。

虽然解法也对，但步骤多且复杂，极易出错。

6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。

【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。

6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。

【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。

若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。

6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。

公共基础专题探究——二叉树1．6 树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。

在树结构中，没有前件的结点只有一个，称为树的根结点，简称树的根。

每一个结点可以有多个后件，称为该结点的子结点。

没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。

为该结点的左子树与右子树。

二叉树的基本性质：必考的题目（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）二叉树中 n = n0 +n1 +n2k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。

若干结点。

二叉树的遍历：（一般画个图要你把顺序写出来）后序遍历（访问根结点在访问左子树和访问右子树之后）重点题型：二叉树的遍历例1：某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为（DCBA ）。

【解析】前序序列为ABCD，可知A为根结点。

根据中序序列为DCBA可知DCB是A的左子树。

根据前序序列可知B是CD的根结点。

再根据中序序列可知DC是结点B的左子树。

根据前序序列可知，C是D的根结点，故后序序列为DCBA例2：对下列二叉树进行前序遍历的结果为 ABDYECFXZ例3：设二叉树如下，则后序序列为 DGEBHFCA【解析】本题中前序遍历为ABDEGCFH，中序遍历为DBGEAFHC，后序遍历为DGEBHFCA完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后堆排序问题：例1：已知前序序列与中序序列均为ABCDEFGH，求后序序列【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 已知ABCDEFGH中：L-D-R 已知ABCDEFGH后：L-R-D 待求由此可知，L=0，D-R= ABCDEFGH故R-D=HGFEDCBA，即后序序列= HGFEDCBA变式训练1：已知后序序列与中序序列均为ABCDEFGH，求前序序列答案：HGFEDCBA，（这次R=0）结论：若前序序列与中序序列均为某序列，则后序序列为该序列的倒序，且为折线；同样地，若后序序列与中序序列均为某序列，则前序序列为该序列的倒序，且为折线例2：已知前序序列=ABCD，中序序列=DCBA，求后序序列【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 已知ABCD中：L-D-R 已知DCBA后：L-R-D 待求因为ABCD与DCBA正好相反，由此可知，R=0所以D-L=ABCD，即L-D=DCBA所以后序序列= DCBA变式训练2-1：中序序列=BDCA，后序序列=DCBA，求前序序列【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 待求中：L-D-R 已知BDC,A后：L-R-D 已知DCB,A通过观察可知，R=0，L={B,D,C}，D=A中、后变换时，{B,D,C}发生了变化，说明左子树结构特殊，进一步令中’：L’-D’-R’已知B,DC后’：L’-R’-D’已知DC,B可知L’=0，即D’=B，R’= DC可以画出二叉树示意图为：Array所以前序序列= ABCD变式训练2-2：中序序列=ABC，后序序列=CBA，求前序序列【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 待求中：L-D-R 已知ABC后：L-R-D 已知通过观察可知，L=0，D-R=ABC，R-D=CBA所以前序序列=D-L-R= D-R=ABC变式训练2-3：前序序列=ABC，中序序列=CBA，求后序序列【解析】设根节点为D≠0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 已知A,BC中：L-D-R 已知CB,A后：L-R-D 待求通过观察可知，D=A ，L={B,C}，R=0所以后序序列=CBA (一边偏)题型二：求二叉树的深度。