第5章树与二叉树2008_0320_1241.ppt

后序遍历二叉树的递归算法如下： void PostorderTraverse(BiTree T) { if(T)/*若二叉树非空，则后序遍历*/ { PostorderTraverse(T-lchild); PostorderTraverse(T-rchild); printf(%c,T-data); } } 上述二叉树遍历算法的时间复杂度均为O(n)其中n为树的结点数。算法的实现是对已存在的二叉树的二叉链表进行的操作，必须事先建立一棵二叉树的二叉链表。构造二叉链表的方法很多，这里介绍一个基于先序遍历的构造算法。算法的输入是二叉树的先序序列，为了指示空指针信息，在先序序列中用一个空格符表示一个空指针的位置。 例如，对图5-7所示二叉树，按下列次序输入字符序列：ABφφφDFφCφφφEφφ（用空格表示图5-7所示二叉树的空指针位置后的满二叉树的先序序列），可建立相应的二叉链表，其中φ表示空格字符。算法如下 ： CreateBiTree(BiTree *T) { char ch; if((ch=getchar())==) *T=NULL; else { /*生成根结点后递归构造左右子树*/ *T =(BiTree)malloc(sizeof(BiTNode)); (*T)-data=ch; CreateBiTree((*T)-lchild); CreateBiTree((*T)-rchild); } } 5.5 树的存储结构 树在计算机内有多种表示方法，下面介绍三种常用双亲表示法、孩子表示法、孩子兄弟表示法。 1.双亲表示法 用一组连续空间存储数的结点，同时在每一个结点中附设一个指示器，指示其双亲结点的位置。图5-12 树的双亲表示法示例 图5-12 树的双亲表示法 2.孩子表示法 由于树中每个结点可能有多个孩子，因此可用多重链表来存储一棵树。链表中的结点由一个数据域和若干个指针域组成，每个指针域指向该结点的一个孩子。由于树中每个结点的度不同，所以链表中的结点可以采用定长表示，也可以采用不定长表示。 假设树的度数为d，则在定长表示中，结点的结构如图5-13所示。 data ch1 ch2 … chd 图5-13 孩子表示法的定长结点的结构 在不定长表示中，结点的结构如图5-14所示。 data d ch1 ch2 … chd 这里，data表示自身的数据，d表示结点的度，而ch1，ch2，…，chd 表示第1,2,…,d个孩子的指针。 图5-14 孩子表示法的不定长结点的结构 图5-15 就是图5-12 中树的多重链表表示。 图5-15 树的孩子表示法 如果把孩子链接成一个带表头结点的单链表，表头结点中存放双亲的信息，这些表头结点又组成一个线性表，那么图5-12中的树可用图5-16所示结构表示。该方法实际上是把双亲表示法和孩子表示法结合起来。 图5-16 树的带双亲的孩子链表表示法 3.孩子兄弟表示法 孩子兄弟表示法又称二叉链表表示法。在这种表示法中，结点的结构如图5-17所示。 firstchild data nextbrother 图5-17 孩子兄弟表示法的结点结构 这里,data存放结点的有关信息,firstchild指向该结点的第一个孩子,nextbrother指向下一个兄弟结点。图5-18就是图5-12中树的孩子兄弟表示法。 图5-18 树的孩子兄弟表示法 1.树转换为二叉树 将树转换成二叉树的方法为： （1）在兄弟之间加一连线； （2）对每个结点，除了其最左孩子外，去除它与其余孩子之间的联系； （3）将保留下来的边作为左子树的边，兄弟间的连线作为右子树的边（即各兄弟间的连线依左边的兄弟结点为轴，顺时针旋转45度角）。 5.6 森林与二叉树的转换 图5-19 树转换为二叉树示例 以图5-19（a）所示的树为例，可转换为如图5-19（d）所示的二叉树。 从树转换为二叉树的过程可知，任何一棵树对应的二叉树，其右子树必空，也就是说，所有的树都可以转化为二叉树，但不是所有的二叉树都可以转化为树。 2.森林转换为二叉树 森林是树的集合。将一个森林转换成二叉树的方法是：先将森林中的每棵树转换为二叉树，然后把各二叉树的根结点看成兄弟，用直线把它们连到一起，经整理后可得到相应的二叉树。 下面图5-20（b）是对图5-20（a）所示的森林进行转换后得到的结果，图5-20（c）是经整理后得到的二叉树。 图