树结构的定义和基本操作

1、第第6 6章章 树树6.1树结构的定义和基本操作树结构的定义和基本操作 6.2二叉树二叉树6.3遍历二叉树遍历二叉树 6.4树和森林树和森林6.5树的应用树的应用习题习题 前面谈的基本上是前面谈的基本上是线性表结构线性表结构，线性表，线性表,栈、队列、串、一维数组，即使二维数组栈、队列、串、一维数组，即使二维数组(矩矩阵结构、十字类别阵结构、十字类别)也不过只是线性表的组合，也不过只是线性表的组合，即：除首元素和尾元素以外，每一个元素有即：除首元素和尾元素以外，每一个元素有唯一的前驱唯一的前驱和和后续后续元素。元素。 树形结构树形结构是一种重要的是一种重要的非线性结构非线性结构，讨，讨论的是论

2、的是层次和分支关系层次和分支关系，即：除了有一个根，即：除了有一个根元素没有前驱以外，每一个元素都有元素没有前驱以外，每一个元素都有唯一的唯一的前驱元素前驱元素；另外，每一个元素；另外，每一个元素有零个或多个有零个或多个后继元素后继元素。例如，人类社会的族谱和各种社。例如，人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计会组织机构都可以用树来形象表示。树在计算机领域中也得到广泛应用。算机领域中也得到广泛应用。 6.1 树结构的定义和基本操作树结构的定义和基本操作 6.1.1 树的定义树的定义 递归定义：递归定义： 树树(tree)是是n(n0)个结点的有限集。在任意一棵树中：个结点

3、的有限集。在任意一棵树中： (1)有且只有一个特定的称为根有且只有一个特定的称为根(root)的结点。的结点。 (2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互不相交的个互不相交的有限集有限集t1，t2，tm，其中每一个集合本身又是一，其中每一个集合本身又是一棵树，称为子树棵树，称为子树(subtree)。 图图6.1所示，在图中的树有所示，在图中的树有13个结点，个结点，a是树根，其是树根，其余结点构成三个互不相交的子集：余结点构成三个互不相交的子集：t1=b，e，f，k，l，t2=c，g，t3=d，h，i，j，m；t1，t2和和t3都是根都是根a的子树，且它们本身也是一棵树

4、。如在的子树，且它们本身也是一棵树。如在t1中，中，b是该子树根，其余结点又构成两个互不相交子集，是该子树根，其余结点又构成两个互不相交子集，t11=e，k，l和和t12=f，t11和和t12都是根都是根b的子树，的子树，且它们本身也是一棵树。且它们本身也是一棵树。 图6.1 树的示例 上面是树的一个递归定义，树除了该递归定义外，还上面是树的一个递归定义，树除了该递归定义外，还有其它定义。如图有其它定义。如图6.2所示为图所示为图6.1中树的各种表示中树的各种表示.从图从图6.1的示例可以看出，的示例可以看出，树有两个特点：树有两个特点： (1) 树的根结点没有树的根结点没有前驱结点，其余结点

5、有前驱结点，其余结点有且只有一个前驱结点。且只有一个前驱结点。 (2) 树结点可以有零树结点可以有零个或多个后继结点。个或多个后继结点。 树结构描述的是层树结构描述的是层次和分支关系。次和分支关系。 图6.2 树的其它三种表示方法 图图6.2(a)是以嵌套集合的形式表示是以嵌套集合的形式表示(任何两个集合，或不相交，任何两个集合，或不相交，或一个包含另一个或一个包含另一个)；图；图6.2(b)是以广义表的形式表示，根作为是以广义表的形式表示，根作为子树森林组成的表的名字写在表的左边；图子树森林组成的表的名字写在表的左边；图6.2(c)用的是凹入用的是凹入表示法。表示法。 6.1.2 树的常用术

6、语树的常用术语 结点：结点：是包含一个数据元素和若干指向其子树的分支是包含一个数据元素和若干指向其子树的分支 (即关系即关系). 结点的度：结点的度：结点拥有的子树数。结点拥有的子树数。 叶子：叶子：度为度为0的结点。的结点。 分支结点：分支结点：度不为度不为0的结点。的结点。 树的度：树的度：树内各结点的度的最大值，图树内各结点的度的最大值，图6.1所示树是所示树是 一一 个个3叉树叉树. 孩子结点孩子结点(child)：结点的后继，结点子树的根结点。结点的后继，结点子树的根结点。双亲结点双亲结点(parent)：孩子结点的前驱。孩子结点的前驱。s是是f的孩子的孩子,则则f是是s的双亲的双亲

7、. 兄弟结点兄弟结点(sibling)：同一个双亲的孩子之间互称为兄弟。同一个双亲的孩子之间互称为兄弟。 祖先结点：祖先结点：从根到该结点的所经过分支上的所有结点从根到该结点的所经过分支上的所有结点, 图图6.1树中树中l结点的祖先结点是结点的祖先结点是a，b，f。 子孙结点：子孙结点：以某结点为根的子树中任一结点都称为该结点以某结点为根的子树中任一结点都称为该结点 的子孙的子孙. 图图6.1树中树中d的子孙结点为的子孙结点为h，i，j，m.结点的层次：结点的层次：根是第根是第1层，依次为第层，依次为第2层层。 树的深度：树的深度：树中结点的最大层次，图树中结点的最大层次，图6.1所示的树深度

8、为所示的树深度为4. 有序树：有序树：树中结点的各子树看成从左至右是有次序的树中结点的各子树看成从左至右是有次序的,例例 如如, 人类社会的族谱就是一个有序树。人类社会的族谱就是一个有序树。 无序树：无序树：树中结点的各子树没有次序的，孩子结点的顺树中结点的各子树没有次序的，孩子结点的顺 序可以调整。序可以调整。 森林：森林：m(m0)棵互不相交的树的集合。森林和树之棵互不相交的树的集合。森林和树之 间的联系是：一棵树取掉根，其子树构成一个间的联系是：一棵树取掉根，其子树构成一个 森林；同样，一个森林增加一个根结点成为树森林；同样，一个森林增加一个根结点成为树. 6.1.3 树的基本操作树的基

9、本操作 (1)initiate(t)：t树的初始化，包括建树。树的初始化，包括建树。 (2)root(t)：求：求t树的根。树的根。 (3)parent(t,x)：求：求t树中树中x结点的双亲结点。结点的双亲结点。 (4)child(t,x,i)：求：求t树中树中x结点的第结点的第i个孩子结点。个孩子结点。 (5)right_sibling(t,x)：求：求t树中树中x结点的右兄弟。结点的右兄弟。 (6)insert_child(y,i,x)：将根为：将根为x的子树置为的子树置为y结点的第结点的第i个孩子个孩子 (7)del_child(x,i)：删除：删除x结点的第结点的第i个孩子个孩子(整

10、个子树整个子树)。 (8)traverse(t)：遍历：遍历t树。按某个次序依次访问树中每一个树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。结点，并使每个结点都被访问且只被访问一次。 (9)clear(t)置空置空t树。树。 以上操作的具体实现，依赖于采用的存储结构。以上操作的具体实现，依赖于采用的存储结构。6.2 二叉树二叉树 6.2.1 定义及其操作定义及其操作 二叉树是另一种树形结构，它的特点是每一个结点至二叉树是另一种树形结构，它的特点是每一个结点至多只有两棵子树，并且，子树有左、右之分，其次序不能多只有两棵子树，并且，子树有左、右之分，其次序不能颠倒。颠倒

11、。 递归定义：递归定义：二叉树是二叉树是n(n0)个结点有限集，当个结点有限集，当n1时，时，有而且仅有一个结点为根结点，其余结点构成为有而且仅有一个结点为根结点，其余结点构成为2个互不相个互不相交的子集交的子集t1，t2，其中每一个子集又是一棵二叉树，分别，其中每一个子集又是一棵二叉树，分别称作为根结点的左子树和右子树。称作为根结点的左子树和右子树。 注意：注意：二叉树不是度为二叉树不是度为2的树，在度为的树，在度为2的树中，当一的树中，当一个结点的度为个结点的度为1时，其子树是不考虑序的；而在二叉树中，时，其子树是不考虑序的；而在二叉树中，当一个结点的度为当一个结点的度为1时，其子树要考虑

12、序，即：是作为双亲时，其子树要考虑序，即：是作为双亲的左子树还是作为双亲右子树。另外，树不允许为空树，的左子树还是作为双亲右子树。另外，树不允许为空树，但二叉树允许为空。但二叉树允许为空。 由二叉树的递归定义可知，二叉树有五种基本形态，由二叉树的递归定义可知，二叉树有五种基本形态，如图如图6.3所示。所示。 (a)空树空树 (b)仅有根仅有根 (c)右子树空右子树空 (c)左、右子树均在左、右子树均在 d)左子树空左子树空 图图6.3 二叉树的五种形态二叉树的五种形态 由二叉树的递归定义可知，二叉树有五种基本形态，如图由二叉树的递归定义可知，二叉树有五种基本形态，如图6.3所示。与树的基本操作

13、类似，二叉树有下面一些基本操作：所示。与树的基本操作类似，二叉树有下面一些基本操作： (l)lch(t,x)：求：求t树中树中x结点的左孩子。结点的左孩子。 (2)rch(t,x)：求：求t树中树中x结点的右孩子。结点的右孩子。 (3)lsibling(t,x)：求：求t树中树中x结点的左兄弟。结点的左兄弟。 (4)rsibling(t,x)：求：求t树中树中x结点的右兄弟。结点的右兄弟。其他操作与树相同。其他操作与树相同。 6.2.2 二叉树的性质二叉树的性质 二叉树具有下列重要性质。二叉树具有下列重要性质。 性质性质1：在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i

14、1)。 当当i=1时，只有一个根结点，时，只有一个根结点，2i-1=20=1，由于二叉树的，由于二叉树的每一个结点的度最多为每一个结点的度最多为2，因此，当，因此，当i2时，第时，第i层上的结点层上的结点数，最多为上一层的数，最多为上一层的2倍，所以，第倍，所以，第2层最多有层最多有21=21个个结点，第结点，第3层最多有层最多有221=22个，依次类推，第个，依次类推，第i层最多有层最多有22i-2=2i-1个。个。 性质性质2：深度为深度为k的二叉树至多有的二叉树至多有2k -1个结点个结点(k1)。 由性质由性质1可见，深度为可见，深度为k的二叉树的最大结点数为：的二叉树的最大结点数为：

15、 (第第i层上的最大结点数层上的最大结点数)=2i-1=2k-1 性质性质3：对任何一棵二叉树：对任何一棵二叉树t，如果其叶子结点数为，如果其叶子结点数为n0，度，度 为为2的结点数为的结点数为n2，则，则n0=n2+1。 在二叉树中，度为在二叉树中，度为1的结点为的结点为n1，这样树的结点数，这样树的结点数 n=n0+n1+n2 另外，除根结点外每个结点都有唯一的双亲结点指向该结另外，除根结点外每个结点都有唯一的双亲结点指向该结点，所以度为点，所以度为1的结点指向一个后续，而度为的结点指向一个后续，而度为2的结点指向两的结点指向两个后续，因此，二叉树结点数个后续，因此，二叉树结点数n=n1+

16、2*n2+1。 因为因为 n=n0+n1+n2=n1+2*n2+1 可得可得 n0=n2+1 下面介绍两种特殊的二叉树下面介绍两种特殊的二叉树。 满二叉树：满二叉树：一棵深度为一棵深度为k的二叉树，若其有的二叉树，若其有2k-1个结点，个结点，则称为满二叉树。在满二叉树中只有度为则称为满二叉树。在满二叉树中只有度为0和度为和度为2的的结点，并且在每一层上的结点数都是该层所能取结点结点，并且在每一层上的结点数都是该层所能取结点的最大值。如图的最大值。如图6.4(a)所示为一个深度为所示为一个深度为4的满二叉树。的满二叉树。 (a) 满二叉树 完全二叉树：完全二叉树：一个深度为一个深度为k的二叉树

17、，其结点数的二叉树，其结点数nn，则该结点不存在左孩子。，则该结点不存在左孩子。 (3)若若2i+1n，则，则i的右孩子是标号为的右孩子是标号为2i+1的结点；若的结点；若2i+1n，则该结点不存在右孩子。，则该结点不存在右孩子。 6.2.3 二叉树的存储结构二叉树的存储结构 (1)顺序存储结构顺序存储结构 满二叉树或完全二叉树顺序存储方式满二叉树或完全二叉树顺序存储方式: 即用一个数组即用一个数组按结点的标号顺序依次存放二叉树中的数据元素。图按结点的标号顺序依次存放二叉树中的数据元素。图6.4(b)是一棵完全二叉树，可以用一维数组是一棵完全二叉树，可以用一维数组bt12作为它的存储作为它的存

18、储结构，将二叉树中标号为结构，将二叉树中标号为i的结点的数据元素存放在分量的结点的数据元素存放在分量bti-1中，如图中，如图6.5(a)所示。存储位置暗藏了树中的关系，所示。存储位置暗藏了树中的关系，树的关系是通过完全二叉树的性质实现，例如树的关系是通过完全二叉树的性质实现，例如bt5的双亲的双亲结点标号是结点标号是k=trunc(i+1)/2=3，双亲结点所对应的数组分，双亲结点所对应的数组分量量btk-1=bt2。 1 2 3 4 5 6 7 8 9 10 11 12下标 0 1 2 3 4 5 6 7 8 9 10 11(a)完全二叉树 非完全二叉树非完全二叉树，也必须按完全二叉树的形

19、式存储，如，也必须按完全二叉树的形式存储，如图图6.5(b)所示，图中所示，图中“0”表示该结点不存在。对于畸表示该结点不存在。对于畸形二叉树形二叉树(树中大量存在度为树中大量存在度为1和度为和度为0的结点的结点)，采用，采用顺序存储方式，空间浪费较大。顺序存储方式，空间浪费较大。 1 1 2 2 3 3 4 4 5 5 0 0 0 0 0 0 0 0 6 6下标下标 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9(b)非完全二叉树非完全二叉树 (2)链式结构链式结构 由于二叉树是一种非线性结构，一般情况下采由于二叉树是一种非线性结构，一般情况下采用链式存储结构

20、。不同的结点结构，可以构成不同的用链式存储结构。不同的结点结构，可以构成不同的链式结构，常用的有以下两种。链式结构，常用的有以下两种。 (a)标准存储标准存储(也称为也称为“二叉链表二叉链表”)。 每一个结点有三个域，即：数据域、左指针、右指每一个结点有三个域，即：数据域、左指针、右指针。用针。用c语言描述如下：语言描述如下： struct bitnode int data; struct node *lch,*rch; typedef struct bitnode bitnode;(b)带逆存储带逆存储(也称为也称为“三叉链表三叉链表”)。 在二叉链表中，便于找到一个结点的左右孩子，在二叉链

21、表中，便于找到一个结点的左右孩子，但要找一个结点的双亲不方便，必须从树根开始遍历但要找一个结点的双亲不方便，必须从树根开始遍历整个二叉树，所以，在结点中增加一个指向双亲结点整个二叉树，所以，在结点中增加一个指向双亲结点的指针域。结点的结构如下：的指针域。结点的结构如下： struct tritnode int data; struct node *lch,*rch,*parent; ; typedef struct tritnode tritnode; 图图6.6是一个二叉树的两种链式存储结构图示。从图是一个二叉树的两种链式存储结构图示。从图中可知，二叉树的链式存储结构和逻辑结构是一致的。中可

22、知，二叉树的链式存储结构和逻辑结构是一致的。(a)二叉树逻辑结构 (b)二叉链表 (c)二叉链表 图6.6 二叉树的链式存储结构 6.3 遍历二叉树遍历二叉树 一个遍历二叉树的问题，即：按一定规律访问二叉树一个遍历二叉树的问题，即：按一定规律访问二叉树上的每个结点，且每个结点只能访问一次。这里上的每个结点，且每个结点只能访问一次。这里“访问访问”的含义很广，可以是对结点作各种处理。的含义很广，可以是对结点作各种处理。 在在线性结构线性结构中，因为除尾结点外，每一个中，因为除尾结点外，每一个结点结点都有都有唯唯一后续一后续，所以只要从首结点开始，每次取后继结点就可以，所以只要从首结点开始，每次取

23、后继结点就可以遍历线性结构中每一个结点。而二叉树是一种遍历线性结构中每一个结点。而二叉树是一种非线性结构非线性结构，每一个，每一个结结点可能有点可能有两个后续两个后续，因此需要寻找一种规律，因此需要寻找一种规律，将将层次形层次形的二叉树序列的二叉树序列转化转化为一个为一个线性线性序列。序列。 由递归定义可知，由递归定义可知，二叉树二叉树是由是由三个基本单元三个基本单元组成，即：组成，即：根结点根结点、左子树左子树和和右子树右子树。因此，若能依次遍历这三部分。因此，若能依次遍历这三部分，便是遍历了整个二叉树。若以，便是遍历了整个二叉树。若以(，t，r分别表示遍历左分别表示遍历左子树、访问根和遍历

24、右子树，则可有六种遍历方案：子树、访问根和遍历右子树，则可有六种遍历方案：tlr，ltr，lrt，trl，rtl，rlt。通常限定先遍历。通常限定先遍历左子树，后遍历右子树。所以，二叉树的遍历主要指前三左子树，后遍历右子树。所以，二叉树的遍历主要指前三种。种。6.3.1 二叉树遍历的递归算法二叉树遍历的递归算法(1)前序遍历前序遍历(tlr)递归算法递归算法 前序遍历前序遍历(也可以称为前序遍历也可以称为前序遍历)二叉树的操作定义为：二叉树的操作定义为： 若二叉树为空，则空操作若二叉树为空，则空操作(不作任何操作不作任何操作)；否则；否则 (1)访问根结点。访问根结点。 (2)前序访问左子树。

25、前序访问左子树。 (3)前序访问右子树。前序访问右子树。算法算法6.1 前序遍历二叉树的递归算法。前序遍历二叉树的递归算法。 void prev(bitnode *root) if(root!=null) printf(%d,root-data);/* 访问根结点访问根结点 */ prev(root-lch); prev(root-rch); (2)中序遍历中序遍历(ltr)递归算法递归算法 中序遍历二叉树的操作定义为：中序遍历二叉树的操作定义为： 若二叉树为空，则空操作若二叉树为空，则空操作(不作任何操作不作任何操作)；否则，；否则， (1)中序访问左子树。中序访问左子树。 (2)访问根结点

26、。访问根结点。 (3)中序访问右子树。中序访问右子树。由中序遍历的定义，可得到中序遍历二叉树的递归算法如下：由中序遍历的定义，可得到中序遍历二叉树的递归算法如下：算法算法6.2 中序遍历二叉树的递归算法。中序遍历二叉树的递归算法。 void mid(bitnode *root) if(root!=null) mid(root-lch); printf(%d,root-data);/* 访问根结点访问根结点 */ mid(root-rch); (3)后序遍历后序遍历(lrt)递归算法递归算法 后序遍历二叉树的操作定义为：后序遍历二叉树的操作定义为： 若二叉树为空，则空操作若二叉树为空，则空操作(

27、不作任何操作不作任何操作)；否则，；否则， (1)后序访问左子树；后序访问左子树； (2)后序访问右子树；后序访问右子树； (3)访问根结点；访问根结点；由后序遍历的定义，可得到后序遍历二叉树的递归算法如下。由后序遍历的定义，可得到后序遍历二叉树的递归算法如下。 算法算法6.3 后序遍历二叉树的递归算法。后序遍历二叉树的递归算法。 void pos(bitnode *root) if(root!=null) pos(root-lch); pos(root-rch); printf(%d,root-data);/* 访问根结点访问根结点 */ 图6.7 表达式(a*(b-c)+d/e)的二叉树

28、前序遍历前序遍历二叉树二叉树, 得到二叉树的前序序列为得到二叉树的前序序列为: +*a-bc/de中序遍历中序遍历二叉树，得到此树的中序序列为二叉树，得到此树的中序序列为: a*b-c+d/e后序遍历后序遍历二叉树，得到此树的后序序列为二叉树，得到此树的后序序列为: abc-*de/+ 递归算法逻辑清晰、易懂，但在实现时，由于函数调递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，所以效率不高用栈层层叠加，所以效率不高(每次函数调用，都要保存函每次函数调用，都要保存函数返回地址，实现参数传递，创建局部变量数返回地址，实现参数传递，创建局部变量)，下面讨论二，下面讨论二叉树遍历的非递归

29、算法。叉树遍历的非递归算法。 6.3.2 二叉树遍历的非递归算法二叉树遍历的非递归算法(1)前序非递归的算法前序非递归的算法 前序遍历的特点是：首先访问根，访问完根后访问左子前序遍历的特点是：首先访问根，访问完根后访问左子树，所以对每一个结点，在访问完该结点后，沿其左链访树，所以对每一个结点，在访问完该结点后，沿其左链访问下来，直到左链为空，这时，所有已被访问过的结点进问下来，直到左链为空，这时，所有已被访问过的结点进栈。然后结点出栈，对于每一个出栈结点，即表示该结点栈。然后结点出栈，对于每一个出栈结点，即表示该结点和其左子树已被访问结束，按照前序遍历的定义，应该访和其左子树已被访问结束，按照

30、前序遍历的定义，应该访问该结点的右子树。问该结点的右子树。 (1)当前指针指向根结点。当前指针指向根结点。 (2)打印当前结点，当前指针指向其左孩子并进栈，重打印当前结点，当前指针指向其左孩子并进栈，重复复(2)，直至左孩子为，直至左孩子为null。 (3)依次退栈，将当前指针指向右孩子。依次退栈，将当前指针指向右孩子。 (4)若栈非空或当前指针非若栈非空或当前指针非null，执行，执行2；否则结束。；否则结束。算法算法6.4 前序遍历二叉树的非递归算法。前序遍历二叉树的非递归算法。 void bit_preorder(bitnode *root) bitnode *p,*nodemax; i

31、nt top=0; p=root; do while(p!=null) printf(%d,p-data); nodetop=p; top+; p=p-lch; if(top0) top-; p=nodetop; p=p-rch; / /* * 凡是退栈的指针，其所指的结点及其左子树，都已遍历凡是退栈的指针，其所指的结点及其左子树，都已遍历 * */ / while(top0|p!=null); (2)中序非递归的算法中序非递归的算法 中序的特点是：首先访问左子树，所以对每一个结中序的特点是：首先访问左子树，所以对每一个结点，沿其左链走下来，直到左链为空，所有经过的结点点，沿其左链走下来，直到

32、左链为空，所有经过的结点进栈。然后结点出栈，对于每一个出栈结点，即表示该进栈。然后结点出栈，对于每一个出栈结点，即表示该结点的左子树已访问结束，按照中序遍历的定义，应该结点的左子树已访问结束，按照中序遍历的定义，应该访问该结点访问该结点(根根)，访问完该结点后，访问该结点的右子，访问完该结点后，访问该结点的右子树。树。 (1)当前指针指向根结点。当前指针指向根结点。 (2)当前结点进栈，当前指针指向其左孩子，重复当前结点进栈，当前指针指向其左孩子，重复(2)，直至左孩子为直至左孩子为null。 (3)依次退栈，退栈指针成为当前指针，打印当前结依次退栈，退栈指针成为当前指针，打印当前结点。点。

33、(4)将当前指针指向右孩子。将当前指针指向右孩子。 (5)若栈非空或当前指针非若栈非空或当前指针非null，执行，执行2；否则结束。；否则结束。算法算法6.5 中序遍历二叉树的非递归算法。 void bit_midorder(bitnode *root) bitnode *p,*nodemax; int top=0; p=root; do while(p!=null) nodetop=p; top+; p=p-lch; if(top0) top-; p=nodetop; printf(%d,p-data ); p=p-rch; /* 凡是退栈的指针，其所指的结点的左子树，都已遍历 */ whi

34、le(top0|p!=null); (3)后序非递归的算法后序非递归的算法 后序的特点是：在左、右子树都被访问结束后，才能访后序的特点是：在左、右子树都被访问结束后，才能访问根，所以，每一个出栈的结点都要判断是访问完左子树返问根，所以，每一个出栈的结点都要判断是访问完左子树返回根，还是访问完右子树返回根，一个结点只有在其右子树回根，还是访问完右子树返回根，一个结点只有在其右子树访问结束后，才能访问该结点。因此，需要对进栈的指针进访问结束后，才能访问该结点。因此，需要对进栈的指针进行补充说明，在这里引入了一个标志栈行补充说明，在这里引入了一个标志栈int flagmax。 （1)当前指针指向根结

35、点。当前指针指向根结点。 （2)当前结点进栈，所对应的标志栈为当前结点进栈，所对应的标志栈为0，当前指针指向其，当前指针指向其左孩子，重复左孩子，重复(2)，直至左孩子为，直至左孩子为null。 （3)判断栈顶元素的标志，若为判断栈顶元素的标志，若为1，则依次退栈，并打印退，则依次退栈，并打印退栈指针所指结点，直到标志为栈指针所指结点，直到标志为0。 （4)将栈顶元素的标志变为将栈顶元素的标志变为1，将当前指针为指向栈顶元素，将当前指针为指向栈顶元素的右孩子。的右孩子。 （5)若栈非空或当前指针非若栈非空或当前指针非null，执行，执行2；否则结束。；否则结束。 算法算法6.6 后序遍历二叉树

36、的非递归算法(#define left 0, #define right 1) void bit_postorder(bitnode *root) bitnode *p, *nodemax; int top,flagmax; p=root;top=0; /* top指向下一个进栈的位置 */ do while(p!=null) /* 结点非空，进栈，遍历左子树，直至最左下结点 */ nodetop=p; flagtop=left; top+; p=p-lch; while(top0 & flagtop-1=right) /* 栈顶元素的右子树已被遍历过，连续退栈并打印出栈元素 */ t

37、op-; p=nodetop; printf(%d,p-data); if(top0 & flagtop-1=left) /* 左子树已遍历，遍历右子树 */ p=nodetop-1; flagtop-1=right; p=p-rch; while(top0); 6.3.3 二叉树的层次遍历算法二叉树的层次遍历算法 按照层次遍历二叉树，是通过队列实现的。首先，将根的按照层次遍历二叉树，是通过队列实现的。首先，将根的结点入列；然后，每次判断队列是否为空；若队列不为空，则结点入列；然后，每次判断队列是否为空；若队列不为空，则取出队首元素所对应的结点，并将该不为空取出队首元素所对应的结点，并

38、将该不为空(null)的孩子结的孩子结点的指针入列；如若队列为空，则遍历结束。点的指针入列；如若队列为空，则遍历结束。算法算法6.7二叉树的层次遍历算法。二叉树的层次遍历算法。void travelbylevel(bitnode *root) bitnode *p; queue q; / /* * q q为指针队列为指针队列 * */ / queue_init(&q); / /* * 初始化队列初始化队列 * */ / queue_enter(&q, root); / /* * 将将rootroot进队列进队列 * */ / while( (p=queue_leave(&

39、;q) !=null) / /* * 出队列的值赋给出队列的值赋给p p * */ / printf(%c,p-data); if(p-lch) q_enter(&q, p-lch); if(p-rch) q_enter(&q, p-rch); 6.3.4 6.3.4 遍历算法的应用遍历算法的应用( (1) 1) 一种建树算法一种建树算法 已知树的结构，可以写出唯一的前序序列。但反之，则已知树的结构，可以写出唯一的前序序列。但反之，则不能建立唯一的树结构。这里推荐一种改进的前序遍历方法不能建立唯一的树结构。这里推荐一种改进的前序遍历方法，其遍历序列可以和树结构一一对应。该遍历方

40、法对空指针，其遍历序列可以和树结构一一对应。该遍历方法对空指针用字符用字符* *表示。于是表示。于是6.86.8图的前序序列为图的前序序列为abdabd* * *e e* * *c c* * * 。由。由于这样的序列和树结构一一对应，所以可以用此类序列作为于这样的序列和树结构一一对应，所以可以用此类序列作为建树的参数。建树的参数。图6.8 算法算法6.8 一种建立二叉树的算法。一种建立二叉树的算法。/ /* * s s中为带空指针记号的前序序列，中为带空指针记号的前序序列， * *pipi为下标在，函数调用中被改变为下标在，函数调用中被改变* */ /bitnode *bit_create(c

41、har s,int *pi) bitnode *root; char ch; ch=s*pi; *(pi)+; if(ch=*) return(null); / /* * 创建根结点创建根结点 * */ / root=(bitnode *)malloc(sizeof(bitnode); root-data=ch; / /* * 创建左子树，并将左子树的根指针赋给创建左子树，并将左子树的根指针赋给root-lchildroot-lchild * */ / root-lchild=bit_create(s, pi); / /* * * *pipi在调用中已被修改在调用中已被修改 * */ / /*

42、 * 创建右子树，并将右子树的根指针赋给创建右子树，并将右子树的根指针赋给root-lchildroot-lchild * */ / root-rchild=bit_create(s, pi); return(root);main() char s20=abd*e*c*; int i=0; bitnode *root; root=bit_create(s, &i)(2)释放二叉树结构释放二叉树结构 树结构是一种动态数据结构，它由一个个结点逐渐创建树结构是一种动态数据结构，它由一个个结点逐渐创建链接而成。当树结构处理完成后，有必要释放其所有结点。链接而成。当树结构处理完成后，有必要释放其

43、所有结点。遍历算法的本质是访问每个结点且每个结点只访问一次遍历算法的本质是访问每个结点且每个结点只访问一次。这和释放每个结点的要求非常相似，以下是利用后序遍历。这和释放每个结点的要求非常相似，以下是利用后序遍历算法的结构，释放二叉树中所有结点的存储结构的算法。算法的结构，释放二叉树中所有结点的存储结构的算法。算法算法6.9 释放二叉树中所有结点的存储结构的算法。释放二叉树中所有结点的存储结构的算法。void bit_free(bitnode *root) if(root!=null) bit_free(root-lchild); bit_free(root-rchild); free(root

44、); / /* * 将访问语句改为释放语句将访问语句改为释放语句 * */ / 需要注意的是，必须采用后序遍历算法的结构，而不需要注意的是，必须采用后序遍历算法的结构，而不能是前序或中序的遍历结构。因为只有在释放完左右子树能是前序或中序的遍历结构。因为只有在释放完左右子树之，才允许释放根结点，否则，程序的运行是不安全的。之，才允许释放根结点，否则，程序的运行是不安全的。(3)统计结点的个数统计结点的个数 统计结点个数是树结构的一个简单应用算法，同统计结点个数是树结构的一个简单应用算法，同样可以借鉴遍历算法的结构。只是将访问结点的语句改为样可以借鉴遍历算法的结构。只是将访问结点的语句改为加法运算

45、而已。加法运算而已。算法算法6.10 统计二叉树结点个数算法。统计二叉树结点个数算法。int bit_count(bitnode *root) int left,right; if(root=null) return(0); left= bit_count(root-lchild); / /* * 计算左子树的结点数计算左子树的结点数 * */ / right=bit_count(root-rchild); / /* * 计算右子树的结点数计算右子树的结点数 * */ / return(left+right+1); / /* * 计算结点总数计算结点总数 * */ / 算法算法6.11 统计二

46、叉树树叶结点的个数算法。统计二叉树树叶结点的个数算法。 统计结点个数算法的一个变形是：统计树叶结点统计结点个数算法的一个变形是：统计树叶结点的个数。这只需要在做加法运算前，先判断结点的度是的个数。这只需要在做加法运算前，先判断结点的度是否为否为0。int bit_leafcount(bitnode *root) int left,right; if(root=null) return(0); if(root-lchild=null & root-rchild=null) return(1); left = bit_leafcount(root-lchild); right= bit_l

47、eafcount(root-rchild); return(left+right);(4)求二叉树的深度求二叉树的深度 空二叉树的深度为空二叉树的深度为0，否则它的深度等于其根的左右，否则它的深度等于其根的左右子树的深度的最大值加子树的深度的最大值加1。显然这是一个递归定义，最简捷。显然这是一个递归定义，最简捷的实现方式是采用递归算法。同样，在此借鉴后序遍历算法的实现方式是采用递归算法。同样，在此借鉴后序遍历算法的结构，在遍历根的左右子树时，分别计算其深度，于是二的结构，在遍历根的左右子树时，分别计算其深度，于是二叉树的深度自然就求出了。叉树的深度自然就求出了。算法算法6.12 计算二叉树的深

48、度算法。计算二叉树的深度算法。int bit_depth(bitnode *root) int left,right; if(root=null) return(0); left = bit_depth(root-lchild); / /* * 计算左子树深度计算左子树深度 * */ / right= bit_depth(root-rchild); / /* * 计算右子树深度计算右子树深度 * */ / return(max(left,right)+1);(5)交换树中每个结点的左右子树交换树中每个结点的左右子树 若仅仅交换某个结点的左右子树，那就太简单了。要若仅仅交换某个结点的左右子树，那

49、就太简单了。要求对每个结点的左右子树都进行交换，这是加强对遍历算法求对每个结点的左右子树都进行交换，这是加强对遍历算法理解、应用的一个常用练习。以下采用后序遍历的算法理解、应用的一个常用练习。以下采用后序遍历的算法结，交换每个结点的左右子树。结，交换每个结点的左右子树。算法算法6.13 交换二叉树每个结点的左右子树算法。交换二叉树每个结点的左右子树算法。void bit_exchange(bitnode *root) bitnode *p; if(root=null) return; bit_exchange(root-lchild); / /* * 对左子树中的每个结点交换对左子树中的每个结

50、点交换 * */ / bit_exchange(root-rchild); / /* * 对右子树中的每个结点交换对右子树中的每个结点交换 * */ / / /* * 交换结点的左右孩子交换结点的左右孩子 * */ / p=root-lchild; root-lchild=root-rchild; root-rchild=p;(6)根据前序序列和中序序列构造二叉树结构根据前序序列和中序序列构造二叉树结构 我们已经知道二叉树结构和它的某个遍历序列不存我们已经知道二叉树结构和它的某个遍历序列不存在一一对应的关系，但若已知一个二叉树的前序序列和中在一一对应的关系，但若已知一个二叉树的前序序列和中序序

51、列，却一定可以唯一确定一个二叉树的结构。序序列，却一定可以唯一确定一个二叉树的结构。算法思路如下：算法思路如下：(a)因为前序序列的首元素为根元素，所以可以立即确定因为前序序列的首元素为根元素，所以可以立即确定根结点。根结点。(b)在中序序列中定位根结点的位置，必然将中序序列在中序序列中定位根结点的位置，必然将中序序列分为根元素和左、右子树三个部分。分为根元素和左、右子树三个部分。(c)由于已知左、右子树的元素个数，也自然可以将前序由于已知左、右子树的元素个数，也自然可以将前序序列分为根元素和左、右子树三个部分。序列分为根元素和左、右子树三个部分。(d)建树问题被细分为建左右子树的同类小问题。

52、在问建树问题被细分为建左右子树的同类小问题。在问题逐步分解细化过程中，若中序序列和前序序列都为空序题逐步分解细化过程中，若中序序列和前序序列都为空序列，则表明待建子树为空。列，则表明待建子树为空。示例：示例：设设pre0到到pre6为前序序列为前序序列abdecgh， mid0到到mid6为中序序列为中序序列dbeagch。其建树的步骤如下。其建树的步骤如下。0123456preabdecghmiddbeagch图图6.9确定根结点的数据为确定根结点的数据为pre0，即字符，即字符a。(2)在中序序列中定位字符在中序序列中定位字符a的位置，即下标为的位置，即下标为3，可以确定，可以确定mid0

53、到到mid2为为左子树左子树的中序序列的中序序列；mid4到到mid6为为右子右子树树的的中序序列中序序列。(3)根据中序序列与前序序列的对应关系，可知根据中序序列与前序序列的对应关系，可知pre1到到pre3为为左子树的前序序列左子树的前序序列；pre4到到pre6为为右子树的前序右子树的前序序列序列。(4)根据前序序列根据前序序列pre1到到pre3，中序序列，中序序列mid0到到mid2，构造左子树；根据前序序列构造左子树；根据前序序列pre4到到pre6，中序序列，中序序列mid4到到mid6，构造右子树。，构造右子树。 在程序中值得注意的是，在这种递归算法策略中，大在程序中值得注意的

54、是，在这种递归算法策略中，大小问题的描述，即函数的参数形式，必须具有完全相同的小问题的描述，即函数的参数形式，必须具有完全相同的形式。形式。算法算法6.14 由前序序列和中序序列构造二叉树结构算法。由前序序列和中序序列构造二叉树结构算法。/ /* * pre pre中存储前序序列，中存储前序序列，midmid中存储中序序列，中存储中序序列，n n为序列中元素为序列中元素的个数的个数 * */ / /* * pre_i pre_i为前序序列在为前序序列在prepre中的起始位置中的起始位置 * */ / /* * mid_i mid_i为前序序列在为前序序列在midmid中的起始位置中的起始位置

55、 * */ /bitnode *premid(char pre,char mid,int pre_i,int mid_i,int n) int i=0; bitnode *root; if(n=0) return(null); / /* * 最终解决方案：空序列建空树最终解决方案：空序列建空树 * */ / / /* * 在中序序列中定位根元素的位置在中序序列中定位根元素的位置 */ while(idata=prepre_i; / /* * 建左子树建左子树 * */ / root-lchild=premid(pre,mid, pre_i+1, mid_i, i); / /* * 建右子树建右

56、子树 * */ / root-rchild=premid(pre,mid, pre_i+i+1,mid_i+i+1,n-i-1) ; return(root); main() char pre= abdecgh , mid= dbeagch ; bitnode *root; root=premid(pre, mid, 0,0,7); 6.4 树和森林树和森林 6.4.1 树的存储结构树的存储结构 在大量的应用中，可以使用多种形式的存储在大量的应用中，可以使用多种形式的存储结构来表示树。在这里介绍三种表示树的方法，结构来表示树。在这里介绍三种表示树的方法，在具体应用中可以采用这三种表示方法，也可

57、以在具体应用中可以采用这三种表示方法，也可以定义其它存储结构，以满足应用的需求。采用某定义其它存储结构，以满足应用的需求。采用某种结构的理由来自实践的需要，即使数据完全一种结构的理由来自实践的需要，即使数据完全一样，因具体应用不同，所以结构就可能不同。样，因具体应用不同，所以结构就可能不同。(1)双亲表示法双亲表示法 采用一组连续空间存储树的结点，同时在每个结点采用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在该连续空间中位置中附设一个指示器指示其双亲结点在该连续空间中位置。若该连续空间用数组表示，则每一个结点的指示器值。若该连续空间用数组表示，则每一个结点的指示器值

58、是其双亲结点在数组中下标。用是其双亲结点在数组中下标。用c语言定义的树的双亲语言定义的树的双亲表示存储结构如下：表示存储结构如下：struct node int data; int parent; /* 双亲结点的下标双亲结点的下标 */ treemax;例如，图例如，图6.10所示为一棵树及其双亲表示的存储结构，其所示为一棵树及其双亲表示的存储结构，其中，中，tree0.parent存放树中结点数。存放树中结点数。 下标 dataparent 0 9 1 a 0 2 b 1 3 c 1 4 d 2 5 e 2 6 f 3 7 g 5 8 h 5 9 i 5图6.10 树的双亲表示法 在这种存

59、储结构中，利在这种存储结构中，利用每一个结点的双亲指示域，用每一个结点的双亲指示域，很容易找到每一个结点的双很容易找到每一个结点的双亲，同样找结点的祖先结点亲，同样找结点的祖先结点也非常便利。但要找某个结也非常便利。但要找某个结点的孩子或子孙结点，需遍点的孩子或子孙结点，需遍历整个数组历整个数组. (2)孩子表示法孩子表示法 将树中每个结点的将树中每个结点的孩子结点用一个单链表孩子结点用一个单链表(孩链表孩链表)表示，那么，一棵树有表示，那么，一棵树有n个结点个结点就有就有n个孩链表个孩链表(度为度为0的的结点，所对应的孩链表为空表结点，所对应的孩链表为空表)。这。这n个个孩链表孩链表的的头指

60、针头指针又又构成一个线性表构成一个线性表，用一个指针数组存储该线性表，这，用一个指针数组存储该线性表，这就构成了树的孩子表示法的存储结构。就构成了树的孩子表示法的存储结构。 如图如图6.11(a)所示为图所示为图6.10中树的孩子表示法的存储中树的孩子表示法的存储结构，在这种存储结构中，找一个结点的孩子十分方便。结构，在这种存储结构中，找一个结点的孩子十分方便。例如，要找结点例如，要找结点b的孩子，只要遍历结点的孩子，只要遍历结点b的孩链表，就的孩链表，就可以找到该结点的所有孩子。但要找一个结点的双亲就可以找到该结点的所有孩子。但要找一个结点的双亲就不方便，需要遍历整个结构。例如，要找结点不方便，需要遍历整个结构。例如，要找结点d的双亲的双亲结点，就要找到某