第7章树形结构

1、 小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都來玩高尔夫，以至于所有员工都忙的团团转还是应付不过来，而有些天不知道什么原因却一个人也不来，俱乐部为雇员数量浪费了不少资金。 小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，以适时调整雇员数量。因此首先他必须了解人们决定是否打球的原因。线性结构线性结构树结构树结构第第一一个数据元素个数据元素根结点（只有根结点（只有一一个）个）无前驱无前驱无双亲无双亲最后最后一一个数据元素个数据元素叶子结点叶子结点(可以有可以有多多个个)无后继无后继无孩子无孩子其它数据元素其它数据元素其它结点其它结点一个前驱一个

2、前驱,一个后继一个后继一个双亲一个双亲,多个孩子多个孩子一对一一对一 一对多一对多树的逻辑结构树的逻辑结构7.1 7.1 树的基本概念树的基本概念 7.1.1 7.1.1 树的定义树的定义 7.1.3 7.1.3 树的基本术语树的基本术语 7.1.2 7.1.2 树的表示树的表示7.1.1 树的定义：树的定义：核心关系：层次关系。核心关系：层次关系。 A C G J B E D F I H M K L 树形表示法树形表示法 树：树：n（n0）个）个结点结点的有限的有限集合集合。当。当n0时，称为时，称为空树；任意一棵非空树满足以下条件：空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为

3、有且仅有一个特定的称为根根的结点；的结点； 当当n1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m（m0）个）个互不相交互不相交的有限集合的有限集合T1, ,T2, , , ,Tm，其中，其中每个集合又是一棵树，并称为这个根结点的每个集合又是一棵树，并称为这个根结点的子树子树。1.1 通俗定义通俗定义树形表示法广义表表示法a(b(e,f,g),c(h),d(i,j)树是树是n(n0)n(n0)个结点的有限集，在任意一棵树中：个结点的有限集，在任意一棵树中：1 1 有且只有一个特定的有且只有一个特定的根根(root)(root)结点；结点；2 2 当当n1n1时，其余结点可分

4、为时，其余结点可分为m(m0)m(m0)个互不相交的有限子集个互不相交的有限子集T T1 1,T,T2 2.T.Tm m，每个子集是一棵树，称为，每个子集是一棵树，称为子树子树。判断以下是否为树型结构判断以下是否为树型结构7.1.3 7.1.3 树的基本术语树的基本术语 1. 树的树的结点结点：包含一个：包含一个数据元素数据元素和指向其子树的和指向其子树的所有所有分支分支。 2.结点的度：一个结点拥有的子树的个数。结点的度：一个结点拥有的子树的个数。 A C G J B E D F I H M K L 树形表示法树形表示法 AA的度：3B的度：2C的度：1D的度：2E的度：0I的度：33.分支

5、结点与叶结点：度不为零的结点称为非终端结分支结点与叶结点：度不为零的结点称为非终端结点点,又叫又叫分支结点分支结点。度为零的结点称为。度为零的结点称为终端结点或叶终端结点或叶结点结点。4. 树的度：树中所有结点的度的最大值树的度：树中所有结点的度的最大值max(D(I)。含义：树中最大分支数为树的度。含义：树中最大分支数为树的度。A的度：3B的度：2C的度：1D的度：2E的度：0I的度：3 A C G B D I JEFH MKL 树形表示法树形表示法 树的度：树的度：31 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJCCBDEFKLHJA71234568910数据结构中讨论

6、的一般都是有序树数据结构中讨论的一般都是有序树 ACBGFEDACBGFEDCBDEFKLHJACGBDEFKLHMIJACGBDEFKLHMIJA结点的度：结点的度：一个结点含有的子树的个数称为该结点的度； 如结点D含有3个子树，则结点D的度为3，而结点C的度为1，结点K的度为0。叶结点或终端结点：叶结点或终端结点：度为零的结点称为叶结点； 如结点F的度为0，则为叶子结点。非终端结点或分支结点：非终端结点或分支结点：度不为零的结点； 双亲结点（父结点）：双亲结点（父结点）：含有孩子的结点称为其孩子的双亲结点； 例如，结点B是E,F的双亲结点（父结点）。孩子结点：孩子结点：一个结点子树的根结点

7、称为该结点的孩子结点； 例如，结点B的孩子结点有E,F两个。兄弟结点：兄弟结点：具有相同双亲结点的结点互称为兄弟结点； 如E,F互为兄弟结点。CGBDE FK LHMIJA树的度：树的度：一棵树中，最大的结点的度称为树的度；结点的层次：结点的层次：从根开始定义起，根为第一层，根的孩子为第二层； 树的高度或深度：树的高度或深度：树中结点的最大层次；堂兄弟：堂兄弟：双亲在同一层的结点互为堂兄弟； 结点的祖先：结点的祖先：从根到该结点所经分支上的所有结点；子孙：子孙：以某结点为根的子树中任一结点都称为该结点的子孙。森林：森林：由m（m=0）棵互不相交的树的集合称为森林；CGBDE FK LHMIJA

8、 1.有一棵树如图所示，回答下面的问题 （1）这棵树的叶子结点是_。 （2）结点k3的度是_ （3）这棵树的度是_ （4）这棵树的深度是_ （5）结点k3的孩子结点是_ （6）这棵树的根结点是_ （7）结点k3的双亲结点是_二叉树的定义二叉树的定义 二叉树是二叉树是n（n0）个结点的有限集合，该集合或）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点者为空集（称为空二叉树），或者由一个根结点和两棵和两棵互不相交互不相交的、分别称为根结点的的、分别称为根结点的左子树左子树和和右子树右子树的二叉树组成。的二叉树组成。二叉树的逻辑结构二叉树的逻辑结构问题转化：将树转换为二叉树，从

9、而利用二叉树解问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。决树的有关问题。研究二叉树的意义？研究二叉树的意义？把硬币分成三组，从八枚硬币中任取六枚a、b、c、d、e、f，在天平两端各放三枚进行比较。 假设a、b、c三枚放在天平的一端，d、e、f三枚放在天平的另一端，可能出现如图所示的三种比较结7.2 7.2 二叉树概念和性质二叉树概念和性质 7.2.1 7.2.1 二叉树概念二叉树概念7.2.2 7.2.2 二叉树性二叉树性质质7.2.3 7.2.3 二叉树存储结构二叉树存储结构7.2.1 7.2.1 二叉树概念二叉树概念 二叉树也称为二次树或二分树，它是结点数为二叉树也称为二

10、次树或二分树，它是结点数为0或当节点数不为或当节点数不为0时每个结点最多只有左右两棵子树时每个结点最多只有左右两棵子树的树。的树。 特点是：特点是： （1）每个结点最多只有两棵树，既不存在度大于）每个结点最多只有两棵树，既不存在度大于2的结点。的结点。 （2）子树有左右之分，不能颠倒。）子树有左右之分，不能颠倒。思考：二叉树和度为思考：二叉树和度为2的树一样吗有什么区别？的树一样吗有什么区别？结点的孩子数结点的孩子数结点孩子的有序性结点孩子的有序性7.2.1二叉树的逻辑结构二叉树的逻辑结构ABCDEFGABAB二叉树的基本形态二叉树的基本形态空二叉树空二叉树只有一个根结点只有一个根结点左子树左

11、子树根结点只有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树二叉树的逻辑结构二叉树的逻辑结构二叉树的逻辑结构二叉树的逻辑结构特殊的二叉树特殊的二叉树斜树斜树1 . .所所有结点都只有左子有结点都只有左子树的二叉树称为树的二叉树称为左斜树左斜树；2 . .所有结点都只所有结点都只有右子有右子树的二叉树称为树的二叉树称为右斜树右斜树；3.3.左斜树和右斜树统称为左斜树和右斜树统称为斜树斜树。1. 在斜树中，每一层只有一个结点；在斜树中，每一层只有一个结点；2. .斜树的结点个数与其深度相同。斜树的结点个数与其深度相

12、同。 二叉树的逻辑结构二叉树的逻辑结构-斜树的特点：斜树的特点：ABCABC满二叉树满二叉树在一棵二叉树中，如果所在一棵二叉树中，如果所有分支结点都存在左子树有分支结点都存在左子树和右子树，并且所有叶子和右子树，并且所有叶子都在都在同一层上。同一层上。满二叉树的特点满二叉树的特点：1. 叶子只能出现在最下一层；叶子只能出现在最下一层；2. 只有度为只有度为0和度为和度为2的结点。的结点。CDEFGHIJKLM NO1112 13 14 15特殊的二叉树特殊的二叉树二叉树的逻辑结构二叉树的逻辑结构-A1523467BCDEFGLM89特殊的二叉树特殊的二叉树二叉树的逻辑

13、结构二叉树的逻辑结构-CDEFGHIJKLM NO1112 13 14 15CDEFGHIJ特殊的二叉树特殊的二叉树二叉树的逻辑结构二叉树的逻辑结构-在满二叉树中，从最后在满二叉树中，从最后一个结点开始，一个结点开始，连续连续去去掉掉任意任意个结点，即是一个结点，即是一棵完全二叉树。棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ特殊的二叉树特殊的二叉树二叉树的逻辑结构二叉树的逻辑结构-CDEFGHIJ特殊的二叉树特殊的二叉树二叉树的逻辑

14、结构二叉树的逻辑结构- 二叉树的概念二叉树的概念 二叉树的五种形态二叉树的五种形态 斜二叉树斜二叉树 满二叉树满二叉树 完全二叉树完全二叉树 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 满二叉树满二叉树 7.2.2 7.2.2 二叉树性质（二叉树性质（5 5个）个） 性质性质1 非空二叉树上第非空二叉树上第i层上至多有层上至多有2i-1个结点个结点,这里这里应有应有i1。 性质性质1 非空二叉树上第非空二叉树上第i层上至多有层上至多有2i-1个结点个结点,这里这里应有应有i1。证明：用归纳法证明：用归纳法（

15、1）当）当i=1 20 有一个根结点有一个根结点 成立成立（2）假设）假设 对所有的对所有的j(1=j1）,结点结点i的双亲为的双亲为 i/2 . (2) 若若2in时时。结点。结点i无左孩子，是叶结点；否则无左孩子，是叶结点；否则结点结点i的左孩子为结点的左孩子为结点2i。 (3)若若2i+1n时。结点时。结点i无右孩子；否则结点无右孩子；否则结点i的的左孩子为结点左孩子为结点2i+1。余下的性质是针对完全二叉树的（很重要）：余下的性质是针对完全二叉树的（很重要）：(2) 若若2in时。结点时。结点i无左孩子，是叶结点；否则结点无左孩子，是叶结点；否则结点i的的左孩子为结点左孩子为结点2i。

16、 (3)若若2i+1n时。结点时。结点i无右孩子；否则结点无右孩子；否则结点i的左孩子为的左孩子为结点结点2i+1。1）当）当i=1时，如果时，如果2i=2n 无左孩子，否则无左孩子，否则2i=2n 无右孩子，否则无右孩子，否则2i+1=3=n 结点结点3存在是结点存在是结点1的右孩子。的右孩子。第三条成立第三条成立2）假设对所有的结点假设对所有的结点j(1=j=i)有：有：j的左孩子为的左孩子为2j(2j=n),右孩子为右孩子为2j+1(2j+1=n)3)要证明要证明 j=i+1时等式成立时等式成立i+1的左孩子为的左孩子为 2（i+1） (2(i+1)=n)i+1的右孩子为的右孩子为 2（

17、i+1）+1 (2(i+1)+11）,结点结点i的双亲为的双亲为 i/2 . 用归纳法自己证明第五条性质非常重要，是二叉树顺序存储第五条性质非常重要，是二叉树顺序存储的理论基础的理论基础7.2.3 树、森林与二叉树的转换树、森林与二叉树的转换 1.兄弟加线兄弟加线.树转化为二叉树树转化为二叉树ABCDEFG2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线.ABCDEFG 1.兄弟加线兄弟加线.7.2.3 树、森林与二叉树的转换树、森林与二叉树的转换3.顺时针转动顺时针转动,使之使之层次分明层次分明.2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去

18、与删去与其他孩子的连线其他孩子的连线. 1.兄弟加线兄弟加线.ABCDEFG7.2.3 树、森林与二叉树的转换树、森林与二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系3.顺时针转动顺时针转动,使之使之层次分明层次分明.2.保留双亲与第一保留双亲与第一孩子连线孩子连线,删去与删去与其他孩子的连线其他孩子的连线. 1.兄弟加线兄弟加线.GDABECF7.2.3 树、森林与二叉树的转换树、森林与二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系总结：树转换为二叉树 加线加线树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。 去线去线对树中的每个结点，只保留它与第

19、一个对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间孩子结点之间的连线，删去它与其它孩子结点之间的连线。的连线。 层次调整层次调整以根结点为轴心，将树顺时针转动以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。一定的角度，使之层次分明。 森林转换为二叉树森林转换为二叉树 将森林中的每棵树转换成二叉树；将森林中的每棵树转换成二叉树； 从第二棵二叉树开始，依次把后一棵二叉树的根从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点结点作为前一棵二叉树根结点的右孩子，当所有二的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转叉树连起来后，

20、此时所得到的二叉树就是由森林转换得到的二叉树换得到的二叉树。7.2.3 树、森林与二叉树的转换树、森林与二叉树的转换IHGBCDAFE二叉树转换为树或森林二叉树转换为树或森林 加线加线若某结点若某结点x是其双亲是其双亲y的左孩子，则把结点的左孩子，则把结点x的右孩子、右孩子的右孩子、的右孩子、右孩子的右孩子、，都与结点，都与结点y用线连用线连起来；起来； 去线去线删去原二叉树中所有的双亲结点与右孩子结删去原二叉树中所有的双亲结点与右孩子结点的连线；点的连线； 层次调整层次调整整理由、两步所得到的树或森林，整理由、两步所得到的树或森林，使之层次分明。使之层次分明。 7.2.3 树、森林与二叉树的

21、转换树、森林与二叉树的转换FHGEAICDBFHGDCEBAIFEDCBAHGI加线加线去线去线层次调整层次调整IHGBCDAFE树、森林与二叉树的转换树、森林与二叉树的转换ACDBEFGJIH7.3 7.3 二叉树存储结构二叉树存储结构 7.3.1 7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 7.3.2 7.3.2 二叉树的链式存储结构二叉树的链式存储结构7.3.1 7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 用一组地址连续的存储单元，以层序的顺序用一组地址连续的存储单元，以层序的顺序存放二叉树的数据元素，结点的相对位置蕴含着存放二叉树的数据元素，结点的相对位置蕴含着结点

22、的关系。结点的关系。【注意注意】逻辑关系蕴含在这里：逻辑关系蕴含在这里：结点的相对位置结点的相对位置蕴含着结点的关系。蕴含着结点的关系。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 A B C D E F G H I J K123456789101112131415顺序存储结构顺序存储结构 一般二叉树的顺序存储没有左右孩子的地方填一般二叉树的顺序存储没有左右孩子的地方填0 A B C D E FG 一般二叉树一般二叉树 A B C D E 0 0 0 0 F G 0 0 0 0123456789101112131415顺序存

23、储结构顺序存储结构 例：深度为例：深度为K,只有只有K个结点的右单支树的存放：个结点的右单支树的存放： 分析分析:根据性质根据性质2：二叉树深度为：二叉树深度为K 最多有最多有2k-1个结点个结点 按顺序存储实际只使用按顺序存储实际只使用K个存储单元，浪费掉个存储单元，浪费掉2k-1-K 1 2 K 1 K 结论：顺序存储只适合完全二叉树，既不浪费空间，结论：顺序存储只适合完全二叉树，既不浪费空间，又能很快的确定结点存放的位置，以及结点的双亲又能很快的确定结点存放的位置，以及结点的双亲和左右孩子。但是对于一般二叉树可能造成存储空和左右孩子。但是对于一般二叉树可能造成存储空间的浪费。间的浪费。7

24、.3.2 7.3.2 二叉树的链式存储结构二叉树的链式存储结构 常用的：常用的：二叉链表二叉链表三叉链表三叉链表线索链表线索链表 A B C D E FG 一般二叉树一般二叉树 在二叉树的链接存储中在二叉树的链接存储中,结点的结构如下结点的结构如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存储对应的数据元用于存储对应的数据元素素,lchild和和rchild分别表示左指针域和右指针域分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点用于分

25、别存储左孩子结点和右孩子结点(即左、右即左、右子树的根结点子树的根结点)的存储位置。的存储位置。lchild data rchild 二叉树及其链式存储结构二叉树及其链式存储结构 优点：找孩子比较容易，找双亲很难优点：找孩子比较容易，找双亲很难 A B C E F D G A B C D E F G (a) (b) 在三叉链表的存储中在三叉链表的存储中,结点的结构如下结点的结构如下: typedef struct node ElemType data; struct node *lchild ,*parent,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存储对应的

26、数据元用于存储对应的数据元素素,lchild和和rchild分别表示左指针域和右指针域分别表示左指针域和右指针域,用用于分别存储左孩子结点和右孩子结点于分别存储左孩子结点和右孩子结点(即左、右子树即左、右子树的根结点的根结点)的存储位置，的存储位置， parent 指向结点的双亲。指向结点的双亲。lchild data parent rchild 二叉树及其链式存储结构二叉树及其链式存储结构 A B C E F D G (a) ABCDFEG 证明： （1）n=n0+n1+n2 （2）空链域=2n0+n1 （3）no=n2+1 A B C E F D G A B C D E F G (a) (

27、b) 7.5 7.5 二叉树的遍历二叉树的遍历7.5.1 7.5.1 二叉树遍历的概念二叉树遍历的概念7.5.2 7.5.2 二叉树遍历的实现递归及非递归二叉树遍历的实现递归及非递归算法算法二叉树的遍历操作二叉树的遍历操作 二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结点，使得每个结点被访问一访问二叉树中的所有结点，使得每个结点被访问一次且仅被次且仅被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化7.5 二叉树的逻辑结构二叉树的逻辑结构抽象操作，抽象操作，可以是对结点进行的各种可以是对结

28、点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 如果限定先左后右，则二叉树遍历方式有三种：如果限定先左后右，则二叉树遍历方式有三种：前序前序：DLR中序中序：LDR后序后序：LRD层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。 7.5.1 二叉树的逻辑结构二叉树的逻辑结构考虑二叉树的组成：考虑二叉树的组成：根结点根结点D左子树左子树L右子树右子树R二二叉叉树树前序遍历序列：前序遍历序列：A B D G C E FABCDEFG二叉树的遍历操作二叉树的遍历操

29、作 7.5 二叉树的逻辑结构二叉树的逻辑结构中序遍历序列：中序遍历序列：D G B A E C FABCDEFG二叉树的遍历操作二叉树的遍历操作 7.5 二叉树的逻辑结构二叉树的逻辑结构后序遍历序列：后序遍历序列：G D B E F C AABCDEFG二叉树的遍历操作二叉树的遍历操作 7.5 二叉树的逻辑结构二叉树的逻辑结构层序遍历序列：层序遍历序列：A B C D E F GABCDEFG二叉树的遍历操作二叉树的遍历操作 7.5 二叉树的逻辑结构二叉树的逻辑结构 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 先序序列：先序序列：ABDHIEJK

30、CFG中序序列：中序序列：HDIBJEKAFCG后序序列：后序序列：HIDJKEBFGCA先序序列：先序序列：ABDEHJKLMNCFGI中序序列：中序序列：DBJHLKMNEAFCGI后序序列：后序序列：DJLMNKHEBFGICA 在二叉树的链接存储中在二叉树的链接存储中,结点的结构如下结点的结构如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存储对应的数据元用于存储对应的数据元素素,lchild和和rchild分别表示左指针域和右指针域分别表示左

31、指针域和右指针域,用于分别存储左孩子结点和右孩子结点用于分别存储左孩子结点和右孩子结点(即左、右即左、右子树的根结点子树的根结点)的存储位置。的存储位置。lchild data rchild 二叉树及其链式存储结构二叉树及其链式存储结构 (a) (b) A B C E F D A B C D E F 1. 先序遍历先序遍历DLR先序遍历二叉树的过程是：先序遍历二叉树的过程是：(1) 访问根结点访问根结点D；(2) 先序遍历左子树先序遍历左子树L；(3) 先序遍先序遍历右子树历右子树R。先序序列：先序序列：ABDECF/*先序遍历的递归算法先序遍历的递归算法*/void PreOrder(BTN

32、ode *b) if (b!=NULL) printf(%c ,b-data); /*访问根结点访问根结点*/ PreOrder(b-lchild); PreOrder(b-rchild); A B C E F D lchild data rchild /*先序遍历的递归算法先序遍历的递归算法*/void PreOrder(BTNode *b) if (b!=NULL) printf(%c ,b-data); /*访问根结点访问根结点*/ PreOrder(b-lchild); PreOrder(b-rchild); PreOrder(&A)APreOrder(A-lchild=B);

33、BPreOrder(B-lchild=D);DPreOrder(D-lchild=NULL);PreOrder(D-rchild=NULL);PreOrder(B-rchild=E);EPreOrder(E-lchild=NULL);PreOrder(E-rchild=NULL);PreOrder(A-rchild=C);CPreOrder(C-lchild=NULL);PreOrder(C-rchild=F);FPreOrder(F-lchild=NULL);PreOrder(F-rchild=NULL); A B C D E F 2. 中序遍历中序遍历LDR 中序遍历二叉树的过程是：中序遍

34、历二叉树的过程是： (1) 中序遍历左子树中序遍历左子树L；(2) 访问根结点访问根结点D； (3) 中序遍历右子树中序遍历右子树R。中序序列：中序序列：DBEACF/*中序遍历的递归算法中序遍历的递归算法*/void InOrder(BTNode *b) if (b!=NULL) /*访问根结点访问根结点*/ InOrder(b-lchild); printf(%c ,b-data); InOrder(b-rchild); A B C E F D 3. 后序遍历后序遍历后序遍历二叉树的过程是：后序遍历二叉树的过程是：(1) 后序遍历左子树；后序遍历左子树；(2) 后序遍历右子树；后序遍历右子

35、树；(3) 访问访问根结点。根结点。后序序列：后序序列：DEBFCA void PostOrder(BTNode *b) /*后序遍后序遍历递归算法历递归算法*/ if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /*访访问根结点问根结点*/ A B C E F D 习题一：编写三种遍历方式的递归算法，打印遍历序列。 A B C E F D 设二叉树设二叉树bt的存储结构如下：的存储结构如下：其中，其中，bt为树根结点指针，为树根结点指针，lchild、rchild分别为结点的左、右孩子指针域，分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，在这里使用结点编号作为指针域值，0表示表示指针域值为空；