第第6 6章章 树树6.1树结构的定义和基本操作树结构的定义和基本操作 6.2二叉树二叉树6.3遍历二叉树遍历二叉树 6.4树和森林树和森林6.5树的应用树的应用习题习题 前面谈的基本上是前面谈的基本上是线性表结构线性表结构，线性表，线性表,栈、队列、串、一维数组，即使二维数组栈、队列、串、一维数组，即使二维数组(矩矩阵结构、十字类别阵结构、十字类别)也不过只是线性表的组合，也不过只是线性表的组合，即：除首元素和尾元素以外，每一个元素有即：除首元素和尾元素以外，每一个元素有唯一的前驱唯一的前驱和和后续后续元素。元素。 树形结构树形结构是一种重要的是一种重要的非线性结构非线性结构，讨，讨论的是论的是层次和分支关系层次和分支关系，即：除了有一个根，即：除了有一个根元素没有前驱以外，每一个元素都有元素没有前驱以外，每一个元素都有唯一的唯一的前驱元素前驱元素；另外，每一个元素；另外，每一个元素有零个或多个有零个或多个后继元素后继元素。例如，人类社会的族谱和各种社。例如，人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计会组织机构都可以用树来形象表示。树在计算机领域中也得到广泛应用。算机领域中也得到广泛应用。 6.1 树结构的定义和基本操作树结构的定义和基本操作 6.1.1 树的定义树的定义 递归定义：递归定义： 树树(tree)是是n(n0)个结点的有限集。在任意一棵树中：个结点的有限集。在任意一棵树中： (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的子树，且它们本身也是一棵树。如在的子树，且它们本身也是一棵树。如在T1中，中，B是该子树根，其余结点又构成两个互不相交子集，是该子树根，其余结点又构成两个互不相交子集，T11=E，K，L和和T12=F，T11和和T12都是根都是根B的子树，且的子树，且它们本身也是一棵树。它们本身也是一棵树。 图6.1 树的示例 上面是树的一个递归定义，树除了该递归定义外，还上面是树的一个递归定义，树除了该递归定义外，还有其它定义。如图有其它定义。如图6.2所示为图所示为图6.1中树的各种表示中树的各种表示.从图从图6.1的示例可以看出，的示例可以看出，树有两个特点：树有两个特点： (1) 树的根结点没有树的根结点没有前驱结点，其余结点有前驱结点，其余结点有且只有一个前驱结点。且只有一个前驱结点。 (2) 树结点可以有零树结点可以有零个或多个后继结点。个或多个后继结点。 树结构描述的是层树结构描述的是层次和分支关系。次和分支关系。 图6.2 树的其它三种表示方法 图图6.2(a)是以嵌套集合的形式表示是以嵌套集合的形式表示(任何两个集合，或不相交，任何两个集合，或不相交，或一个包含另一个或一个包含另一个)；图；图6.2(b)是以广义表的形式表示，根作为是以广义表的形式表示，根作为子树森林组成的表的名字写在表的左边；图子树森林组成的表的名字写在表的左边；图6.2(c)用的是凹入用的是凹入表示法。表示法。 6.1.2 树的常用术语树的常用术语 结点：结点：是包含一个数据元素和若干指向其子树的分支是包含一个数据元素和若干指向其子树的分支 (即关系即关系). 结点的度：结点的度：结点拥有的子树数。结点拥有的子树数。 叶子：叶子：度为度为0的结点。的结点。 分支结点：分支结点：度不为度不为0的结点。的结点。 树的度：树的度：树内各结点的度的最大值，图树内各结点的度的最大值，图6.1所示树是所示树是 一一 个个3叉树叉树. 孩子结点孩子结点(child)：结点的后继，结点子树的根结点。结点的后继，结点子树的根结点。双亲结点双亲结点(parent)：孩子结点的前驱。孩子结点的前驱。s是是f的孩子的孩子,则则f是是s的双的双亲亲. 兄弟结点兄弟结点(sibling)：同一个双亲的孩子之间互称为兄弟。同一个双亲的孩子之间互称为兄弟。 祖先结点：祖先结点：从根到该结点的所经过分支上的所有结点从根到该结点的所经过分支上的所有结点, 图图6.1树中树中L结点的祖先结点是结点的祖先结点是A，B，F。 子孙结点：子孙结点：以某结点为根的子树中任一结点都称为该结点以某结点为根的子树中任一结点都称为该结点 的子孙的子孙. 图图6.1树中树中D的子孙结点为的子孙结点为H，I，J，M.结点的层次：结点的层次：根是第根是第1层，依次为第层，依次为第2层层。 树的深度：树的深度：树中结点的最大层次，图树中结点的最大层次，图6.1所示的树深度为所示的树深度为4. 有序树：有序树：树中结点的各子树看成从左至右是有次序的树中结点的各子树看成从左至右是有次序的,例例 如如, 人类社会的族谱就是一个有序树。人类社会的族谱就是一个有序树。 无序树：无序树：树中结点的各子树没有次序的，孩子结点的顺树中结点的各子树没有次序的，孩子结点的顺 序可以调整。序可以调整。 森林：森林：m(m0)棵互不相交的树的集合。森林和树之棵互不相交的树的集合。森林和树之 间的联系是：一棵树取掉根，其子树构成一个间的联系是：一棵树取掉根，其子树构成一个 森林；同样，一个森林增加一个根结点成为树森林；同样，一个森林增加一个根结点成为树. 6.1.3 树的基本操作树的基本操作 (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个孩子个孩子(整个子树整个子树)。 (8)traverse(T)：遍历：遍历T树。按某个次序依次访问树中每一树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。个结点，并使每个结点都被访问且只被访问一次。 (9)clear(T) 置空置空T树。树。 以上操作的具体实现，依赖于采用的存储结构。以上操作的具体实现，依赖于采用的存储结构。6.2 二叉树二叉树 6.2.1 定义及其操作定义及其操作 二叉树是另一种树形结构，它的特点是每一个结点至二叉树是另一种树形结构，它的特点是每一个结点至多只有两棵子树，并且，子树有左、右之分，其次序不能多只有两棵子树，并且，子树有左、右之分，其次序不能颠倒。颠倒。 递归定义：递归定义：二叉树是二叉树是n(n0)个结点有限集，当个结点有限集，当n1时，时，有而且仅有一个结点为根结点，其余结点构成为有而且仅有一个结点为根结点，其余结点构成为2个互不相个互不相交的子集交的子集T1，T2，其中每一个子集又是一棵二叉树，分别，其中每一个子集又是一棵二叉树，分别称作为根结点的左子树和右子树。称作为根结点的左子树和右子树。 注意：注意：二叉树不是度为二叉树不是度为2的树，在度为的树，在度为2的树中，当一的树中，当一个结点的度为个结点的度为1时，其子树是不考虑序的；而在二叉树中，时，其子树是不考虑序的；而在二叉树中，当一个结点的度为当一个结点的度为1时，其子树要考虑序，即：是作为双亲时，其子树要考虑序，即：是作为双亲的左子树还是作为双亲右子树。另外，树不允许为空树，的左子树还是作为双亲右子树。另外，树不允许为空树，但二叉树允许为空。但二叉树允许为空。 由二叉树的递归定义可知，二叉树有五种基本形态，由二叉树的递归定义可知，二叉树有五种基本形态，如图如图6.3所示。所示。 (a)空树空树 (b)仅有根仅有根 (c)右子树空右子树空 (c)左、右子树均在左、右子树均在 d)左子树空左子树空 图图6.3 二叉树的五种形态二叉树的五种形态 由二叉树的递归定义可知，二叉树有五种基本形态，如图由二叉树的递归定义可知，二叉树有五种基本形态，如图6.3所示。与树的基本操作类似，二叉树有下面一些基本操作：所示。与树的基本操作类似，二叉树有下面一些基本操作： (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个结点个结点(i1)。 当当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的二叉树的最大结点数为：的二叉树的最大结点数为： (第第i层上的最大结点数层上的最大结点数)=2i-1=2k-1 性质性质3：对任何一棵二叉树：对任何一棵二叉树T，如果其叶子结点数为，如果其叶子结点数为n0，度，度 为为2的结点数为的结点数为n2，则，则n0=n2+1。 在二叉树中，度为在二叉树中，度为1的结点为的结点为n1，这样树的结点数，这样树的结点数 n=n0+n1+n2 另外，除根结点外每个结点都有唯一的双亲结点指向该结点，另外，除根结点外每个结点都有唯一的双亲结点指向该结点，所以度为所以度为1的结点指向一个后续，而度为的结点指向一个后续，而度为2的结点指向两个后的结点指向两个后续，因此，二叉树结点数续，因此，二叉树结点数n=n1+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的二叉树，其结点数的二叉树，其结点数nn，则该结点不存在左孩子。，则该结点不存在左孩子。 (3)若若2i+1n，则，则i的右孩子是标号为的右孩子是标号为2i+1的结点；若的结点；若2i+1n，则该结点不存在右孩子。，则该结点不存在右孩子。 6.2.3 二叉树的存储结构二叉树的存储结构 (1)顺序存储结构顺序存储结构 满二叉树或完全二叉树顺序存储方式满二叉树或完全二叉树顺序存储方式: 即用一个数组即用一个数组按结点的标号顺序依次存放二叉树中的数据元素。图按结点的标号顺序依次存放二叉树中的数据元素。图6.4(b)是一棵完全二叉树，可以用一维数组是一棵完全二叉树，可以用一维数组bt12作为它的作为它的存储结构，将二叉树中标号为存储结构，将二叉树中标号为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)完全二叉树 非完全二叉树非完全二叉树，也必须按完全二叉树的形式存储，如，也必须按完全二叉树的形式存储，如图图6.5(b)所示，图中所示，图中“0”表示该结点不存在。对于畸表示该结点不存在。对于畸形二叉树形二叉树(树中大量存在度为树中大量存在度为1和度为和度为0的结点的结点)，采用，采用顺序存储方式，空间浪费较大。顺序存储方式，空间浪费较大。 1 2 3 4 5 0 0 0 0 6下标 0 1 2 3 4 5 6 7 8 9(b)非完全二叉树非完全二叉树 (2)链式结构链式结构 由于二叉树是一种非线性结构，一般情况下采由于二叉树是一种非线性结构，一般情况下采用链式存储结构。不同的结点结构，可以构成不同的用链式存储结构。不同的结点结构，可以构成不同的链式结构，常用的有以下两种。链式结构，常用的有以下两种。 (a)标准存储标准存储(也称为也称为“二叉链表二叉链表”)。 每一个结点有三个域，即：数据域、左指针、右指每一个结点有三个域，即：数据域、左指针、右指针。用针。用C语言描述如下：语言描述如下： struct bitnode int data; struct node *lch,*rch; typedef struct bitnode BiTNode;(b)带逆存储带逆存储(也称为也称为“三叉链表三叉链表”)。 在二叉链表中，便于找到一个结点的左右孩子，在二叉链表中，便于找到一个结点的左右孩子，但要找一个结点的双亲不方便，必须从树根开始遍历整但要找一个结点的双亲不方便，必须从树根开始遍历整个二叉树，所以，在结点中增加一个指向双亲结点的指个二叉树，所以，在结点中增加一个指向双亲结点的指针域。结点的结构如下：针域。结点的结构如下： struct tritnode int data; struct node *lch,*rch,*parent; ; typedef struct tritnode TriTnode; 图图6.6是一个二叉树的两种链式存储结构图示。从图中是一个二叉树的两种链式存储结构图示。从图中可知，二叉树的链式存储结构和逻辑结构是一致的。可知，二叉树的链式存储结构和逻辑结构是一致的。(a)二叉树逻辑结构 (b)二叉链表 (c)二叉链表 图6.6 二叉树的链式存储结构 6.3 遍历二叉树遍历二叉树 一个遍历二叉树的问题，即：按一定规律访问二叉树一个遍历二叉树的问题，即：按一定规律访问二叉树上的每个结点，且每个结点只能访问一次。这里上的每个结点，且每个结点只能访问一次。这里“访问访问”的含义很广，可以是对结点作各种处理。的含义很广，可以是对结点作各种处理。 在在线性结构线性结构中，因为除尾结点外，每一个中，因为除尾结点外，每一个结点结点都有都有唯唯一后续一后续，所以只要从首结点开始，每次取后继结点就可以，所以只要从首结点开始，每次取后继结点就可以遍历线性结构中每一个结点。而二叉树是一种遍历线性结构中每一个结点。而二叉树是一种非线性结构非线性结构，每一个每一个结结点可能有点可能有两个后续两个后续，因此需要寻找一种规律，将，因此需要寻找一种规律，将层次形层次形的二叉树序列的二叉树序列转化转化为一个为一个线性线性序列。序列。 由递归定义可知，由递归定义可知，二叉树二叉树是由是由三个基本单元三个基本单元组成，即：组成，即：根结点根结点、左子树左子树和和右子树右子树。因此，若能依次遍历这三部分，。因此，若能依次遍历这三部分，便是遍历了整个二叉树。若以便是遍历了整个二叉树。若以(，T，R分别表示遍历左子分别表示遍历左子树、访问根和遍历右子树，则可有六种遍历方案：树、访问根和遍历右子树，则可有六种遍历方案：TLR，LTR，LRT，TRL，RTL，RLT。通常限定先遍历左子树，。通常限定先遍历左子树，后遍历右子树。所以，二叉树的遍历主要指前三种。后遍历右子树。所以，二叉树的遍历主要指前三种。6.3.1 二叉树遍历的递归算法二叉树遍历的递归算法(1)前序遍历前序遍历(TLR)递归算法递归算法 前序遍历前序遍历(也可以称为前序遍历也可以称为前序遍历)二叉树的操作定义为：二叉树的操作定义为： 若二叉树为空，则空操作若二叉树为空，则空操作(不作任何操作不作任何操作)；否则；否则 (1)访问根结点。访问根结点。 (2)前序访问左子树。前序访问左子树。 (3)前序访问右子树。前序访问右子树。算法算法6.1 前序遍历二叉树的递归算法。前序遍历二叉树的递归算法。 void prev(BiTNode *root) if(root!=NULL) printf(%d,root-data);/* 访问根结点访问根结点 */ prev(root-lch); prev(root-rch); (2)中序遍历中序遍历(LTR)递归算法递归算法 中序遍历二叉树的操作定义为：中序遍历二叉树的操作定义为： 若二叉树为空，则空操作若二叉树为空，则空操作(不作任何操作不作任何操作)；否则，；否则， (1)中序访问左子树。中序访问左子树。 (2)访问根结点。访问根结点。 (3)中序访问右子树。中序访问右子树。由中序遍历的定义，可得到中序遍历二叉树的递归算法如下：由中序遍历的定义，可得到中序遍历二叉树的递归算法如下：算法算法6.2 中序遍历二叉树的递归算法。中序遍历二叉树的递归算法。 void mid(BiTNode *root) if(root!=NULL) mid(root-lch); printf(%d,root-data);/* 访问根结点访问根结点 */ mid(root-rch); (3)后序遍历后序遍历(LRT)递归算法递归算法 后序遍历二叉树的操作定义为：后序遍历二叉树的操作定义为： 若二叉树为空，则空操作若二叉树为空，则空操作(不作任何操作不作任何操作)；否则，；否则， (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)的二叉树 前序遍历前序遍历二叉树二叉树, 得到二叉树的前序序列为得到二叉树的前序序列为: +*a-bc/de中序遍历中序遍历二叉树，得到此树的中序序列为二叉树，得到此树的中序序列为: a*b-c+d/e后序遍历后序遍历二叉树，得到此树的后序序列为二叉树，得到此树的后序序列为: abc-*de/+ 递归算法逻辑清晰、易懂，但在实现时，由于函数调递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，所以效率不高用栈层层叠加，所以效率不高(每次函数调用，都要保存函每次函数调用，都要保存函数返回地址，实现参数传递，创建局部变量数返回地址，实现参数传递，创建局部变量)，下面讨论二，下面讨论二叉树遍历的非递归算法。叉树遍历的非递归算法。 6.3.2 二叉树遍历的非递归算法二叉树遍历的非递归算法(1)前序非递归的算法前序非递归的算法 前序遍历的特点是：首先访问根，访问完根后访问左子前序遍历的特点是：首先访问根，访问完根后访问左子树，所以对每一个结点，在访问完该结点后，沿其左链访树，所以对每一个结点，在访问完该结点后，沿其左链访问下来，直到左链为空，这时，所有已被访问过的结点进问下来，直到左链为空，这时，所有已被访问过的结点进栈。然后结点出栈，对于每一个出栈结点，即表示该结点栈。然后结点出栈，对于每一个出栈结点，即表示该结点和其左子树已被访问结束，按照前序遍历的定义，应该访和其左子树已被访问结束，按照前序遍历的定义，应该访问该结点的右子树。问该结点的右子树。 (1)当前指针指向根结点。当前指针指向根结点。 (2)打印当前结点，当前指针指向其左孩子并进栈，重打印当前结点，当前指针指向其左孩子并进栈，重复复(2)，直至左孩子为，直至左孩子为NULL。 (3)依次退栈，将当前指针指向右孩子。依次退栈，将当前指针指向右孩子。 (4)若栈非空或当前指针非若栈非空或当前指针非NULL，执行，执行2；否则结束。；否则结束。算法算法6.4 前序遍历二叉树的非递归算法。前序遍历二叉树的非递归算法。 void BiT_PreOrder(BiTNode *root) BiTNode *p,*nodeMAX; int 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)中序非递归的算法中序非递归的算法 中序的特点是：首先访问左子树，所以对每一个结中序的特点是：首先访问左子树，所以对每一个结点，沿其左链走下来，直到左链为空，所有经过的结点点，沿其左链走下来，直到左链为空，所有经过的结点进栈。然后结点出栈，对于每一个出栈结点，即表示该进栈。然后结点出栈，对于每一个出栈结点，即表示该结点的左子树已访问结束，按照中序遍历的定义，应该结点的左子树已访问结束，按照中序遍历的定义，应该访问该结点访问该结点(根根)，访问完该结点后，访问该结点的右子，访问完该结点后，访问该结点的右子树。树。 (1)当前指针指向根结点。当前指针指向根结点。 (2)当前结点进栈，当前指针指向其左孩子，重复当前结点进栈，当前指针指向其左孩子，重复(2)，直至左孩子为，直至左孩子为NULL。 (3)依次退栈，退栈指针成为当前指针，打印当前结依次退栈，退栈指针成为当前指针，打印当前结点。点。 (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; /* 凡是退栈的指针，其所指的结点的左子树，都已遍历 */ while(top0|p!=NULL); (3)后序非递归的算法后序非递归的算法 后序的特点是：在左、右子树都被访问结束后，才能访后序的特点是：在左、右子树都被访问结束后，才能访问根，所以，每一个出栈的结点都要判断是访问完左子树返问根，所以，每一个出栈的结点都要判断是访问完左子树返回根，还是访问完右子树返回根，一个结点只有在其右子树回根，还是访问完右子树返回根，一个结点只有在其右子树访问结束后，才能访问该结点。因此，需要对进栈的指针进访问结束后，才能访问该结点。因此，需要对进栈的指针进行补充说明，在这里引入了一个标志栈行补充说明，在这里引入了一个标志栈int flagMAX。 （1)当前指针指向根结点。当前指针指向根结点。 （2)当前结点进栈，所对应的标志栈为当前结点进栈，所对应的标志栈为0，当前指针指向其，当前指针指向其左孩子，重复左孩子，重复(2)，直至左孩子为，直至左孩子为NULL。 （3)判断栈顶元素的标志，若为判断栈顶元素的标志，若为1，则依次退栈，并打印退，则依次退栈，并打印退栈指针所指结点，直到标志为栈指针所指结点，直到标志为0。 （4)将栈顶元素的标志变为将栈顶元素的标志变为1，将当前指针为指向栈顶元素，将当前指针为指向栈顶元素的右孩子。的右孩子。 （5)若栈非空或当前指针非若栈非空或当前指针非NULL，执行，执行2；否则结束。；否则结束。 算法算法6.6 后序遍历二叉树的非递归算法(#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) /* 栈顶元素的右子树已被遍历过，连续退栈并打印出栈元素 */ top-; 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 二叉树的层次遍历算法二叉树的层次遍历算法 按照层次遍历二叉树，是通过队列实现的。首先，将根的按照层次遍历二叉树，是通过队列实现的。首先，将根的结点入列；然后，每次判断队列是否为空；若队列不为空，则结点入列；然后，每次判断队列是否为空；若队列不为空，则取出队首元素所对应的结点，并将该不为空取出队首元素所对应的结点，并将该不为空(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(&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) 一种建一种建树算法算法 已知已知树的的结构，可以写出唯一的前序序列。但反之，构，可以写出唯一的前序序列。但反之，则不能建立唯一的不能建立唯一的树结构。构。这里推荐一种改里推荐一种改进的前序遍的前序遍历方法，方法，其遍其遍历序列可以和序列可以和树结构一一构一一对应。该遍遍历方法方法对空指空指针用用字符字符* *表示。于是表示。于是6.86.8图的前序序列的前序序列为ABD*E*C*ABD*E*C*。由。由于于这样的序列和的序列和树结构一一构一一对应，所以可以用此，所以可以用此类序列作序列作为建建树的参数。的参数。 图6.8图6.8 算法算法6.8 一种建立二叉树的算法。一种建立二叉树的算法。/* s/* s中为带空指针记号的前序序列，中为带空指针记号的前序序列， * *pipi为下标在，函数调用中被改变为下标在，函数调用中被改变* */ /BiTNode *BiT_Create(char s,int *pi) BiTNode *root; char ch; ch=s*pi; *(pi)+; if(ch=*) return(NULL); /* /* 创建根结点创建根结点 * */ / root=(BiTNode *)malloc(sizeof(BiTNode); root-data=ch; /* /* 创建左子树，并将左子树的根指针赋给创建左子树，并将左子树的根指针赋给root-root-lchildlchild */ */ root-lchild=BiT_Create(s, pi); /* *pi/* *pi在调用中已被修改在调用中已被修改 * */ /* /* 创建右子树，并将右子树的根指针赋给创建右子树，并将右子树的根指针赋给root-root-lchildlchild */ */ 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)释放二叉树结构释放二叉树结构 树结构是一种动态数据结构，它由一个个结点逐渐创建树结构是一种动态数据结构，它由一个个结点逐渐创建链接而成。当树结构处理完成后，有必要释放其所有结点。链接而成。当树结构处理完成后，有必要释放其所有结点。遍历算法的本质是访问每个结点且每个结点只访问一次。遍历算法的本质是访问每个结点且每个结点只访问一次。这和释放每个结点的要求非常相似，以下是利用后序遍历算这和释放每个结点的要求非常相似，以下是利用后序遍历算法的结构，释放二叉树中所有结点的存储结构的算法。法的结构，释放二叉树中所有结点的存储结构的算法。算法算法6.9 释放二叉树中所有结点的存储结构的算法。释放二叉树中所有结点的存储结构的算法。void BiT_Free(BiTNode *root) if(root!=NULL) BiT_Free(root-lchild); BiT_Free(root-rchild); free(root); /* /* 将访问语句改为释放语句将访问语句改为释放语句 * */ / 需要注意的是，必须采用后序遍历算法的结构，而不需要注意的是，必须采用后序遍历算法的结构，而不能是前序或中序的遍历结构。因为只有在释放完左右子树之，能是前序或中序的遍历结构。因为只有在释放完左右子树之，才允许释放根结点，否则，程序的运行是不安全的。才允许释放根结点，否则，程序的运行是不安全的。(3)统计结点的个数统计结点的个数 统计结点个数是树结构的一个简单应用算法，同样统计结点个数是树结构的一个简单应用算法，同样可以借鉴遍历算法的结构。只是将访问结点的语句改为加可以借鉴遍历算法的结构。只是将访问结点的语句改为加法运算而已。法运算而已。算法算法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 统计二叉树树叶结点的个数算法。统计二叉树树叶结点的个数算法。 统计结点个数算法的一个变形是：统计树叶结点统计结点个数算法的一个变形是：统计树叶结点的个数。这只需要在做加法运算前，先判断结点的度是的个数。这只需要在做加法运算前，先判断结点的度是否为否为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_LeafCount(root-rchild); return(left+right);(4)求二叉树的深度求二叉树的深度 空二叉树的深度为空二叉树的深度为0，否则它的深度等于其根的左右，否则它的深度等于其根的左右子树的深度的最大值加子树的深度的最大值加1。显然这是一个递归定义，最简捷的。显然这是一个递归定义，最简捷的实现方式是采用递归算法。同样，在此借鉴后序遍历算法的实现方式是采用递归算法。同样，在此借鉴后序遍历算法的结构，在遍历根的左右子树时，分别计算其深度，于是二叉结构，在遍历根的左右子树时，分别计算其深度，于是二叉树的深度自然就求出了。树的深度自然就求出了。算法算法6.12 计算二叉树的深度算法。计算二叉树的深度算法。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)交换树中每个结点的左右子树交换树中每个结点的左右子树 若仅仅交换某个结点的左右子树，那就太简单了。要若仅仅交换某个结点的左右子树，那就太简单了。要求对每个结点的左右子树都进行交换，这是加强对遍历算法求对每个结点的左右子树都进行交换，这是加强对遍历算法理解、应用的一个常用练习。以下采用后序遍历的算法结，理解、应用的一个常用练习。以下采用后序遍历的算法结，交换每个结点的左右子树。交换每个结点的左右子树。算法算法6.13 交换二叉树每个结点的左右子树算法。交换二叉树每个结点的左右子树算法。void BiT_Exchange(BiTNode *root) BiTNode *p; if(root=NULL) return; BiT_Exchange(root-lchild); /* /* 对左子树中的每个结点交换对左子树中的每个结点交换 * */ / BiT_Exchange(root-rchild); /* /* 对右子树中的每个结点交换对右子树中的每个结点交换 * */ / /* /* 交换结点的左右孩子交换结点的左右孩子 * */ / p=root-lchild; root-lchild=root-rchild; root-rchild=p;(6)根据前序序列和中序序列构造二叉树结构根据前序序列和中序序列构造二叉树结构 我们已经知道二叉树结构和它的某个遍历序列不存我们已经知道二叉树结构和它的某个遍历序列不存在一一对应的关系，但若已知一个二叉树的前序序列和中在一一对应的关系，但若已知一个二叉树的前序序列和中序序列，却一定可以唯一确定一个二叉树的结构。序序列，却一定可以唯一确定一个二叉树的结构。算法思路如下：算法思路如下：(a)因为前序序列的首元素为根元素，所以可以立即确因为前序序列的首元素为根元素，所以可以立即确定根结点。定根结点。(b)在中序序列中定位根结点的位置，必然将中序序列在中序序列中定位根结点的位置，必然将中序序列分为根元素和左、右子树三个部分。分为根元素和左、右子树三个部分。(c)由于已知左、右子树的元素个数，也自然可以将前由于已知左、右子树的元素个数，也自然可以将前序序列分为根元素和左、右子树三个部分。序序列分为根元素和左、右子树三个部分。(d)建树问题被细分为建左右子树的同类小问题。在问建树问题被细分为建左右子树的同类小问题。在问题逐步分解细化过程中，若中序序列和前序序列都为空序题逐步分解细化过程中，若中序序列和前序序列都为空序列，则表明待建子树为空。列，则表明待建子树为空。示例：示例：设设pre0到到pre6为前序序列为前序序列abdecgh， mid0到到mid6为中序序列为中序序列dbeagch。其建树的步骤如下。其建树的步骤如下。0123456preabdecghmiddbeagch图6.9确定根结点的数据为确定根结点的数据为pre0，即字符，即字符a。(2)在中序序列中定位字符在中序序列中定位字符a的位置，即下标为的位置，即下标为3，可以确定，可以确定mid0到到mid2为为左子树左子树的中序序列的中序序列；mid4到到mid6为为右子右子树树的的中序序列中序序列。(3)根据中序序列与前序序列的对应关系，可知根据中序序列与前序序列的对应关系，可知pre1到到pre3为为左子树的前序序列左子树的前序序列；pre4到到pre6为为右子树的前序序右子树的前序序列列。(4)根据前序序列根据前序序列pre1到到pre3，中序序列，中序序列mid0到到mid2，构造左子树；根据前序序列，构造左子树；根据前序序列pre4到到pre6，中序序列，中序序列mid4到到mid6，构造右子树。，构造右子树。 在程序中值得注意的是，在这种递归算法策略中，大小在程序中值得注意的是，在这种递归算法策略中，大小问题的描述，即函数的参数形式，必须具有完全相同的形式。问题的描述，即函数的参数形式，必须具有完全相同的形式。算法算法6.14 由前序序列和中序序列构造二叉树结构算法。由前序序列和中序序列构造二叉树结构算法。/* pre/* pre中存储前序序列，中存储前序序列，midmid中存储中序序列，中存储中序序列，n n为序列中元素为序列中元素的个数的个数 * */ /* /* pre_ipre_i为前序序列在为前序序列在prepre中的起始位置中的起始位置 * */ /* /* mid_imid_i为前序序列在为前序序列在midmid中的起始位置中的起始位置 * */ /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); /* /* 建右子树建右子树 * */ / 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 树的存储结构树的存储结构 在大量的应用中，可以使用多种形式的存储在大量的应用中，可以使用多种形式的存储结构来表示树。在这里介绍三种表示树的方法，结构来表示树。在这里介绍三种表示树的方法，在具体应用中可以采用这三种表示方法，也可以在具体应用中可以采用这三种表示方法，也可以定义其它存储结构，以满足应用的需求。采用某定义其它存储结构，以满足应用的需求。采用某种结构的理由来自实践的需要，即使数据完全一种结构的理由来自实践的需要，即使数据完全一样，因具体应用不同，所以结构就可能不同。样，因具体应用不同，所以结构就可能不同。(1)双亲表示法双亲表示法 采用一组连续空间存储树的结点，同时在每个结点采用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在该连续空间中位置。中附设一个指示器指示其双亲结点在该连续空间中位置。若该连续空间用数组表示，则每一个结点的指示器值是若该连续空间用数组表示，则每一个结点的指示器值是其双亲结点在数组中下标。用其双亲结点在数组中下标。用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 树的双亲表示法 在这种存储结构中，利在这种存储结构中，利用每一个结点的双亲指示域，用每一个结点的双亲指示域，很容易找到每一个结点的双很容易找到每一个结点的双亲，同样找结点的祖先结点亲，同样找结点的祖先结点也非常便利。但要找某个结也非常便利。但要找某个结点的孩子或子孙结点，需遍点的孩子或子孙结点，需遍历整个数组历整个数组. (2)孩子表示法孩子表示法 将树中每个结点的将树中每个结点的孩子结点用一个单链表孩子结点用一个单链表(孩链表孩链表)表示，那么，一棵树有表示，那么，一棵树有n个结点个结点就有就有n个孩链表个孩链表(度为度为0的的结点，所对应的孩链表为空表结点，所对应的孩链表为空表)。这。这n个个孩链表孩链表的的头指针头指针又又构成一个线性表构成一个线性表，用一个指针数组存储该线性表，这，用一个指针数组存储该线性表，这就构成了树的孩子表示法的存储结构。就构成了树的孩子表示法的存储结构。 如图如图6.11(a)所示为图所示为图6.10中树的孩子表示法的存储中树的孩子表示法的存储结构，在这种存储结构中，找一个结点的孩子十分方便。结构，在这种存储结构中，找一个结点的孩子十分方便。例如，要找结点例如，要找结点B的孩子，只要遍历结点的孩子，只要遍历结点B的孩链表，就的孩链表，就可以找到该结点的所有孩子。但要找一个结点的双亲就可以找到该结点的所有孩子。但要找一个结点的双亲就不方便，需要遍历整个结构。例如，要找结点不方便，需要遍历整个结构。例如，要找结点D的双亲的双亲结点，就要找到某个结点的孩链表中有结点结点，就要找到某个结点的孩链表中有结点D，该结点，该结点就是就是D的双亲，在这里结点的双亲，在这里结点B的孩链表中包含了的孩链表中包含了D结点的结点的位置，所以，位置，所以，B是是D的双亲结点。的双亲结点。 图6.11 图6.10中树的孩子表示法 为了便于查找结点的双亲，将树的双亲表示法和孩子表为了便于查找结点的双亲，将树的双亲表示法和孩子表示法结合起来，就有了树的双亲孩子表示法，如图示法结合起来，就有了树的双亲孩子表示法，如图6.11(b)所所示就是树的双亲孩子表示法示就是树的双亲孩子表示法存储结构存储结构示意图。示意图。 这种结构用这种结构用C语言描述如下：语言描述如下： struct node int pos; /* 结点在数组中下标结点在数组中下标 */ struct node *link; ； struct t_node char data; int parent; struct node *first_link; /* 孩子链表的头指针孩子链表的头指针 */ treeMAX;其中，其中，tree0.parent用来存放树中结点数。用来存放树中结点数。(3)孩子兄弟表示法孩子兄弟表示法 又称为二叉树表示法，也称又称为二叉树表示法，也称为二叉链表表示法，即：以二叉链为二叉链表表示法，即：以二叉链表作为树的存储结构。链表中结点表作为树的存储结构。链表中结点的两个指针域分别指向该结点的第的两个指针域分别指向该结点的第一个孩子结点和右边下一个兄弟结一个孩子结点和右边下一个兄弟结点，分别命名为点，分别命名为son域和域和brother域。域。 struct node int data; struct node *son; /* /* 第第1 1个孩子个孩子 * */ / struct node *brother; /* /* 下一下一个兄弟个兄弟 * */ / ； 图图6.12 图图6.10中树的二叉链表表示法中树的二叉链表表示法图图6.12所示为图所示为图6.10中树的中树的孩子兄弟链表的存储结构。孩子兄弟链表的存储结构。在这种存储结构中，找一在这种存储结构中，找一个结点的孩子十分方便。个结点的孩子十分方便。 6.4.2 树与二叉树的转换树与二叉树的转换 由于二叉树和树都可以用二叉链表存储，因此，可从由于二叉树和树都可以用二叉链表存储，因此，可从树的孩子兄弟链表中，导出树与二叉树之间的一个对应关树的孩子兄弟链表中，导出树与二叉树之间的一个对应关系。也就是说，可以找到唯一的二叉树与之对应。从物理系。也就是说，可以找到唯一的二叉树与之对应。从物理(存储存储)结构来看，它们的二叉链表是相同的。只是解释不结构来看，它们的二叉链表是相同的。只是解释不同而已。同而已。 例如，图例如，图6.12所示为图所示为图6.10中树的孩子兄弟链表中树的孩子兄弟链表的存储结构，表中结点的两个指针域的存储结构，表中结点的两个指针域son域和域和brother域解域解释为：指向该结点的第一个孩子结点和下一个兄弟结点。释为：指向该结点的第一个孩子结点和下一个兄弟结点。但也可以看成是将图但也可以看成是将图6.10中树转换成的二叉树的存储结构。中树转换成的二叉树的存储结构。这时，表中结点的两个指针域这时，表中结点的两个指针域son域和域和brother域就应解释域就应解释为：指向该结点左孩子和右孩子。为：指向该结点左孩子和右孩子。 所以，树与二叉树之间转换和树的二叉链表表示法所所以，树与二叉树之间转换和树的二叉链表表示法所用的方法相同。用的方法相同。6.4.3 森林与二叉树的转换森林与二叉树的转换(1)森林转换为二叉树森林转换为二叉树 从树的二叉链表表示的定义可知，一棵与树对应的二从树的二叉链表表示的定义可知，一棵与树对应的二叉树，其叉树，其右子树必为空右子树必为空。所以，只要将森林中。所以，只要将森林中所有树的根所有树的根结点视为兄弟结点视为兄弟，即将各个树转换为二叉树；再按森林中树，即将各个树转换为二叉树；再按森林中树的次序，依次将后一个树作为前一棵树的右子树，并将第的次序，依次将后一个树作为前一棵树的右子树，并将第一棵树的根作为目标二叉树树根，就可以将一个森林转换一棵树的根作为目标二叉树树根，就可以将一个森林转换成二叉树。成二叉树。 转换规则定义：转换规则定义： 若若F=T1,T2,Tn是森林，可按以下规则转成一棵二叉是森林，可按以下规则转成一棵二叉树树B(F)=root,LB,RB： (1)若若F为空，即为空，即n=0，则，则B(F)为空树。为空树。 (2)若若F非空，即非空，即n0，则，则B(F)的根是的根是T1的根，其左子树为的根，其左子树为LB是从是从T1根结点的子树森林根结点的子树森林F1=T11,T12,T1m转换而转换而成的二叉树；其右子树成的二叉树；其右子树RB是从除是从除T1外的森林外的森林F=(T2,Tn)转换而成的二叉树。转换而成的二叉树。 图图6.13 森林与二叉树的对应关系示例森林与二叉树的对应关系示例 (2)二二叉树还原为森林叉树还原为森林 转换规则定义：转换规则定义： 若若B=(root,LB,RB)是一棵二叉树，可按以下规则转换为是一棵二叉树，可按以下规则转换为森林森林F=T1,T2,Tn： (1)若若B为空，则为空，则B(F)为空树。为空树。 (2)若若B非空，则非空，则F中第一棵树中第一棵树T1的根是二叉树的根；的根是二叉树的根；T1中根结点的子森林中根结点的子森林F1是由是由B的左子树的左子树LB转换而成的森林；转换而成的森林；F中除中除T1之外其余树组成的森林之外其余树组成的森林F =T2,T3,Tm是由是由B(F)的右子树的右子树RB转换而成。转换而成。 森林与目标二叉树之间有一一对应的关系。所以，对森森林与目标二叉树之间有一一对应的关系。所以，对森林的操作也可以在二叉树的结构上进行。林的操作也可以在二叉树的结构上进行。回回 顾顾树和森林树和森林一、树的存储结构一、树的存储结构 1. 双亲表示法双亲表示法 2. 孩子表示法孩子表示法 3. 孩子兄弟表示法孩子兄弟表示法二、树和二叉树的转换二、树和二叉树的转换三、森林和二叉树的转换三、森林和二叉树的转换四、二叉树转换为树或森林四、二叉树转换为树或森林6.5 树的应用树的应用 6.5.1 二叉排序树二叉排序树 6.5.2 哈夫曼树哈夫曼树6.5.1 二叉排序树二叉排序树1、二、二叉排序树的定义叉排序树的定义 二叉排序树，是一种很有用的、特殊的二叉树，它的二叉排序树，是一种很有用的、特殊的二叉树，它的每一个结点每一个结点数据中都数据中都有有一个一个关键值关键值，并有如下，并有如下性质：性质：对于对于每个结点，如果其左子树非空，则每个结点，如果其左子树非空，则左子树左子树的所有结点的所有结点的关的关键值键值都都小于小于该该结点的关键值结点的关键值；如果其右子树非空，则；如果其右子树非空，则右子右子树树的所有结点的的所有结点的关键值关键值都都大于大于该该结点的关键值结点的关键值。二叉排序二叉排序树的示例树的示例 如图如图6.14所示的二叉树，就是一棵二叉排序树。二叉排序所示的二叉树，就是一棵二叉排序树。二叉排序树有查找效率高，增添、删除方便的特点，而且对二叉排树有查找效率高，增添、删除方便的特点，而且对二叉排序树进行中序遍历，将得到一个按结点关键值递增有序的序树进行中序遍历，将得到一个按结点关键值递增有序的中序线性序列。所以，它被广泛地用来作为动态查找的数中序线性序列。所以，它被广泛地用来作为动态查找的数据结构。据结构。二叉排序树的存储结构也采用二叉链表，二叉排序树的存储结构也采用二叉链表，存储结构如下存储结构如下：举例：举例：用二叉排序树作为目录树，把一个记录的关键用二叉排序树作为目录树，把一个记录的关键码和记录的地址作为二叉排序树的结点，按关键码值码和记录的地址作为二叉排序树的结点，按关键码值建成二叉排序树。这样，既能像有序表那样进行高效建成二叉排序树。这样，既能像有序表那样进行高效查找，又能像链表那样灵活删除，而不需要移动其他查找，又能像链表那样灵活删除，而不需要移动其他结点。如要得到按关键码值的排序结果，还可以对其结点。如要得到按关键码值的排序结果，还可以对其进行中序遍历。进行中序遍历。struct bstnode int data; struct bstnode *lch,*rch; ;typedef struct bstnode BSTNode;2、二、二叉排序树的查找叉排序树的查找 在二叉排序树中进行查找，将要查找的值从在二叉排序树中进行查找，将要查找的值从树根开始比较，若与根的关键值相等，则成功；若树根开始比较，若与根的关键值相等，则成功；若比根的关键值比根的关键值小小，则到，则到左子树左子树找；若比根的关键值找；若比根的关键值大大，则到，则到右子树右子树找；直到查找成功或查找子树为空找；直到查找成功或查找子树为空(失败失败)。若成功，则返回查找到结点的地址；若失。若成功，则返回查找到结点的地址；若失败，则返回空指针。败，则返回空指针。查找的递归算法如下：查找的递归算法如下：算法算法6.15 二叉排序树的查找递归算法。二叉排序树的查找递归算法。BSTNode *search(BSTNode *root, int x) if(root=NULL) return(NULL); while(root) if(x=root-elem.key) return(root); if(xelem.key) root=root-lch; else root=root-rch; return(NULL); 3、二叉排序树的插入和生成、二叉排序树的插入和生成 插入是一个动态的查找过程。首先在树中查插入是一个动态的查找过程。首先在树中查找找x，若不存在则插入。从空树开始，插入一系列，若不存在则插入。从空树开始，插入一系列结点，就是二叉排序树的生成过程。例如，给定一结点，就是二叉排序树的生成过程。例如，给定一组关键值序列为组关键值序列为45,24,53, 45,12,24,90，则生成，则生成二叉排序树的过程如图所示。二叉排序树的过程如图所示。45,24,53, 45,12,24,90图6.15 二叉排序树的生成过程 再插入再插入50将要插入的关键值存放在数组将要插入的关键值存放在数组aMAX中，中，MAX为要插为要插入的关键值个数。入的关键值个数。(a) 二叉排序树的插入算法二叉排序树的插入算法算法算法6.16 二叉排序树中插入结点的二叉排序树中插入结点的递归递归算法算法BSTNode *BSTNode_Insert(BSTNode *root, BSTNode *newp) /* /* 在根指针为在根指针为rootroot的二叉排序树中插入结点的二叉排序树中插入结点* *newpnewp */ */ if(root=NULL) return (newp); if(newp-datadata) root-lch=BSTNode_Insert(root-lch, newp); else root-rch=BSTNode_Insert(root-rch, newp); return (root); 算法算法6.17 二叉排序树中插入结点的二叉排序树中插入结点的非递归非递归算法。算法。BSTNode *BSTNode_Insert(BSTNode *root, BSTNode *newp)/*/*在根指针为在根指针为rootroot的二叉排序树中插入关键值为的二叉排序树中插入关键值为aiai 的结点的结点* */ / BSTNode *p=root; if(root=NULL) return(newp); while(1) if(newp-data data) if(p-lch) p=p-lch; else p-lch=newp; return(root); else if(p-rch) p=p-rch; else p-rch=newp; return(root); return(root); (b) 建立二叉排序树建立二叉排序树算法算法6.18 利用插入算法，建立二叉排序树。利用插入算法，建立二叉排序树。BSTNode * BSTNode_Create(BSTNode *root, int a,int n)/* /* 依据依据aa中元素序列，建立二叉排序树中元素序列，建立二叉排序树 * */ / BSTNode *p,*head=NULL; int i; for(i=0; idata=ai; p-lch=p-rch=NULL; head=BSTNode_Insert(head,p); /* /* 调用插入函数调用插入函数 * */ / return(head); 3、二叉排序树的删除、二叉排序树的删除 在二叉排序树中删除结点，首先要进行查找，在二叉排序树中删除结点，首先要进行查找，若查找成功则删除该结点，但删除之后，不能破坏若查找成功则删除该结点，但删除之后，不能破坏原二叉排序树中结点的关系，即删除后二叉树的中原二叉排序树中结点的关系，即删除后二叉树的中序序列仍然是按关键值递增有序。序序列仍然是按关键值递增有序。 删除算法可分下面三种情况讨论：删除算法可分下面三种情况讨论： （1）被删除结点是叶子结点）被删除结点是叶子结点 （2）被删除结点是单分支结点）被删除结点是单分支结点 （3）被删除结点是双分支结点）被删除结点是双分支结点(假定，假定，p指向要删除结点，指向要删除结点，f指向指向p的双亲结点，且的双亲结点，且不失一般性，设不失一般性，设p是是f的右孩子的右孩子)(1) 被删除结点是叶子结点被删除结点是叶子结点若若*p结点为结点为叶子结点叶子结点，只需，只需直接删除直接删除。即：将双亲结点指向它的指针，设置为空指针即：将双亲结点指向它的指针，设置为空指针(f-rch=NULL)。 (2)被删除结点是单分支结点被删除结点是单分支结点 若若*p结点为结点为单分支结点单分支结点，只需用它唯一，只需用它唯一子树的根子树的根去去继承它的位置继承它的位置。即：将双亲结点原指向它的指针，设置为指向它的左即：将双亲结点原指向它的指针，设置为指向它的左孩子或右孩子孩子或右孩子(若只有左子树，则若只有左子树，则f-rch=p-lch；若；若只有右子树，则只有右子树，则f-rch=p-rch) (3)被删除结点是双分支结点被删除结点是双分支结点 若若*p结点为结点为双分支结点双分支结点，为保证删除该结点后，为保证删除该结点后，该树的中序序列任然是按关键值递增有序。该树的中序序列任然是按关键值递增有序。所以有如下两种方法。所以有如下两种方法。 方法方法1：用左子树中序遍历的最后一个结点用左子树中序遍历的最后一个结点(左左子树的最右结点子树的最右结点)替换替换*p。 查找到查找到*p的左子树的右链为空的结点的左子树的右链为空的结点*s；然后，用；然后，用*s的数的数据据替换替换*p的数据的数据；最后，；最后，删除删除*s结点结点。*s是其是其双亲双亲结点的右孩结点的右孩子，并且子，并且s-rch为为NULL。若。若s-lch也为空，则置也为空，则置*s双亲双亲的右指的右指针为针为NULL，删除，删除*s；若若s-lch不为空，则置不为空，则置*s双亲的右指针为双亲的右指针为s-lch，删除，删除*s。方法方法2：用右子树中序遍历的第一个结点用右子树中序遍历的第一个结点(右右子树的最左结点子树的最左结点)替换替换*p。 首先，沿首先，沿*p的右子树的左链，查找到左指针域为空的的右子树的左链，查找到左指针域为空的结点结点*s；然后，用；然后，用*s的数据替换的数据替换*p的数据；最后，删除的数据；最后，删除*s结点。结点。算法算法6.19 二叉排序树中删除结点的算法二叉排序树中删除结点的算法(x x删除结点的关键值删除结点的关键值) )BSTNode * BSTNode_del(BSTNode *root,int x) BSTNode *p,*f,*s_f,*s; /* p/* p要删除结点要删除结点,f,f为为p p的双亲的双亲,s,s为为p p的左子树的最右边结点的左子树的最右边结点, ,s_fs_f为为s s双亲双亲 * */ / if(root=NULL) return; /* /* 二叉排序树为空树二叉排序树为空树 * */ / f=NULL; p=root; while(p!=NULL & p-data!=x) /* /* 查找要删除结点位置查找要删除结点位置 * */ / if(p-datax) if(p-lch!=NULL) f=p; p=p-lch; else break; else if(p-rch!=NULL) f=p; p=p-rch; else break; /* 查找结束，进行节点删除，下一页查找结束，进行节点删除，下一页*/* /* 查找失败，无找到要删除的结点查找失败，无找到要删除的结点 * */ / if(p=NULL) return(root); /* /* 删除删除* *p p的第一种情形：的第一种情形：* *p p为叶子为叶子 * */ / if(p-lch=NULL & p-rch=NULL) if(f=NULL) free(p);return(NULL); /* *p/* *p是双亲的左孩子，进行处理是双亲的左孩子，进行处理 * */ / if(f-lch=p) f-lch=NULL; /* *p/* *p是双亲的右孩子是双亲的右孩子，进行处理，进行处理 * */ / else f-rch=NULL; free(p); /* /* 释放被删除的节点释放被删除的节点* *p p的空间的空间 * */ / return(root); /* /* 删除删除* *p p的第二种情形：的第二种情形：* *p p为单分支结点为单分支结点 * */ / if(p-lch=NULL) /* /* 没有左子树没有左子树 * */ / if(f=NULL) root=p-rch;free(p);return(root); if(f-lch=p) f-lch=p-rch; /* *p/* *p是双亲的左孩子是双亲的左孩子 * */ / else f-rch=p-rch; /* *p/* *p是双亲的右孩子是双亲的右孩子 * */ / free(p); return(root); if(p-rch=NULL) /* /* 没有右子树没有右子树 * */ / if(f=NULL) root=p-lch;free(p);return(root); if(f-lch=p) f-lch=p-lch; else f-rch=p-lch; free(p); return(root); /* /* 删除删除* *p p的第三种情形：的第三种情形：* *p p为双分支结点为双分支结点 * */ / s_f=p; s=p-lch; /* /* 找找* *p p左子树的最右结点左子树的最右结点* *s,*s,*s_fs_f是是* *s s的父结点的父结点 * */ / while(s-rch!=NULL) /* /* 循环，直到循环，直到s s右指针为空右指针为空 * */ / s_f=s; s=s-rch; /* s/* s以替代以替代p p，然后删除，然后删除s s结点结点 * */ / p-data=s-data; if(s-lch=NULL) /* *s/* *s是叶子是叶子 * */ / s_f-rch=NULL; /*/*置置* *s s双亲结点的右指针为空双亲结点的右指针为空* */ / else /* *s/* *s有左子树有左子树 * */ / s_f-rch=s-lch; /*/*置置* *s s双亲的右指针为双亲的右指针为* *s s的左孩子的左孩子* */ / free(s); return(root); 6.5.2 哈夫曼树以及应用哈夫曼树以及应用 哈夫曼树，又称为最优树，是一类带权路径长度最短哈夫曼树，又称为最优树，是一类带权路径长度最短的树，有着广泛的应用。的树，有着广泛的应用。(a)基本术语基本术语 路径：路径：从一个结点到另一个结点之间的若干分支。从一个结点到另一个结点之间的若干分支。 路径长度：路径长度：路径的分支数。路径的分支数。 结点的路径长度：结点的路径长度：从根到该结点的路径长度。从根到该结点的路径长度。 树的路径长度：树的路径长度：树中所有结点的路径长度之和。一般记树中所有结点的路径长度之和。一般记作作PL。 图图6.17所示为计算树的路径长度的示例。在结点数相同的所示为计算树的路径长度的示例。在结点数相同的条件下，路径最短的二叉树为完全二叉树。条件下，路径最短的二叉树为完全二叉树。 若将上述概念推广到一般情况，考虑带有权值的结点。若将上述概念推广到一般情况，考虑带有权值的结点。 结点的带权路径：结点的带权路径：从根到带权结点之间的路径长度与结从根到带权结点之间的路径长度与结点上的权值乘积。点上的权值乘积。树的带权路径：树的带权路径：树中所有带权结点的带权路径长度之和树中所有带权结点的带权路径长度之和(无权值结点的路径不考虑无权值结点的路径不考虑)。一般记作。一般记作WPL，即，即其中，其中，wk是编号为是编号为k结点的权值；结点的权值；lk是根到编号为是根到编号为k结点的结点的路径；路径；n为树中带权结点数。为树中带权结点数。最优二叉树最优二叉树(哈夫曼树哈夫曼树)：假设有假设有n个权值个权值w1,w2,wn，是，是构造一棵有构造一棵有n个叶子结点的严格二叉树个叶子结点的严格二叉树(只有度为只有度为0和度为和度为2的的结点结点)，每个叶子结点带权为，每个叶子结点带权为wi，则其中带权路径长度，则其中带权路径长度WPL最最小的严格二叉树称为哈夫曼树。小的严格二叉树称为哈夫曼树。 因为，哈夫曼树为严格二叉树。所以，由二叉树性质因为，哈夫曼树为严格二叉树。所以，由二叉树性质3可知，哈夫曼树有可知，哈夫曼树有n个叶子结点个叶子结点(度为度为0)和和n+1非终端结点非终端结点(度为度为2)的结点组成：的结点组成：图6.18 具有不同带权路径长度的严格二叉树 例如，图例如，图6.18中的四棵严格二叉树，都有中的四棵严格二叉树，都有4个叶子结点个叶子结点A、B、C、D，分别带权，分别带权7、5、2、4，其中以图，其中以图6.18(c)和和(d)的的WPL最小，可以验证它们两个都是哈夫曼树。所以，哈夫最小，可以验证它们两个都是哈夫曼树。所以，哈夫曼树不是唯一的。它们各自的曼树不是唯一的。它们各自的WPL的值如下。的值如下。 图图6.18(a)：WPL=72+52+22+42=36 图图6.18(b)：WPL=73+53+21+42=46 图图6.18(c)：WPL=71+52+23+43=35 图图6.18(d)：WPL=71+52+23+43=35从图中可以看出，要使二叉树从图中可以看出，要使二叉树WPL小，就必须在构造树小，就必须在构造树时，使权值大的结点靠近树根，而使权值小的结点远离树时，使权值大的结点靠近树根，而使权值小的结点远离树根。根。 (b)哈夫曼树的构造哈夫曼树的构造 哈夫曼哈夫曼(Huffman)最早给出了一个带有一般规律的构造最最早给出了一个带有一般规律的构造最优二叉树的算法，所以俗称为哈夫曼算法。叙述如下：优二叉树的算法，所以俗称为哈夫曼算法。叙述如下： (1)根据给定的根据给定的n个权值个权值w1,w2,wn构成构成n棵二叉树的集棵二叉树的集合合F=T1,T2,Tn，其中每棵二叉树，其中每棵二叉树Ti中只有一个权为中只有一个权为Wi的的根结点，其左右子树为空。根结点，其左右子树为空。 (2)在在F中选取两棵根结点的权值最小的树作为左右子树构中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，新树根结点的权为左右子树根结点的权之造一棵新的二叉树，新树根结点的权为左右子树根结点的权之和。和。 (3)在在F中删除这两棵树，同时将新得到的二叉树加入中删除这两棵树，同时将新得到的二叉树加入F中。中。 (4)重复重复(2)和和(3)，直至，直至F只有含一棵树为止。这棵树便是只有含一棵树为止。这棵树便是哈夫曼树。哈夫曼树。 例如，图例如，图6.19展示了图展示了图6.18(d)的哈夫曼树的构造过程。的哈夫曼树的构造过程。其中，根结点上标注的数字是结点的权值。其中，根结点上标注的数字是结点的权值。图6.19 哈夫曼树的构造过程 在图在图6.19中，每次选取根结点的权值最小的树构造新树，采中，每次选取根结点的权值最小的树构造新树，采用先选取的树为左子树，而后选取的树为右子树的规则。这用先选取的树为左子树，而后选取的树为右子树的规则。这样，对给定的权值序列，其所构造出的哈夫曼树是唯一的。样，对给定的权值序列，其所构造出的哈夫曼树是唯一的。 (3)哈哈夫曼编码夫曼编码 在通信中，在发送端将要传送电文中的字符序列转换在通信中，在发送端将要传送电文中的字符序列转换成成0、1序列后发送，而接收端将接收到的序列后发送，而接收端将接收到的0、1序列再转换成序列再转换成相应的字符序列。字符序列与相应的字符序列。字符序列与0、1序列之间转换是通过信息序列之间转换是通过信息编码实现的。字符集的编码按长度分类，可以分为两种形式编码实现的。字符集的编码按长度分类，可以分为两种形式. (1)等长编码等长编码。采用长度相等的二进制序列表示一个字。采用长度相等的二进制序列表示一个字符。符。ASC就是采用就是采用7位二进制序列表示一个字符。等长编位二进制序列表示一个字符。等长编码对于字符集中使用的频率不同的字符，都采用长度一样的码对于字符集中使用的频率不同的字符，都采用长度一样的编码。这样得到的电文编码的总长度较长，降低了传输效率。编码。这样得到的电文编码的总长度较长，降低了传输效率。 (2)不等长编码不等长编码。 每一个字符所对应二进制序列的长度每一个字符所对应二进制序列的长度是不等的。在一个字符集中，出现是不等的。在一个字符集中，出现频率高频率高的字符所对应的字符所对应编码编码长度短长度短，而出现，而出现频率低频率低的字符所对应的字符所对应编码长度长编码长度长。在不等长。在不等长编码中，为了在接收端将编码中，为了在接收端将0、1序列还原成字符，必须保证序列还原成字符，必须保证任任何字符的编码都不是另一字符编码的前缀何字符的编码都不是另一字符编码的前缀，也称为，也称为前缀编码前缀编码。例例6.1 有一段电文为有一段电文为ABACCDA，它只有，它只有4种字符。种字符。 (1)采用等长编码需要长度为采用等长编码需要长度为2的的0、1编码便可分辨。编码便可分辨。 设：设：A：00 B：01 C：10 D：11 则则 ABACCDA 对应的编码串：对应的编码串：00010010101100，总，总长度为长度为14位。接收端可按每两位对应一个字符进行译码。位。接收端可按每两位对应一个字符进行译码。 (2)采用不等长编码时，将出现次数多的字符采用短的编码采用不等长编码时，将出现次数多的字符采用短的编码. 设：设：A：0 B：00 C：1 D：11 则则 ABACCDA 对应的编码串为对应的编码串为000011110，总长度为，总长度为9位。但接收端对这样的电文编码串无法译码。如开始的子串位。但接收端对这样的电文编码串无法译码。如开始的子串0000就可有多种译法，或是就可有多种译法，或是AAAA，或是，或是ABA，或，或是是BB等。因为，上述编码不是前缀编码。等。因为，上述编码不是前缀编码。 若设：若设：A：0 B：110 C：10 D：111 则该编码是前缀编码。则该编码是前缀编码。ABACCDA 对应的编码串为对应的编码串为0110010101110，总长度为，总长度为13位。接收端可对这样的电文位。接收端可对这样的电文编码进行译码，并且所得到的译码是唯一的编码进行译码，并且所得到的译码是唯一的 可以利用可以利用严格二叉树严格二叉树来来设计设计二进制二进制前前缀编码缀编码。例。例6.1中的前缀编码所对应的严中的前缀编码所对应的严格二叉树如图格二叉树如图6.20所示，在树中，每一个所示，在树中，每一个叶子结点叶子结点对应一个对应一个字符字符，并约定，并约定左分支左分支表示表示编码编码0，右分支右分支表示表示编码编码1，从，从根到根到叶子叶子的的路径路径为该叶子结点上字符的为该叶子结点上字符的编码编码。 图6.20 前缀编码示例 设字符集中的字符在电文中出现的次数为设字符集中的字符在电文中出现的次数为wi(为叶子结点的为叶子结点的权值权值)，其编码长度为，其编码长度为li(从根到叶子路径长度从根到叶子路径长度)，电文中有，电文中有n种字符，则电文的总长度为种字符，则电文的总长度为wili 。由此可见，设计电文总。由此可见，设计电文总长度最短的二进制前缀编码即为以长度最短的二进制前缀编码即为以n种字符出现的频率作权，种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到二进制前缀编码称为设计一棵哈夫曼树的问题，由此得到二进制前缀编码称为哈夫曼编码。如图哈夫曼编码。如图6.18所示的二叉树是一个哈夫曼树，所以，所示的二叉树是一个哈夫曼树，所以，例例6.1的前缀编码是一个哈夫曼编码。的前缀编码是一个哈夫曼编码。