数据结构-第5章-树和二叉树.pptx

数据结构 新世纪应用型高等教育新世纪应用型高等教育计算机类课程规划教材计算机类课程规划教材新世纪应用型高等教育教材编审委员会新世纪应用型高等教育教材编审委员会 组编组编 主编主编 曹春萍曹春萍5.1 树和二叉树的基本概念第第5 5章章树和二叉树树和二叉树5.1.1 5.1.1 树的定义及相关术语树的定义及相关术语1 1树的定义树的定义树的定义树的定义 树树(Tree)是是n(n=0)个结点的有限集个结点的有限集T，n=0时称为空树，否则它满足如下两个条件：时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根）有且仅有一个特定的称为根(Root)的结点；的结点；（2）其余的结点可分为）其余的结点可分为m(m=0)个互不相交的子集个互不相交的子集T1、T2、T3、Tm，其中每个子，其中每个子集又是一棵树，并称其为根结点的子树集又是一棵树，并称其为根结点的子树(Subtree)。从树的定义和图从树的定义和图5-1的示例可以看出，树具有下面两个特点：的示例可以看出，树具有下面两个特点：(1)(1)树树的根结点没有前驱结点，除根结点之外的所有结点的根结点没有前驱结点，除根结点之外的所有结点有有且且仅有一个前驱结点；仅有一个前驱结点；(2)树中所有结点可以有零个或多个后继结点。树中所有结点可以有零个或多个后继结点。5.1 树和二叉树的基本概念第第5 5章章树和二叉树树和二叉树2.2.相关术语相关术语相关术语相关术语(1)树的结点树的结点 (Node)指一个数据元素及指向其子树的分支。指一个数据元素及指向其子树的分支。(2)结点的度结点的度 (Degree)结点所拥有的子树的个数称为该结点的度。图结点所拥有的子树的个数称为该结点的度。图5-1中结点中结点A的度为的度为3，结点，结点B的度为的度为4，结点，结点F的度为的度为2，结点，结点D的度为的度为1，结点，结点C、E、G、H、I、J、K的度为的度为0。(3)树的度树的度 树中各结点度的最大值称为该树的度。图树中各结点度的最大值称为该树的度。图5-1中树的度为中树的度为4。(4)分支结点分支结点 度大于度大于0的结点称为分支结点或非终端结点。的结点称为分支结点或非终端结点。图图5-1中的分支结点有中的分支结点有A、B、D、F。(5)叶子结点叶子结点 (Leaf)度为度为0的结点称为叶子结点或终端结点，的结点称为叶子结点或终端结点，简称叶子。图简称叶子。图5-1中的叶子中的叶子结点为结点为C、E、G、H、I、J、K。(6)孩子结点孩子结点 (Child)某一结点的子树的根称为该结点的孩子结点，简称孩子。图某一结点的子树的根称为该结点的孩子结点，简称孩子。图5-1中结中结点点A的孩子为的孩子为B、C、D。5.1 树和二叉树的基本概念第第5 5章章树和二叉树树和二叉树(7)双亲结点双亲结点 (Parent)一个结点称为它孩子结点的双亲结点。图一个结点称为它孩子结点的双亲结点。图5-1中结点中结点B的双亲为的双亲为A。(8)兄弟、堂兄弟兄弟、堂兄弟 具有同一个双亲的孩子结点互称为兄弟；双亲在同一层的结点互为堂具有同一个双亲的孩子结点互称为兄弟；双亲在同一层的结点互为堂兄弟。图兄弟。图5-1中中B、C、D为兄弟，为兄弟，E、I是堂兄弟。是堂兄弟。(9)祖先、子孙祖先、子孙 在树中，从根到某个结点所经分支上的所有结点称为该结点的祖先；一在树中，从根到某个结点所经分支上的所有结点称为该结点的祖先；一个结点的子树中的任一结点为该结点的子孙结点。个结点的子树中的任一结点为该结点的子孙结点。(10)结点的层数结点的层数 (Level)规定树的根结点的层数为规定树的根结点的层数为1，其余结点的层数等于它的双亲结点，其余结点的层数等于它的双亲结点的层数加的层数加1。图。图5-1中中A的层数为的层数为1，B、C、D的层数为的层数为2，E、F、G、H、I的层数为的层数为3，J、K的的层数为层数为4。(11)树的深度树的深度 (Depth)树中所有结点的最大层数。图树中所有结点的最大层数。图5-1中树的深度为中树的深度为4。(12)有序树和无序树有序树和无序树 如果一棵树中结点的各子树从左到右是有次序的，即如果交换了某如果一棵树中结点的各子树从左到右是有次序的，即如果交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。(13)森林森林 (Forest)棵或更多棵互不相交的树的集合。棵或更多棵互不相交的树的集合。5.1 树和二叉树的基本概念第第5 5章章树和二叉树树和二叉树5.1.2 5.1.2 二叉树的定义及特殊二叉树二叉树的定义及特殊二叉树1 1二叉树二叉树二叉树二叉树的定义的定义的定义的定义二叉树二叉树T(Binary Tree)是是n（n0）个结点的有限集合，它满足下面两个条件：）个结点的有限集合，它满足下面两个条件：（1）当）当n=0时，时，T为空二叉树；为空二叉树；（2）当）当n0时，它是由一个称为根的结点时，它是由一个称为根的结点t及两个互不相交的子集组成，其中每个子集又及两个互不相交的子集组成，其中每个子集又是一棵二叉树，分别称为是一棵二叉树，分别称为t的左子树和右子树。的左子树和右子树。由上述二叉树的定义可知，对于非空二叉树有且仅有一个结点由上述二叉树的定义可知，对于非空二叉树有且仅有一个结点t没有前驱，称为树根；除没有前驱，称为树根；除t之外，二叉树中的所有结点有且仅有一个直接前驱、最多有两个直接后继。同时，在此定义中之外，二叉树中的所有结点有且仅有一个直接前驱、最多有两个直接后继。同时，在此定义中又用到了二叉树的概念，所以二叉树的定义是一个递归定义，它刻画出了二叉树的固有特性又用到了二叉树的概念，所以二叉树的定义是一个递归定义，它刻画出了二叉树的固有特性。5.1 树和二叉树的基本概念第第5 5章章树和二叉树树和二叉树5.1.2 5.1.2 二叉树的定义及特殊二叉树二叉树的定义及特殊二叉树1 1二叉树二叉树二叉树二叉树的定义的定义的定义的定义二叉树二叉树T(Binary Tree)是是n（n0）个结点的有限集合，它满足下面两个条件：）个结点的有限集合，它满足下面两个条件：（1）当）当n=0时，时，T为空二叉树；为空二叉树；（2）当）当n0时，它是由一个称为根的结点时，它是由一个称为根的结点t及两个互不相交的子集组成，其中每个子集又及两个互不相交的子集组成，其中每个子集又是一棵二叉树，分别称为是一棵二叉树，分别称为t的左子树和右子树。的左子树和右子树。由上述二叉树的定义可知，对于非空二叉树有且仅有一个结点由上述二叉树的定义可知，对于非空二叉树有且仅有一个结点t没有前驱，称为树根；除没有前驱，称为树根；除t之外，二叉树中的所有结点有且仅有一个直接前驱、最多有两个直接后继。同时，在此定义中之外，二叉树中的所有结点有且仅有一个直接前驱、最多有两个直接后继。同时，在此定义中又用到了二叉树的概念，所以二叉树的定义是一个递归定义，它刻画出了二叉树的固有特性又用到了二叉树的概念，所以二叉树的定义是一个递归定义，它刻画出了二叉树的固有特性。5.1 树和二叉树的基本概念第第5 5章章树和二叉树树和二叉树5.1 树和二叉树的基本概念第第5 5章章树和二叉树树和二叉树2 2特殊二叉树特殊二叉树特殊二叉树特殊二叉树(1)满二叉树满二叉树 (Full Binary Tree)若一棵二叉树的最下面一层结点度数全为若一棵二叉树的最下面一层结点度数全为0，其它所有结点的度数均为，其它所有结点的度数均为2，则称这种二叉树，则称这种二叉树为满二叉树。如图为满二叉树。如图5-7(a)所示。所示。(2)完全二叉树完全二叉树 (Complete Binary Tree)若一棵二叉树至多只有最下面的两层结点的度数小于若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一层结点都集中在该，并且最下面一层结点都集中在该层的最左边，则称这种二叉树为完全二叉树。如图层的最左边，则称这种二叉树为完全二叉树。如图5-7(b)所示，而图所示，而图5-7（c）不是完全二叉树。）不是完全二叉树。5.1 树和二叉树的基本概念第第5 5章章树和二叉树树和二叉树5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树5.2.1 5.2.1 二叉树的性质二叉树的性质性质性质性质性质1 1 在非空二叉树的第在非空二叉树的第在非空二叉树的第在非空二叉树的第i i层上最多有层上最多有层上最多有层上最多有2i-12i-1个结点个结点个结点个结点(i1)(i1)。证明证明 此性质用数学归纳法来证明。此性质用数学归纳法来证明。当当i=1时，第一层上只有时，第一层上只有个根结点，结论成立；个根结点，结论成立；假设对所有的假设对所有的j,（1ji），结论成立，即第），结论成立，即第j层上有层上有2j-1个结点。则有，对于个结点。则有，对于j=i-1时，由归时，由归纳假设可知第纳假设可知第i-1层上最多有层上最多有2i-2个结点，又由于二叉树的每个结点的度最多为个结点，又由于二叉树的每个结点的度最多为2，所以在第，所以在第i层层上的最大结点数为第上的最大结点数为第i-1层最大结点数的层最大结点数的2倍，即有倍，即有22i-2=2i-1，故对于，故对于j=i时结论成立，得证。时结论成立，得证。5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树性质性质性质性质2 2 深度为深度为深度为深度为k k的二叉树最多有的二叉树最多有的二叉树最多有的二叉树最多有2k-12k-1个结点个结点个结点个结点(k1)(k1)。证明证明 由性质由性质1可知，深度为可知，深度为k的二叉树的最大结点数为：的二叉树的最大结点数为：5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树性质性质性质性质3 3 对任何一棵二叉树对任何一棵二叉树对任何一棵二叉树对任何一棵二叉树T T，如果终端结点，如果终端结点，如果终端结点，如果终端结点(叶子结点叶子结点叶子结点叶子结点)的个数为的个数为的个数为的个数为n0n0，度为，度为，度为，度为2 2的结点数为的结点数为的结点数为的结点数为n2n2，那么那么那么那么n0=n2+1n0=n2+1。证明证明 设二叉树设二叉树T的总结点数为的总结点数为n，度为，度为1的结点数为的结点数为n1，由于二叉树中结点的度都小于等，由于二叉树中结点的度都小于等于于2，所以二叉树的结点总数，所以二叉树的结点总数n为：为：5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树性质性质性质性质4 4 一棵非空二叉树空子树的数目等于其结点数目加一棵非空二叉树空子树的数目等于其结点数目加一棵非空二叉树空子树的数目等于其结点数目加一棵非空二叉树空子树的数目等于其结点数目加1 1。证明证明 设二叉树设二叉树T有有n个结点，将其所有空子树换成叶结点，把新的二叉树记为个结点，将其所有空子树换成叶结点，把新的二叉树记为T，即，即T中中的叶结点数恰为的叶结点数恰为T中的空子树的数目，设有中的空子树的数目，设有n0 个。所有原来树个。所有原来树T的结点现在是树的结点现在是树T的分支结点，的分支结点，即即T中分支结点有中分支结点有n个，又由于树个，又由于树T中的所有分支结点都有两个子结点，即在中的所有分支结点都有两个子结点，即在T中度为中度为2的结点的结点数数n2=n，由性质，由性质3可以得出，可以得出，n0=n+1，得证。，得证。5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树性质性质性质性质5 5 具有具有具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为 证明证明 设该二叉树的深度为设该二叉树的深度为K，则由性质，则由性质2和完全二叉树的定义可知：和完全二叉树的定义可知：则有则有 ，因为，因为k为数，所以有为数，所以有。5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树性质性质性质性质6 6 如果对一棵有如果对一棵有如果对一棵有如果对一棵有n n个结点的完全二叉树的结点按层数编号个结点的完全二叉树的结点按层数编号个结点的完全二叉树的结点按层数编号个结点的完全二叉树的结点按层数编号(从第从第从第从第1 1层到第层到第层到第层到第 层，每层从左层，每层从左层，每层从左层，每层从左到右编号到右编号到右编号到右编号)，那么对任意结点，那么对任意结点，那么对任意结点，那么对任意结点i(1in)i(1in)有：有：有：有：如果如果i1，则结点，则结点i是二叉树的根，无双亲结点；如果是二叉树的根，无双亲结点；如果i1，则其双亲结点的编号是，则其双亲结点的编号是 ；如果如果2in，则结点，则结点i无左孩子无左孩子(结点结点i为叶子结点为叶子结点)；否则其左孩子结点的编号是；否则其左孩子结点的编号是2i；如果如果2i+1n，则结点，则结点i无右孩子，否则其右孩子结点的编号是无右孩子，否则其右孩子结点的编号是2i+1。5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树5.2.2 5.2.2 二叉树的存储结构二叉树的存储结构1.1.二叉树的顺序存储表示二叉树的顺序存储表示二叉树的顺序存储表示二叉树的顺序存储表示(1)完全（满）二叉树的顺序存储完全（满）二叉树的顺序存储由二叉树的性质由二叉树的性质6可知，完全二叉树按层编号后，结点编号间有一定的关系。在顺序存储可知，完全二叉树按层编号后，结点编号间有一定的关系。在顺序存储中，利用此性质，将完全二叉树上编号为中，利用此性质，将完全二叉树上编号为i的结点元素存储在一维数组中下标为的结点元素存储在一维数组中下标为i的分量中，图的分量中，图5-7（b）所示完全二叉树的顺序存储如图）所示完全二叉树的顺序存储如图5-8所示，这样第所示，这样第0个单元不存储数据。个单元不存储数据。5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树(2)一般二叉树的存储一般二叉树的存储对于一般二叉树可以参照完全二叉树对于一般二叉树可以参照完全二叉树的存储来实现。如图的存储来实现。如图5-9（a）所示二叉树）所示二叉树的顺序存储如图的顺序存储如图5-9（b）所示，图）所示，图5-9（c）指明了每个结点之间的相互关系。）指明了每个结点之间的相互关系。5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树2.二叉树的链式存储表示二叉树的链式存储表示链式存储就是用链表来存储二叉树中的结点，通过指针反映结点之间的逻辑关系。二叉树链式存储就是用链表来存储二叉树中的结点，通过指针反映结点之间的逻辑关系。二叉树常用的链式存储形式有二叉链表、三叉链表及线索链表等。对于线索链表在后面再进行说明。常用的链式存储形式有二叉链表、三叉链表及线索链表等。对于线索链表在后面再进行说明。(1)二叉链表二叉链表二叉树中的每个结点最多有两个孩子，因此可以用这样的方式存储二叉树：在每个结点中二叉树中的每个结点最多有两个孩子，因此可以用这样的方式存储二叉树：在每个结点中包含三个域，即一个数据元素域及两个分别指向左、右子树根结点的指针域组成。这种结点结包含三个域，即一个数据元素域及两个分别指向左、右子树根结点的指针域组成。这种结点结构称之为二叉链表结构。结点的存储结构如下：构称之为二叉链表结构。结点的存储结构如下：5.2 二叉树的性质和存储结构第第5 5章章树和二叉树树和二叉树(2)三叉链表三叉链表为了方便地查找双亲，在二叉链表的结点中再增加一个指向双亲的指针域，这种结构称做为了方便地查找双亲，在二叉链表的结点中再增加一个指向双亲的指针域，这种结构称做为三叉链表存储结构。结点结构如下为三叉链表存储结构。结点结构如下：其中，其中，data、lchild、rchild三个域的意义同二叉链表结构；三个域的意义同二叉链表结构；parent域为指向该结点双亲域为指向该结点双亲结点的指针。同样，在三叉链表中也增加一个指向根结点的指针结点的指针。同样，在三叉链表中也增加一个指向根结点的指针BT。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树5.3.1 5.3.1 遍历二叉树遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点；或者对树中全部结点在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点；或者对树中全部结点逐一进行某种处理，比如打印出每个结点的内容、判断二叉树是否连通等等。这都是与二叉树逐一进行某种处理，比如打印出每个结点的内容、判断二叉树是否连通等等。这都是与二叉树的遍历有关的问题。的遍历有关的问题。遍历二叉树遍历二叉树 (Traversing Binary Tree)是指按照某条搜索路径访问二叉树中的每个结点是指按照某条搜索路径访问二叉树中的每个结点,使得每一个结点均被访问一次，而且仅被访问一次。使得每一个结点均被访问一次，而且仅被访问一次。在此的所谓在此的所谓“访问访问”可以是对结点做各种处理，如输出结点数据可以是对结点做各种处理，如输出结点数据域域值值、比较、更新、查看元素内容等等、比较、更新、查看元素内容等等。对线性表的遍历，可以按表的顺序很简单地实现。但由于对线性表的遍历，可以按表的顺序很简单地实现。但由于二叉树二叉树是是一种非线性结构，因此，对二叉树的遍历就不能那样简单地实现。一种非线性结构，因此，对二叉树的遍历就不能那样简单地实现。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树1.1.二叉树遍历的递归算法二叉树遍历的递归算法二叉树遍历的递归算法二叉树遍历的递归算法(1)先序遍历（先序遍历（Preorder Traversal）先序遍历的递归过程为：若二叉树为空，遍历结束。否则先序遍历的递归过程为：若二叉树为空，遍历结束。否则 访问根结点；访问根结点；先序遍历根的左子树；先序遍历根的左子树；先序遍历根的右子树。先序遍历根的右子树。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树(2)中序遍历（中序遍历（LDR）中序遍历的递归过程为：若二叉树为空，遍历结束。否则中序遍历的递归过程为：若二叉树为空，遍历结束。否则中中序遍历根的左子树；序遍历根的左子树；访问访问根结点；根结点；中中序遍历根的右子树。序遍历根的右子树。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树(3)(3)后序遍历（后序遍历（后序遍历（后序遍历（LRDLRD）后序遍历的递归过程为：若二叉树为空，遍历结束。否则后序遍历的递归过程为：若二叉树为空，遍历结束。否则（1）后序遍历根的左子树；）后序遍历根的左子树；（2）后序遍历根的右子树；）后序遍历根的右子树；（3）访问根结点。）访问根结点。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树2 2.二叉树遍历的非递归算法二叉树遍历的非递归算法二叉树遍历的非递归算法二叉树遍历的非递归算法前面给出的二叉树先序、中序和后序三种遍历算法都是递归算法。递归算法相对简洁直观，前面给出的二叉树先序、中序和后序三种遍历算法都是递归算法。递归算法相对简洁直观，容易写出，但可读性一般不好，执行效率也不高。因此，就存在如何把一个递归算法转化为非容易写出，但可读性一般不好，执行效率也不高。因此，就存在如何把一个递归算法转化为非递归算法的问题递归算法的问题。对于对于图图5-16（a）所示的二叉树，其先序、中序和后序遍历都是从根结点）所示的二叉树，其先序、中序和后序遍历都是从根结点A开始的，且在遍开始的，且在遍历过程中经过结点的路线也是一样的，只是历过程中经过结点的路线也是一样的，只是访问访问的的时机不同而已。图时机不同而已。图(b)是从根结点左外侧开始是从根结点左外侧开始，到到根结点右外侧结束的路线，即是图根结点右外侧结束的路线，即是图(a)的的遍历遍历路线路线。沿着该路线按。沿着该路线按 标记标记的结点读得的的结点读得的序列序列为先为先序序列序序列A B D F C E，按，按 标记标记读得的读得的序序列为中序列为中序序列序列B F D A E C，按按 标记读得的标记读得的序序列为后序序列列为后序序列F D B E C A。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树3 3二叉树的确定性二叉树的确定性二叉树的确定性二叉树的确定性前面给出了二叉树的先序、中序和后序遍历的算法，对于给定的二叉树调用相应的算法也前面给出了二叉树的先序、中序和后序遍历的算法，对于给定的二叉树调用相应的算法也就得到了相应的先序、中序和后序遍历序列。很明显，对于不同形态的二叉树，先序遍历序列就得到了相应的先序、中序和后序遍历序列。很明显，对于不同形态的二叉树，先序遍历序列可能相同；中序遍历序列可能相同；后序遍历序列也可能相同。但是，如果给定某棵二叉树的可能相同；中序遍历序列可能相同；后序遍历序列也可能相同。但是，如果给定某棵二叉树的两种遍历序列，是否可以唯一的确定二叉树呢？实际上，有如下的定理：两种遍历序列，是否可以唯一的确定二叉树呢？实际上，有如下的定理：定理定理 任何任何n（n0）个不同结点的二叉树，都可由它的中序序列和先序序列唯一地确定。）个不同结点的二叉树，都可由它的中序序列和先序序列唯一地确定。这个定理也是二叉树的确定性。这个定理也是二叉树的确定性。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树5.3.2 5.3.2 线索二叉树线索二叉树常用常用的不用栈的二叉树遍历的非递归方法有以下几种：的不用栈的二叉树遍历的非递归方法有以下几种：（1）对二叉树采用三叉链表存放，这样在遍历深入到不能再深人时，可沿着走过的路径）对二叉树采用三叉链表存放，这样在遍历深入到不能再深人时，可沿着走过的路径回退到任何一棵子树的根结点，并再向另一方向走。当然，这一方法在每个结点中增加了一个回退到任何一棵子树的根结点，并再向另一方向走。当然，这一方法在每个结点中增加了一个双亲域，故其存储开销相应的有所增加。双亲域，故其存储开销相应的有所增加。（2）在线索二叉树上的遍历，即利用二叉树中叶子结点和度为）在线索二叉树上的遍历，即利用二叉树中叶子结点和度为1结点的空指针域，来存放结点的空指针域，来存放线索，然后在这种具有线索的二叉树上遍历，这种遍历方法既不需要栈，也不需要递归。下面线索，然后在这种具有线索的二叉树上遍历，这种遍历方法既不需要栈，也不需要递归。下面给出有关线索二叉树的详细内容。给出有关线索二叉树的详细内容。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树1 1 线索二叉树的定义线索二叉树的定义线索二叉树的定义线索二叉树的定义在线性结构中，结点有唯一的直接前驱和直接后继。而二叉树是非线性结构，它的后继并在线性结构中，结点有唯一的直接前驱和直接后继。而二叉树是非线性结构，它的后继并不唯一。但在遍历二叉树时，按照一定的规则将二叉树的结点排列成一个线性序列，从而得到不唯一。但在遍历二叉树时，按照一定的规则将二叉树的结点排列成一个线性序列，从而得到了二叉树的先序序列、中序序列和后序序列。因此遍历操作实际上是将二叉树进行线性化的操了二叉树的先序序列、中序序列和后序序列。因此遍历操作实际上是将二叉树进行线性化的操作，也就是把非线性的二叉树线性化成了一个逻辑上除第一个结点无前驱和最后一个结点无后作，也就是把非线性的二叉树线性化成了一个逻辑上除第一个结点无前驱和最后一个结点无后继外，其它所有结点都有一个前驱和一个后继的线性序列。但是在二叉树的链式存储结构中，继外，其它所有结点都有一个前驱和一个后继的线性序列。但是在二叉树的链式存储结构中，只有左右孩子的信息而无前驱和后继的信息，从而只能在对二叉树遍历的动态过程中得到这些只有左右孩子的信息而无前驱和后继的信息，从而只能在对二叉树遍历的动态过程中得到这些信息。信息。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树2 2 线索二叉树线索二叉树线索二叉树线索二叉树的结构的结构的结构的结构为了避免混淆，一般是在结点中增加两个标志域来标识二叉链表的指针域是指向儿子的指为了避免混淆，一般是在结点中增加两个标志域来标识二叉链表的指针域是指向儿子的指针还是指向某遍历序列的前驱或后继的指针。这时结点结构定义如下。针还是指向某遍历序列的前驱或后继的指针。这时结点结构定义如下。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树3 3 二叉树的线索化及遍历线索二叉树的线索化及遍历线索二叉树的线索化及遍历线索二叉树的线索化及遍历线索二叉树二叉树二叉树二叉树给出一棵用二叉链表存储的二叉树，要将它按中序线索化，或者说对二叉树中序线索化，给出一棵用二叉链表存储的二叉树，要将它按中序线索化，或者说对二叉树中序线索化，实质上就是按中序遍历此二叉树，在遍历的过程中用线索代替空的指针，即检查当前结点的左、实质上就是按中序遍历此二叉树，在遍历的过程中用线索代替空的指针，即检查当前结点的左、右指针域是否为空，如果为空，则改为指向其在中序遍历序列中的直接前驱结点或直接后继结右指针域是否为空，如果为空，则改为指向其在中序遍历序列中的直接前驱结点或直接后继结点。点。另外，在对一棵二叉树加线索时，模仿线性链表的存储结构，在二叉树的线索链表上也添另外，在对一棵二叉树加线索时，模仿线性链表的存储结构，在二叉树的线索链表上也添加一个头结点，并且建立头结点与二叉树的根结点的指向关系，即令头结点加一个头结点，并且建立头结点与二叉树的根结点的指向关系，即令头结点lchild域的指针指域的指针指向二叉树的根结点；对二叉树线索化后，还需建立最后一个结点与头结点之间的线索，即头结向二叉树的根结点；对二叉树线索化后，还需建立最后一个结点与头结点之间的线索，即头结点的点的rchild域的指针指向中序遍历时访问的最后一个结点。同时，令二叉树中序序列中的第一域的指针指向中序遍历时访问的最后一个结点。同时，令二叉树中序序列中的第一个结点的个结点的lchild域指针和最后一个结点的域指针和最后一个结点的rchild域指针均指向头结点；就像为二叉树建立了一个域指针均指向头结点；就像为二叉树建立了一个双向线索链表。双向线索链表。5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树3 3 二叉树的线索化及遍历线索二叉树的线索化及遍历线索二叉树的线索化及遍历线索二叉树的线索化及遍历线索二叉树二叉树二叉树二叉树5.3 二叉树的遍历及线索化第第5 5章章树和二叉树树和二叉树4 4 遍历算法的应用遍历算法的应用遍历算法的应用遍历算法的应用通过通过二叉树的遍历，可以得到一个二叉树结点的线性序列，由于二叉树的结点之间的逻辑二叉树的遍历，可以得到一个二叉树结点的线性序列，由于二叉树的结点之间的逻辑关系是非线性的，在访问结点时就要进行多种判断，利用遍历算法可以解决许多有关二叉树上关系是非线性的，在访问结点时就要进行多种判断，利用遍历算法可以解决许多有关二叉树上的操作要求。在高级语言的编译程序中，经常需要处理和计算一些表达式，例如对算术表达式的操作要求。在高级语言的编译程序中，经常需要处理和计算一些表达式，例如对算术表达式或逻辑表达式进行求值运算。而对于任意一个表达式中的二元运算符处理需要考虑运算符的优或逻辑表达式进行求值运算。而对于任意一个表达式中的二元运算符处理需要考虑运算符的优先级，而且大部分运算符（二元运算符）都有这样的特点：一个运算符对应两个操作数。故我先级，而且大部分运算符（二元运算符）都有这样的特点：一个运算符对应两个操作数。故我们可以将二元运算表示成图们可以将二元运算表示成图5-19（a）所示的形式：）所示的形式：5.4 树和森林第第5 5章章树和二叉树树和二叉树5.4.1 5.4.1 树的存储结构树的存储结构在计算机中，树的存储结构有多种形式，既可以采用顺序存储结构，也可以采用链式存储在计算机中，树的存储结构有多种形式，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系。唯一地反映树中各结点之间的逻辑关系。1顺序存储结构 (1)父亲表示法 (2)左孩子结点/右兄弟表示法（孩子兄弟表示）5.4 树和森林第第5 5章章树和二叉树树和二叉树2链式存储结构链式存储结构上述两种实现树的方法使用数组存储结点。我们接着尝试将链表表示法扩展到树，即树的上述两种实现树的方法使用数组存储结点。我们接着尝试将链表表示法扩展到树，即树的链式存储结构。链式存储结构。(1)孩子链表表示法孩子链表表示法是对树的每个结点建立一个儿子结点链表，是对树的每个结点建立一个儿子结点链表，由于由于各各结点的儿子结点数目多少不一，所以常用单链表结点的儿子结点数目多少不一，所以常用单链表来来实现实现儿子结点链表。儿子结点链表。5.4 树和森林第第5 5章章树和二叉树树和二叉树(2)孩子兄弟表示法孩子兄弟表示法又称为二叉树表示法或二叉链表表示法，即以二叉链表作树的存储结构。具体含义是这样又称为二叉树表示法或二叉链表表示法，即以二叉链表作树的存储结构。具体含义是这样的：在树中每个结点除其数据域外，再增加两个指针域，分别是指向该结点的第的：在树中每个结点除其数据域外，再增加两个指针域，分别是指向该结点的第个孩子结点个孩子结点的指针和下一个兄弟结点的指针。在这种表示法中，既用到了儿子指针又用到了兄弟指针，因的指针和下一个兄弟结点的指针。在这种表示法中，既用到了儿子指针又用到了兄弟指针，因此称这种表示法为儿子兄弟表示法。图此称这种表示法为儿子兄弟表示法。图5-1的孩子兄弟表示法如图的孩子兄弟表示法如图5-25所示。所示。5.4 树和森林第第5 5章章树和二叉树树和二叉树5.4.2 5.4.2 树、森林雨二叉树的装换树、森林雨二叉树的装换从从前面几节的讨论可知，相对于二叉树来说，树的存储结构要复杂得多，主要是由于树中前面几节的讨论可知，相对于二叉树来说，树的存储结构要复杂得多，主要是由于树中每个结点的度可能相差很多，且没有规律。更重要的是一般树的基本运算实现比较复杂，而对每个结点的度可能相差很多，且没有规律。更重要的是一般树的基本运算实现比较复杂，而对于二叉树就有相应的一系列实现简单而于二叉树就有相应的一系列实现简单而成成熟熟的算法。同时由上一节可知，任何树的算法。同时由上一节可知，任何树都都可以可以采用孩子兄弟链表作为存储结构，采用孩子兄弟链表作为存储结构，那那么么树或森林与二叉树之间是否存着某种树或森林与二叉树之间是否存着某种转转换换关系呢？图关系呢？图5-26直观地给出了树与二直观地给出了树与二叉叉树树之间的对应关系。之间的对应关系。5.4 树和森林第第5 5章章树和二叉树树和二叉树1 1森林转换为二叉树森林转换为二叉树森林转换为二叉树森林转换为二叉树设设TT1，T2，Tn是一棵森林，那么是一棵森林，那么T可以按如下方法转换成一棵二叉树可以按如下方法转换成一棵二叉树BT。如如T为空，那么为空，那么BT为空二叉树；为空二叉树；如果如果T非空，那么非空，那么BT的根结点为森林的第一棵树的根结点为森林的第一棵树T1的根，的根，BT的左子树为的左子树为T1去掉根结点去掉根结点后的子树组成的森林按此方法转换成的二叉树，后的子树组成的森林按此方法转换成的二叉树，BT的右子树为森林的右子树为森林T2，Tn按此方法转按此方法转换成的二叉树。换成的二叉树。可以证明，森林通过这种方法转换后所得的二叉树是唯一的。可以证明，森林通过这种方法转换后所得的二叉树是唯一的。5.4 树和森林第第5 5章章树和二叉树树和二叉树2 2二叉树转换成森林二叉树转换成森林二叉树转换成森林二叉树转换成森林设设BTroot，lbt，rbt是一棵二叉树，其中，是一棵二叉树，其中，root为二叉树的根结点，为二叉树的根结点，lbt、rbt分别是分别是root的左子树和右子树。那么的左子树和右子树。那么BT可以按可以按如下如下方法方法转换成森林转换成森林T=T1，T2，Tn。BT为空，那么为空，那么T为空树；为空树；BT非空，那么森林非空，那么森林T中第一棵树中第一棵树T1的的根根为二叉树为二叉树BT的根结点的根结点root，T中第中第棵棵树树T1的根的子树森林为的根的子树森林为BT的左子树的左子树lbt按此按此方方法法转换成的森林，森林转换成的森林，森林T2，Tn为为BT的右子树的右子树rbt按此方法转换成的森林。按此方法转换成的森林。5.4 树和森林第第5 5章章树和二叉树树和二叉树5.4.3 5.4.3 树及森林的遍历树及森林的遍历与二叉树类似，遍历是树和森林的一种基本运算。对于树来说仍有三种主要的遍历方法，与二叉树类似，遍历是树和森林的一种基本运算。对于树来说仍有三种主要的遍历方法，即先序即先序(根根)遍历、后序遍历和层次遍历；而对于森林来说，一般有前序遍历和中序遍历两种方遍历、后序遍历和层次遍历；而对于森林来说，一般有前序遍历和中序遍历两种方法。法。1树的遍历树的遍历先序遍历先序遍历若树非空，则：若树非空，则：()访问根结点；访问根结点；()按照从左到右依次先根序遍历根的每棵子树按照从左到右依次先根序遍历根的每棵子树。5.4 树和森林第第5 5章章树和二叉树树和二叉树后序遍历后序遍历若树非空，则：若树非空，则：()先按照从左到右依次后根遍历根的每棵子树；先按照从左到右依次后根遍历根的每棵子树；()访问根结点。访问根结点。层次遍历层次遍历若树非空，则先访问根结点，再按从左到右的顺序访问第二层上的结点，依次按层访问，若树非空，则先访问根结点，再按从左到右的顺序访问第二层上的结点，依次按层访问，直到树中的所有结点都被访问完为止。直到树中的所有结点都被访问完为止。5.4 树和森林第第5 5章章树和二叉树树和二叉树2.2.森林的遍历森林的遍历森林的遍历森林的遍历先序遍历先序遍历若森林非空，则若森林非空，则()访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；()先序遍历第一棵树中根结点的子树森林；先序遍历第一棵树中根结点的子树森林；()先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历中序遍历若森林非空，则若森林非空，则()中序遍历森林中第一棵树的根结点的子树森林；中序遍历森林中第一棵树的根结点的子树森林；()访问第一棵树的根结点；访问第一棵树的根结点；()中序遍历除去第一棵树之后剩余的树构成的森林。中序遍历除去第一棵树之后剩余的树构成的森林。5.5 最优二叉树及哈夫曼编码第第5 5章章树和二叉树树和二叉树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，将百分制转换成五级分制的程序流程图如图序的执行效率。例如，将百分制转换成五级分制的程序流程图如图5-30（a）：）：5.5 最优二叉树及哈夫曼编码第第5 5章章树和二叉树树和二叉树5.5.1 5.5.1 哈夫曼树的基本概念及其构造哈夫曼树的基本概念及其构造1有关术语及哈夫曼树的定义有关术语及哈夫曼树的定义首先给出树中的一些与哈夫曼树有关的术语及哈夫曼树的定义。首先给出树中的一些与哈夫曼树有关的术语及哈夫曼树的定义。(1)路径路径丛丛树中一个结点到另一个结点之间的分支称为这两个结点间的路径。树中一个结点到另一个结点之间的分支称为这两个结点间的路径。(2)路径长度路径长度路径路径上的分支数目称为路径长度。上的分支数目称为路径长度。(3)树的路径长度树的路径长度树的路径长度是指从树根到每个结点的路径长度之和。树的路径长度是指从树根到每个结点的路径长度之和。完全二叉树是路径长度最短的二叉树完全二叉树是路径长度最短的二叉树。5.5 最优二叉树及哈夫曼编码第第5 5章章树和二叉树树和二叉树(4)树结点的权树结点的权将将树中的结点赋上一个有某种意义的实数，称此实数为该结点的权。树中的结点赋上一个