第6章_树和二叉树07.ppt

孙克雷制作第第6 6章章 树和二叉树树和二叉树学习要点学习要点q 了解树的定义和基本术语，重点了解二叉树的定了解树的定义和基本术语，重点了解二叉树的定义、性质和存储结构。义、性质和存储结构。q 掌握二叉树遍历的递归算法及它的典型运算。掌握二叉树遍历的递归算法及它的典型运算。q 理解线索化二叉树的特性以及寻找某结点的前驱理解线索化二叉树的特性以及寻找某结点的前驱和后继的方法。和后继的方法。q 理解树、森林和二叉树间的相互转换规则。理解树、森林和二叉树间的相互转换规则。q 掌握哈夫曼树的实现方法，理解构造哈夫曼编码掌握哈夫曼树的实现方法，理解构造哈夫曼编码及带权路径长度的计算。及带权路径长度的计算。孙克雷制作6.1 树的基本概念树的基本概念v 什么是树？什么是树？树是由树是由 n(n 0)个结点的有限集合。如果个结点的有限集合。如果 n=0，称为空树；如果称为空树；如果 n 0，则则 有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的结点，它只有直的结点，它只有直接后继，但没有直接前驱；接后继，但没有直接前驱；当当n 1，除根以外的其它结点划分为除根以外的其它结点划分为 m(m 0)个互不个互不相交的有限集相交的有限集 T1,T2,Tm，其中每个集合本身又是一其中每个集合本身又是一棵树，并且称为根的子树棵树，并且称为根的子树(SubTree)。注注1：过去许多书籍中都定义树为：过去许多书籍中都定义树为n1，曾经有曾经有“空树不是空树不是树树”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具有递归性，即树中还有树。：树的定义具有递归性，即树中还有树。孙克雷制作T=A，B，C，D，E，F，G，H，I，J，K，L A是根，其余结点可以划分为是根，其余结点可以划分为3个互不相交的集合：个互不相交的集合：T1=B，E，F，K，L T2=C，G T3=D，H，I，J，M 这些集合中的每一集合都本身又是一棵树，它们是这些集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。对于对于T1，B是根，其余结点可以划分为是根，其余结点可以划分为2个互不相交的集合：个互不相交的集合：T11=E，K，L T12=F T11，T12是是B的子树。的子树。HBAJFEDKLCMIG&树的示例树的示例孙克雷制作1.树中只有根结点没有前驱；树中只有根结点没有前驱；2.除根外，其余结点都有且仅一个前驱；除根外，其余结点都有且仅一个前驱；3.树的结点，可以有零个或多个后继；树的结点，可以有零个或多个后继；4.除根外的其它结点，都存在唯一条从除根外的其它结点，都存在唯一条从根到该结点的路径；根到该结点的路径；5.树是一种分支结构树是一种分支结构(除了除了一个称为根的结点外一个称为根的结点外)每个每个元素都有且仅有一个直接前元素都有且仅有一个直接前趋，有且仅有零个或多个直趋，有且仅有零个或多个直接后继。接后继。HBAJFEDKLCMIG&树的逻辑结构特点树的逻辑结构特点孙克雷制作 树可表示具有分支结构关系的对象树可表示具有分支结构关系的对象例例1.家族族谱家族族谱 设某家庭有设某家庭有13个成员个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。他们之间的关系可如图所示的树表示。例例2.单位行政机构的组织关系单位行政机构的组织关系HBAJFEDKLCMIG&树的应用树的应用孙克雷制作 树是常用的数据组织形式树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。了便于管理和使用数据，将它们用树的形式来组织。例例3.计算机的文件系统计算机的文件系统 不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件文件系统，所有的文件是用树的形式来组织的。是用树的形式来组织的。文件夹文件夹1文件夹文件夹2文件文件1文件文件2文件夹文件夹11 文件夹文件夹11 文件文件11文件文件12C&树的应用树的应用孙克雷制作树的结点：树的结点：包含一个数据元素的包含一个数据元素的内容及若干指向子树的分支。内容及若干指向子树的分支。孩子结点：孩子结点：结点的子树的根称为结点的子树的根称为该结点的孩子；如该结点的孩子；如E是是B的孩子。的孩子。双亲结点：双亲结点：B结点是结点是A结点的孩子，结点的孩子，则则A结点是结点是B结点的双亲；如结点的双亲；如B是是E的双亲。的双亲。兄弟结点：兄弟结点：同一双亲的孩子结点；如同一双亲的孩子结点；如H、I、J互为兄弟。互为兄弟。堂兄结点：堂兄结点：同一层上结点；如同一层上结点；如G与与E、F、H、I、J互为堂兄。互为堂兄。祖先结点：祖先结点：结点的祖先是从根到该结点所经分支上的所有结点；结点的祖先是从根到该结点所经分支上的所有结点；如如H的祖先为的祖先为A、D。子孙结点：子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；以某结点为根的子树中的任一结点称为该结点的子孙；如如A的子孙为的子孙为B、C、D、E、F、G、H、I、J、K、L、M。HBAJFEDKLCMIG6.1.3 基本术语基本术语孙克雷制作结点的度：结点的度：结点子树的个数；结点子树的个数；如如D的度为的度为3。叶子结点：叶子结点：也叫终端结点，是也叫终端结点，是度为度为0的结点；如的结点；如K、L、F、G、M、I、J。分支结点：分支结点：度不为度不为0的结点；如的结点；如A、B、C、D结点层次：结点层次：根结点的层定义为根结点的层定义为1，根的孩子为第二层结点，依此，根的孩子为第二层结点，依此类推。类推。树的高度：树的高度：树中结点的最大层次；如图所示树的高度为树中结点的最大层次；如图所示树的高度为4。树的度：树的度：树中各结点的度的最大值；如图所示树的度为树中各结点的度的最大值；如图所示树的度为3。森林：森林：m(m=0)棵互不相交的树的集合；棵互不相交的树的集合；HBAJFEDKLCMIG&基本术语基本术语孙克雷制作1.双亲表示法：双亲表示法：以一组连续的空间存储树的结点，通过保存每个以一组连续的空间存储树的结点，通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。其类型结点的双亲结点的位置，表示树中结点之间的结构关系。其类型定义如下：定义如下：#define MAX_TREEE_SIZE 100typedef struct PTNode ElemType data;int parent;/双亲位置域双亲位置域 PTNode;typedef struct PTNode nodesMAX_TREE_SIZE;int n;/结点数结点数 Ptree;特点：找双亲容易，找孩子难特点：找双亲容易，找孩子难ARDCFEGBHKA0B0C0D1E1F3G6H6R-1K60123456789数组下标数组下标6.2 树的存储结构树的存储结构孙克雷制作 通过保存每个结点的孩子结点的位置，表示树中结点通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。之间的结构关系。v多重链表多重链表：每个结点有多个指针域，分别指向其子树的根。：每个结点有多个指针域，分别指向其子树的根。结点同构：结点的指针个数相等，为树的度结点同构：结点的指针个数相等，为树的度d。结点不同构：结点指针个数不等，为该结点的度结点不同构：结点指针个数不等，为该结点的度d。6.2.2 孩子表示法孩子表示法孙克雷制作v 孩子链表：其主体是一个与结点个数一样大小的一维数孩子链表：其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。每个结点的孩子结点用单链表存储，再指向下一个孩子。每个结点的孩子结点用单链表存储，再用含用含n个元素的结构数组指向每个孩子链表个元素的结构数组指向每个孩子链表。&孩子表示法孩子表示法孙克雷制作ARDCFEGBHKABCDEFGHRK0123456789数组下标数组下标125437896特点：找孩子容易，找双亲难特点：找孩子容易，找双亲难&孩子链表表示法图示孩子链表表示法图示孙克雷制作typedef struct CTNode /孩子结点孩子结点 int child;struct CTNode *next;*ChildPtr;typedef struct ElemType data;ChildPtr firstchild;/孩子链表头指针孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根的位置结点数和根的位置CTree;&孩子链表表示法类型定义孩子链表表示法类型定义孙克雷制作v 用二叉链表作树的存储结构，链表中每个结点的两个指用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。针域分别指向其第一个孩子结点和下一个兄弟结点。v 特点：操作容易，但破坏了树的层次。特点：操作容易，但破坏了树的层次。v 孩子兄弟表示法类型定义：孩子兄弟表示法类型定义：typedef struct CSNode ElemType data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;6.2.4 孩子兄弟表示法孩子兄弟表示法孙克雷制作ARDCFEGBHKR AD B EC F G H K 利用树的孩子兄弟链表这种存储结构便利用树的孩子兄弟链表这种存储结构便于实现各种树的操作。例如找某结点的第于实现各种树的操作。例如找某结点的第i个个孩子，则只要先从左指针域中找到第孩子，则只要先从左指针域中找到第1个孩个孩子结点上，然后沿着孩子结点的子结点上，然后沿着孩子结点的next域连续域连续走走i-1步便可找到第步便可找到第i个孩子。如增加一个个孩子。如增加一个parent域，则也能方便实现求双亲的操作。域，则也能方便实现求双亲的操作。&孩子兄弟表示法孩子兄弟表示法孙克雷制作6.3.1 二叉树的基本概念二叉树的基本概念 或为空树，或由根及至多两棵互不相交的左子树、右子树或为空树，或由根及至多两棵互不相交的左子树、右子树构成构成(即不存在度大于即不存在度大于2的结点的结点)，并且左、右子树本身也是，并且左、右子树本身也是二叉树。二叉树。说明：说明：1.二叉树中每个结点最多有两棵子二叉树中每个结点最多有两棵子树，二叉树每个结点度小于等于树，二叉树每个结点度小于等于2；2.左、右子树不能颠倒左、右子树不能颠倒有序树；有序树；3.二叉树是递归结构，在二叉树的定二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念。义中又用到了二叉树的概念。BADCFEG6.3 二叉树二叉树孙克雷制作 (a)(b)(c)(d)(e)(a)空树空树 (b)只含根结点只含根结点 (c)右子树为空树右子树为空树 (d)左右子树均不为空树左右子树均不为空树 (e)左子树为空树左子树为空树LLRR&二叉树的形态二叉树的形态孙克雷制作62175438910 1113 14 1512621754389 1011 122154367216543非完全二非完全二叉树叉树完全二完全二叉树叉树满满二二叉叉树树&两种特殊的二叉树两种特殊的二叉树孙克雷制作满二叉树：满二叉树：深度为深度为k的二叉树，有的二叉树，有2k-1个结点则称为满二叉个结点则称为满二叉树；树；完全二叉树：完全二叉树：如果深度为如果深度为k、由、由n个结点的二叉树中个结点个结点的二叉树中个结点能够与深度为能够与深度为k的顺序编号的满二叉树从的顺序编号的满二叉树从1到到n标号的结点相标号的结点相对应，则称为完全二叉树。对应，则称为完全二叉树。完全二叉树的特点是：完全二叉树的特点是：1.所有的叶结点都出现在第所有的叶结点都出现在第k层或层或k1层。层。2.对任一结点，如果其右子树的最大层次为对任一结点，如果其右子树的最大层次为l，则其左子则其左子树的最大层次为树的最大层次为 l 或或 l 1。&两种特殊的二叉树两种特殊的二叉树孙克雷制作性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i-1个结点。个结点。(i 1)证明用归纳法证明用归纳法证明：当证明：当i=1时，只有根结点，时，只有根结点，2 i-1=2 0=1。假设对所有假设对所有j，1ji，命题成立，即第命题成立，即第j层上至多有层上至多有2 j-1 个个结点。结点。由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i-2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在第，故在第i层上的最大结层上的最大结点数为第点数为第i-1层上的最大结点数的层上的最大结点数的2倍，即倍，即22i-2=2 i-1。6.3.2 二叉树的性质二叉树的性质孙克雷制作性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2 k-1个结点个结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度为k的二叉树的最大结点数为的二叉树的最大结点数为 20+21+2 k-1=2 k-1&二叉树的性质二叉树的性质孙克雷制作性质性质3 对任何一棵二叉树对任何一棵二叉树T，如果其叶结点数为如果其叶结点数为 n0，度为度为2的结点数为的结点数为 n2，则，则n0n21。证明：证明：设二叉树中度为设二叉树中度为1的结点数为的结点数为n1，二叉树中总结点数二叉树中总结点数为：为：nn0n1n2 二叉树中的分支数，除根结点外，其余结点都有一个二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设进入分支，设B为二叉树中的分支总数，为二叉树中的分支总数，则有：则有：nB1。由于这些分支都是由度为由于这些分支都是由度为1和和2的结点射出的，所以有：的结点射出的，所以有：Bn1+2 n2 ;nB1n12n21得到：得到：n0n21&二叉树的性质二叉树的性质孙克雷制作性质性质 4：具有：具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。证明：设完全二叉树的深度为证明：设完全二叉树的深度为 k，则根据性质则根据性质2和完全二叉和完全二叉树的定义有树的定义有2k-1-1 n 2k-1或或 2k-1 n 2k取对数取对数 k-1 1，则其双亲是结点则其双亲是结点 i/2 。2.如果如果2in，则结点则结点i为叶子结点，无左孩子；否则，其为叶子结点，无左孩子；否则，其左孩子是结点左孩子是结点2i。3.如果如果2i1n，则结点则结点i无右孩子；否则，其右孩子是结无右孩子；否则，其右孩子是结点点2i1。&二叉树的性质二叉树的性质孙克雷制作v 顺序存储结构顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：系，用编号的方法：#define MAX-TREE-SIZE 100 typedef TElemType SqBiTreeMAX-TREE-SIZE;6.3.3 二叉树的存储结构二叉树的存储结构孙克雷制作 通常是按照二叉树结点从上至下、从左到右的顺序存储，通常是按照二叉树结点从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系，只有通过一些方法确定某结点在逻辑在逻辑上的邻接关系，只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。依据二叉树上的前驱结点和后继结点，这种存储才有意义。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。标值确定结点在二叉树中的位置，以及结点之间的关系。&顺序存储结构顺序存储结构孙克雷制作FBAGEDCHIJKL例如：例如：bt3的双亲为的双亲为3/2=1，即在，即在bt1中；中；其左孩子在其左孩子在bt2i=bt6中；中；其右孩子在其右孩子在bt2i+1=bt7中。中。如何反映结点之如何反映结点之间的逻辑关系？间的逻辑关系？A1B2C3D4E5F6G7H8I9J10K11L12&完全二叉树的顺序表示完全二叉树的顺序表示孙克雷制作 一般二叉树也按完全二叉树形式存储，只有增添一些并不一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点存在的空结点(用用表示，表示，表示该处没有元素存在，仅仅为了表示该处没有元素存在，仅仅为了好理解好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。顺序存储。A1B2C3D45E6F7G8H910111213I14J15EBAFDCGHIJ例如对于例如对于B结点而言：结点而言：bt2的双亲为的双亲为1/2=1，即在，即在bt1中中(为为A)；其左孩子在其左孩子在bt2i=bt4中中(为为D)；其右孩子在其右孩子在bt2i+1=bt5中中(为为)。&一般二叉树的顺序表示一般二叉树的顺序表示孙克雷制作 这种存储结构适合于完全二叉树，既不浪费存储空间，这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪子的存放位置，但对一般二叉树，可能造成存储空间的浪费。费。例如，深度为例如，深度为k，且只有且只有k个结点的右单枝树个结点的右单枝树(每个非叶每个非叶结点只有右孩子结点只有右孩子)，也需，也需2k-1个个单元，即有单元，即有(2k-1)-k个单元个单元被浪费。被浪费。12k&顺序存储的优缺点顺序存储的优缺点孙克雷制作 所谓链式存储是指，用链表来表示一棵二叉树，即用所谓链式存储是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表来存储。链来指示着元素的逻辑关系。通常采用二叉链表来存储。链表中每个结点由三个域组成，除了数据域外，还有链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左右孩子所在的结点的两个指针域，分别用来给出该结点左右孩子所在的结点的存储地址。其定义如下：存储地址。其定义如下：typedef struct BiTNode ElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;&链式存储结构链式存储结构孙克雷制作 D A B C E F Tlchilddatarchild结点结构结点结构BADCEF&二叉链表二叉链表孙克雷制作 A B C D E F G三叉链表图示三叉链表图示BACDEFG&三叉链表三叉链表lchild data结点结构结点结构parent rchild孙克雷制作6.4 二叉树的遍历和线索二叉树的遍历和线索6.4.1 二叉树的遍历二叉树的遍历v定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。中的所有结点，使得每个结点仅被访问一次。这里所提的这里所提的“访问访问”的含义很广，可以是查询、修改、的含义很广，可以是查询、修改、输出某元素的值，以及对元素作某种运算等等。但要求这输出某元素的值，以及对元素作某种运算等等。但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。但对单，只须从开始结点出发，顺序扫描每个结点即可。但对二叉树这样的非线性结构，每个结点可能有两个后继结点，二叉树这样的非线性结构，每个结点可能有两个后继结点，因此需要寻找一种规律来系统访问树中的各结点。因此需要寻找一种规律来系统访问树中的各结点。如何访问二叉树的每个结点且如何访问二叉树的每个结点且每个结点仅被访问一次？每个结点仅被访问一次？孙克雷制作 由二叉树的定义是递归的，它是由三个基本单元组成，即由二叉树的定义是递归的，它是由三个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍历题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。右子树，只要依次遍历这三部分，就可以遍历整个二叉树。由于实际问题一般都是要求左子树较右子树先遍历，分由于实际问题一般都是要求左子树较右子树先遍历，分别称为先序遍历、中序遍历和后序遍历。别称为先序遍历、中序遍历和后序遍历。令令L，R，D分别代表二叉树的左子树、右子树、根结点，分别代表二叉树的左子树、右子树、根结点，则有则有DLR、LDR、LRD三种遍历规则。三种遍历规则。&递归实现方法递归实现方法孙克雷制作若二叉树非空，则：若二叉树非空，则：1.访问根结点访问根结点 2.先序遍历左子树先序遍历左子树 3.先序遍历右子树先序遍历右子树BADCD L RAD L RD L RBDCD L R得到的序列为：得到的序列为：A B D C&先序遍历二叉树先序遍历二叉树孙克雷制作Status PreOrderTraverse(BiTree T)/采用二叉链表存贮二叉树采用二叉链表存贮二叉树 if(T)/若二叉树不为若二叉树不为空空 Visit(T-data)；/访问根结点访问根结点 PreOrderTraverse(T-lchild);/先序遍历先序遍历T的左子树的左子树 PreOrderTraverse(T-rchild);/先序遍历先序遍历T的右子树的右子树 /PreOrderTraverse&先序遍历二叉树算法实现先序遍历二叉树算法实现孙克雷制作若二叉树非空，则：若二叉树非空，则：1.中序遍历左子树中序遍历左子树 2.访问根结点访问根结点 3.中序遍历右子树中序遍历右子树BADCL D RBL D RL D RADCL D R得到的序列为：得到的序列为：B D A C&中序遍历二叉树中序遍历二叉树孙克雷制作若二叉树非空，则：若二叉树非空，则：1.后序遍历左子树后序遍历左子树 2.访问根结点访问根结点 3.后序遍历右子树后序遍历右子树BADC L R DL R DL R DADCL R DB得到的序列为：得到的序列为：D B C A&后序遍历二叉树后序遍历二叉树孙克雷制作void leaf(BiTree T)/采用二叉链表存贮二叉树，采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的为全局变量，用于累加二叉树的叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结点的个数，初始化点的个数，初始化n=0if(T)if(T-lchild=NULL&T-rchild=NULL)n+=1;/若若T所指结点为叶子结点则计数所指结点为叶子结点则计数 leaf(T-lchild);leaf(T-rchild);/if /leaf 例例 编写求二叉树的叶子结点个数的算法编写求二叉树的叶子结点个数的算法孙克雷制作输入：二叉树的先序序列输入：二叉树的先序序列结果：二叉树的二叉链表结果：二叉树的二叉链表问题：遍历操作访问二叉树的每个结问题：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是点，而且每个结点仅被访问一次。是否可利用遍历，建立二叉链表的所有否可利用遍历，建立二叉链表的所有结点并完成相应结点的链接？结点并完成相应结点的链接？基本思想：输入在空子树处添加字符基本思想：输入在空子树处添加字符的二叉树的按先序遍历的顺序，建的二叉树的按先序遍历的顺序，建立二叉链表的所有结点并完成相应结立二叉链表的所有结点并完成相应结点链接。点链接。BADCEF在空子树处添加的二在空子树处添加的二叉树的先序序列：叉树的先序序列：A B D F E C 例例 建立二叉链表建立二叉链表孙克雷制作Status CreateBiTree(BiTree&T)/输入输入(在空子树处添加字符的二叉树的在空子树处添加字符的二叉树的)先序序列先序序列(设元素均设元素均为字符为字符)scanf(&ch);if(ch=)T=NULL;/若若ch=则表示空则表示空子树子树 else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/建立建立(根根)结点结点 CreateBiTree(T-lchild);/递归构造左子树链表递归构造左子树链表 CreateBiTree(T-rchild);/递归构造右子树链表递归构造右子树链表 return OK;/CreateBiTree 例例 建立二叉链表建立二叉链表孙克雷制作遍历是二叉树最基本最常用的操作。遍历是二叉树最基本最常用的操作。1.对二叉树所有结点做某种处理可在遍历过程中实现；对二叉树所有结点做某种处理可在遍历过程中实现；2.查找二叉树某个结点，可通过遍历实现；查找二叉树某个结点，可通过遍历实现；与线性表相比，对二叉树的遍历存在如下问题：与线性表相比，对二叉树的遍历存在如下问题：1.遍历算法要复杂的多，费时的多；遍历算法要复杂的多，费时的多；2.为查找二叉树中某结点在某种遍历下的后继，必须从根为查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；开始遍历，直到找到该结点及后继；如果能将二叉树线性化，就可以减化遍历算法，提高如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。遍历速度。6.4.2 线索二叉树线索二叉树孙克雷制作定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点的任一序列的前驱与后继信息，这种信息只有在遍而不能直接得到结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域。历的动态过程中才能得到，为了能保存所需的信息，可增加标志域。0 lchild 域指示结点的左孩子域指示结点的左孩子 1 lchild 域指示结点的前驱域指示结点的前驱 0 rchild 域指示结点的右孩子域指示结点的右孩子 1 rchild 域指示结点的后继域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做表，其中指向结点前驱与后继的指针叫做线索线索。加上线索的二叉树称之。加上线索的二叉树称之为为线索二叉树线索二叉树。LTaglchilddatarchildRTagLTag=RTag=&线索二叉树定义线索二叉树定义孙克雷制作 利用现有的空指针域利用现有的空指针域，每个，每个n个结点的二叉链表，有个结点的二叉链表，有n+1个空指针域，故可利用这些的空指针域存放结点的前趋个空指针域，故可利用这些的空指针域存放结点的前趋和后继指针。和后继指针。(n个结点共有个结点共有2n个链域，而每个结点个链域，而每个结点(除根结点外除根结点外)都有一个分支指向，则共有都有一个分支指向，则共有n-1个分支，其中每个分支占有一个个分支，其中每个分支占有一个链域，所以空链域为链域，所以空链域为2n-(n-1)=n+1。)v 若结点有左子树，则左指针若结点有左子树，则左指针lchild指示其左孩子指示其左孩子(LTag=0)；否则，令左指针指示其前驱否则，令左指针指示其前驱(LTag=1)；v 若结点有右子树，则右指针若结点有右子树，则右指针rchild指示其右孩子指示其右孩子(RTag=0)；否则，令右指针指示其后继否则，令右指针指示其后继(RTag=1)。&如何保存遍历过程中得到的信息？如何保存遍历过程中得到的信息？孙克雷制作typedef enum PointerTeg Link,Thread;/Link=0:指针，指针，Thread=1:线索线索typedef struct BiThrNod TElemType data;struct BiThrNode *lchild,*rchild;/左右指针左右指针 PointerTeg LTag,RTag;/左右标志左右标志 BiThrNode,*BiThrTree;&线索链表的类型描述线索链表的类型描述孙克雷制作(以中序遍历为例以中序遍历为例)v 查找任意结点的前驱结点查找任意结点的前驱结点 如如果果该该结结点点的的左左标标志志为为1，那那么么其其左左指指针针域域所所指指向向的的结结点点便便是是它它的的前前驱驱结结点点；如如果果该该结结点点的的左左标标志志为为0，表表明明该该结结点点有有左左孩孩子子，根根据据中中序序遍遍历历的的定定义义，它它的的前前驱驱结结点点是是以以该该结结点点的的左左孩孩子子为为根根结结点点的的子子树树的的最最右右结结点点，即即沿沿着着其其左左子子树树的的右右指指针针链链向向下下查查找找，当当某某结结点点的的右右标标志志为为1时时，它它就就是是所所要要找找的前驱结点。的前驱结点。中序线索二叉树中序线索二叉树中序：中序：DBGJEACHLKFI&如何找结点的前驱和后继如何找结点的前驱和后继BACEFDGJHIKL孙克雷制作中序线索二叉树中序线索二叉树中序：中序：DBGJEACHLKFI&如何找结点的前驱和后继如何找结点的前驱和后继BACEFDGJHIKL(以中序遍历为例以中序遍历为例)v 查找任意结点的后继结点查找任意结点的后继结点 对对任任意意结结点点p，若若右右标标志志为为1，则则rchild指指向向该该结结点点的的后后继继；若若右右标标志志为为0，则则rchild指指向向该该结结点点的的右右孩孩子子，此此时时，应应从从右右孩孩子子开开始始，沿沿左左指指针针前前进进，直直到到找找到到没没有有左左孩孩子子的的结结点点s(Ltag=1)，则则s就就是是p的的后后继继，即即后后继继是是中中序序遍遍历右子树时，访问的第一个结点。历右子树时，访问的第一个结点。孙克雷制作 按不同的方式遍历二叉树所得到的线索二叉树是不相按不同的方式遍历二叉树所得到的线索二叉树是不相同的。同的。BADCE&遍历线索二叉树遍历线索二叉树 A B D C ET先序序列：先序序列：ABCDE先序线索二叉树先序线索二叉树00001111 11 A B D C ET中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树0000111111 A B D C ET后序序列：后序序列：CBEDA后序线索二叉树后序线索二叉树0000111111孙克雷制作BADCE A B D C ET0000111111 01中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树&遍历线索二叉树遍历线索二叉树v 带头结点的线索二叉树带头结点的线索二叉树 在在存存储储线线索索二二叉叉树树时时往往往往增增设设一一头头结结点点，其其数数据据域域不不存存放放信信息息，其其左左指指针针域域指指向向二二叉叉树树的的根根结结点点，右右指指针针域域指指向向某某种种遍遍历历时时访访问问的的最最后后一一个个结结点点。而而原原二二叉叉树树在在某某序序遍遍历历下下的的第第一一个个结结点点的的前前驱驱线线索索和和最最后后一一个个结结点点的的后后继继线线索索都都指向该头结点。指向该头结点。孙克雷制作v 找遍历的第一个结点找遍历的第一个结点 左子树上处于左子树上处于“最左下最左下”(没有左子树没有左子树)的结点。的结点。v 不断地找遍历到的结点的后继结点，直到树中各结点都不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束遍历到为止，结束 若无右子树，则为后继线索所指结点；否则为对其右若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。子树进行中序遍历时访问的第一个结点。&遍历线索二叉树步骤遍历线索二叉树步骤孙克雷制作void InOrderTraverse_Thr(BiThrTree T)p=T-lchild;while(p!=T)while(p-LTag=0)p=p-lchild;Visit(p-data);while(p-RTag=1&p-rchild!=T)p=p-rchild;Visit(p-data);p=p-rchild;/InOrderTraverse_Thr中序线索二叉树中序线索二叉树中序：中序：DBGJEACHLKFI&中序遍历线索二叉树算法实现中序遍历线索二叉树算法实现TBACEFDGJHIKL孙克雷制作6.5.1 树转变为二叉树树转变为二叉树 加线：在兄弟之间加一连线；加线：在兄弟之间加一连线；抹线：对每个结点，除了其左孩子外，去除其与其余孩抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系；子之间的关系；旋转：以树的根结点为轴心，将整树顺时针转旋转：以树的根结点为轴心，将整树顺时针转45。6.5 树、森林与二叉树树、森林与二叉树孙克雷制作BAEDGHCFIBAEDGHCFIBAEDGHCFIBAEDGHCFIBAEDGHCFI 由上面的转换可以看出，在二叉树中，左分支上的各由上面的转换可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。换后的二叉树的根结点的右孩子必为空。树转变为二叉树实现过程树转变为二叉树实现过程孙克雷制作 由森林的概念可知，森林是若干棵树的集合，只要将由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，这样，森林也同样可以用二叉树表示。具体的方法如下：这样，森林也同样可以用二叉树表示。具体的方法如下：l 将各棵树分别转换成二叉树；将各棵树分别转换成二叉树；l 将每棵树的根结点用线相连；将每棵树的根结点用线相连；l 以第一棵树根结点为二叉树的根，再以根结点为轴心，以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。顺时针旋转，构成二叉树型结构。6.5.2 森林转换成二叉树森林转换成二叉树孙克雷制作HIGJBADCEFHIGJBADCEFHIGJBADCEFHIGMBADCEF森林转变为二叉树实现过程森林转变为二叉树实现过程孙克雷制作 加线：若加线：若p结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将p的右孩子，右孩的右孩子，右孩 子子的右孩子，的右孩子，沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与p 的双亲用线的双亲用线连起来连起来；抹线：抹掉原二叉树中双亲与右孩子之间的连线；抹线：抹掉原二叉树中双亲与右孩子之间的连线；调整：将结点按层次排列，形成树结构。调整：将结点按层次排列，形成树结构。BAEDGHCFIBAEDGHCFIBAEDGHCFI注：该注：该二叉树的右子