《数据结构 树和二叉树.pptx》由会员分享，可在线阅读，更多相关《数据结构 树和二叉树.pptx（104页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、7.1 树的基本概念树的基本概念(教材第教材第教材第教材第8 8章章章章)7.1.1 7.1.1 树的定义树的定义 树（树（TreeTree）是）是n n（n0n0）个结点的有限集合。在任意）个结点的有限集合。在任意一棵非空树中：一棵非空树中：（1 1）有且仅有一个特定的称为根（）有且仅有一个特定的称为根（RootRoot）的结点；）的结点；（2 2）当）当n n 1 1时，其余结点可分为时，其余结点可分为m m（m m 0 0）个互不相）个互不相交的有限集合交的有限集合T T1 1，T T2 2，T Tm m，其中每一个集合本身又，其中每一个集合本身又是一棵树，并且称为根的子树（是一棵树，并
2、且称为根的子树（SubtreeSubtree）。）。第1页/共104页树形结构示例树形结构示例 ACDIHGBFEMJKLA只有一个根结点的树只有一个根结点的树这是一个这是一个有有13个结点的树，其中个结点的树，其中A是根结点，其是根结点，其余结点分成三个互不相交的结点的子集：余结点分成三个互不相交的结点的子集：T1=B，E，F，K，L，T2=C，G，T3=D，H，I，J，M。T1、T2、T3都是都是A的子树，且它们本身也是一棵树的子树，且它们本身也是一棵树第2页/共104页树的基本术语 结点的度：结点的度：一个结点所拥有的一个结点所拥有的子树子树的的个数个数。例：例：结点结点A的度为的度为3
3、，结点，结点E的度为的度为2，结点，结点M的度为的度为0。树的度：树中所有结点的度的最大值。即MAX结点的度。例：右图所示树的度为3。ACDIHGBFEMJKL第3页/共104页树的基本术语 叶子结点：叶子结点：度为度为0 0的结点称为叶子的结点称为叶子结点或终端结点。结点或终端结点。例：右图所示树中的例：右图所示树中的结点结点K K、L L、F F、G G、M M、I I、J J为叶子结点。为叶子结点。ACDIHGBFEMJKL分支结点：分支结点：度不为度不为0 0的结点称为非的结点称为非终端结点或分支结点。除终端结点或分支结点。除根结点外，分支结点也称根结点外，分支结点也称为内部结点。为内
4、部结点。第4页/共104页树的基本术语树的基本术语 孩子结点和孩子结点和父父结点（双亲结点）：结点（双亲结点）：一个结点的子树的根称为该结一个结点的子树的根称为该结点的孩子（点的孩子（Child）。相应的，该）。相应的，该结点称为孩子的双亲（结点称为孩子的双亲（ParentsParents）或父结点。或父结点。ACDIHGBFEMJKL兄弟结点：兄弟结点：同一个双亲的孩子之间同一个双亲的孩子之间互称为兄弟（互称为兄弟（SiblingSibling）。）。第5页/共104页树的基本术语 ACDIHGBFEMJKL祖先结点：从根到一个结点的路径上的所有结点称为该结点的祖先结点。子孙结点：以某结点为
5、根的子树中的所有结点都是该结点的子孙。第6页/共104页树的基本术语 树的深度树的深度 树中所有结点的层次的最大值树中所有结点的层次的最大值称为树的深度或高度。即称为树的深度或高度。即MAXMAX结点结点的层次的层次。例：例：右图所示树的深度为右图所示树的深度为4 4。ACDIHGBFEMJKL结点的层次：结点的层次：一棵树从根开始定义，根为第一棵树从根开始定义，根为第一层，根的孩子为第二层，一层，根的孩子为第二层，依，依此类推。若某结点在第此类推。若某结点在第i i层，则其层，则其子树的根就在第子树的根就在第i i1 1层。层。第7页/共104页树的基本术语 森林（Forest）：m（m0）
6、棵互不相交的树的集合称为森林。对树中每个结点而言，其子树的集合即为森林。CDIHGBFEMJKL第8页/共104页课堂思考 u下面两个叙述是否正确？下面两个叙述是否正确？1.1.根结点也可以是叶子结点。根结点也可以是叶子结点。2.2.度为度为0 0的结点就是叶子结点。的结点就是叶子结点。u判断右边判断右边(a)(a)、(b)(b)所示所示图形是否图形是否树？树？BFEKLCDHGMJ(b)(a)第9页/共104页因为树是一种非线性结构，所以不能简单地用一维数组或单链因为树是一种非线性结构，所以不能简单地用一维数组或单链表来存储树。为了存储树，必须把树中每个结点之间存在的关系反表来存储树。为了存
7、储树，必须把树中每个结点之间存在的关系反映在存储结构之中，才能如实的表现一棵树。映在存储结构之中，才能如实的表现一棵树。树的存储结构有多种表示方法，下面介绍常用的三种。树的存储结构有多种表示方法，下面介绍常用的三种。7.2 树的存储结构树的存储结构(教材第教材第教材第教材第8 8章章章章)7.2.1 7.2.1 双亲表示法双亲表示法这这种种表表示示法法要要求求用用一一维维数数组组来来存存储储树树的的有有关关信信息息，每每个个结结点点对对应应一一个个数数组组元元素素，它它包包含含两两个个域域：一一个个是是数数据据域域（datadata），存存放放该该结结点点所所包包含含的的数数据据；一一个个是是
8、指指针针域域（parentparent），指指出出该该结结点点的的双双亲结点的位置（整数）。亲结点的位置（整数）。第10页/共104页RBCFHAEDGK0R-11A02B03C04D15E16F37G68H69K6数据域数据域指针域指针域在树的双亲表示法在树的双亲表示法中，求某个结点的双亲中，求某个结点的双亲结点是非常容易的，但结点是非常容易的，但求某个结点的孩子结点求某个结点的孩子结点比较困难，需要比较困难，需要遍历整遍历整个结构个结构。第11页/共104页7 7.2.2.2.2 孩子表示法孩子表示法方法之一：把每个结点的孩子结点排列起来，构成一个单链表，方法之一：把每个结点的孩子结点排列
9、起来，构成一个单链表，则则n n个结点有个结点有n n个孩子链表（叶子结点的孩子链表为空）。而个孩子链表（叶子结点的孩子链表为空）。而n n个头指个头指针又组成一个线性表，采用顺序存储结构存储。每个结点只要掌握针又组成一个线性表，采用顺序存储结构存储。每个结点只要掌握了这个单链表的表头，就容易找到它的全部孩子。了这个单链表的表头，就容易找到它的全部孩子。0R1A2B3C4D5E6F7G8H9K716245893RBCFHAEDGK第12页/共104页7 7.2.2.2.2 孩子表示法孩子表示法在树的孩子表示法中，寻找任意结点的孩子是比较容易的，但在树的孩子表示法中，寻找任意结点的孩子是比较容易
10、的，但寻找它的双亲却比较困难。我们可以将双亲表示法和孩子表示法合寻找它的双亲却比较困难。我们可以将双亲表示法和孩子表示法合在一起。在一起。0-1R10A20B30C41D51E63F76G86H96K716245893RBCFHAEDGK第13页/共104页 7 7.2.2.3 3 孩子兄弟表示法孩子兄弟表示法 又又称称为为二二叉叉链链表表表表示示法法(或或二二叉叉树树表表示示法法)。即即以以二二叉叉链链表表作作为为树树的的存存储储结结构构，链链表表中中每每个个结结点点设设有有两两个个链链域域，一一个个指指向向该该结结点点的的第第一一个个孩孩子子，一一个个指指向向该该结结点点的的下下一一个个兄
11、兄弟弟结结点点。结结点点类类型型定义如下：定义如下：struct node anytype data；struct node *firstchild，*nextsibling；第14页/共104页7.3 二叉树7.3.1 7.3.1 二叉树的定义和性质二叉树的定义和性质1二叉树的定义二叉树的定义 二叉树二叉树的特点是每个结点至多只有两棵子树（即二叉树中不的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于存在度大于2 2的结点），并且，二叉树的子树有左右之分，其次序的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树有五种基本形态：不能任意颠倒。二叉树有五种基本形态：二叉树二
12、叉树（Binary treeBinary tree）是树形结构中一种最典型、最常用的）是树形结构中一种最典型、最常用的结构，处理起来也比一般树简单，因此，在实际应用中，通常将一结构，处理起来也比一般树简单，因此，在实际应用中，通常将一般树形结构转化为二叉树进行处理。般树形结构转化为二叉树进行处理。第15页/共104页2二叉树的基本性质二叉树的基本性质 性质性质1 1 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点（个结点（i1i1）。）。第一层21-1第二层22-1第三层23-1ACFBEDK第16页/共104页2二叉树的基本性质二叉树的基本性质 性质性质2 2 深
13、度为深度为k k的二叉树至多有的二叉树至多有2 2k k1 1个结点个结点(k1)(k1)。深度121-1深度222-1深度323-1ACFBEDK第17页/共104页2二叉树的基本性质二叉树的基本性质 性质性质3 3 对任何一棵二叉树对任何一棵二叉树T T，设，设n n0 0、n n2 2分别是叶子结点个数分别是叶子结点个数 和度为和度为2 2的结点个数，则：的结点个数，则：n n0 0n n2 21 1。n0：3n2：2ACFBED第18页/共104页证明：证明：在二叉树中有在二叉树中有 n n0 0n n2 21 1。从结点的度来看，二叉树中只有三种结点：度为从结点的度来看，二叉树中只有
14、三种结点：度为0 0、1 1、2 2的结点。的结点。假设二叉树中，度为假设二叉树中，度为0 0的结点有的结点有n n0 0个，个，度为度为1 1的结点有的结点有n n1 1个，度为个，度为2 2的的结点有结点有n n2 2个，则结点总数：个，则结点总数：n=n0+n1+n2 -(1)二叉树中除根结点外，其余结点都由分支引入，则二叉树中除根结点外，其余结点都由分支引入，则 n=n=1 1+分支总数分支总数 -(2)分支总数分支总数与结点的度有关与结点的度有关：度为：度为0 0的结点不发出分支；一个度为的结点不发出分支；一个度为1 1的结的结点发出点发出1 1条分支，则度为条分支，则度为1 1的结
15、点共发出分支的结点共发出分支n n1 1*1*1条。条。一个度为一个度为2 2的结点发出的结点发出2 2条分支，则度为条分支，则度为2 2的结点共发出分支的结点共发出分支n n2 2*2*2条。条。分支总数分支总数=n=n1 1*1*1+n n2 2*2 *2 -(3)由（由（2 2）、（）、（3 3）得：）得：n=1+n1 1*1+n2 2*2 -(4)由（由（1 1）、（）、（4 4）得：）得：n n0 0+n+n1 1+n+n2 2=1 1+n n1 1*1*1+n+n2 2*2 *2 即：即：n0 0=n2 2+1+1第19页/共104页课堂练习 设树设树T T的度为的度为4 4，其中
16、度为，其中度为1 1、2 2、3 3、4 4的结点个数分别为的结点个数分别为4 4、2 2、1 1、1 1。问。问T T中有中有多少个叶子结点？多少个叶子结点？答案答案 树的分支数为树的分支数为15，结点数，结点数=分支数分支数+1=16 叶子结点的个数叶子结点的个数=16-8=8个个第20页/共104页满二叉树与完全二叉树满二叉树与完全二叉树 m(深度)：3，结点数：2m-1=7一棵深度为一棵深度为k k且有且有2 2k k1 1个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。ACFBEDK满二叉树的特点：满二叉树的特点：每一层上的结点数都是最大结点数。每一层上的结点数都是最大结点数。
17、第21页/共104页深深度度为为k k的的、有有n n个个结结点点的的二二叉叉树树，当当且且仅仅当当其其每每一一个个结结点点都都与与深深度度为为k k的的满满二二叉叉树树中中编编号号从从1 1至至n n的的结结点点一一一一对对应应时，称之为时，称之为完全二叉树完全二叉树。满二叉树与完全二叉树满二叉树与完全二叉树 ACFBEDK1234567完全二叉树的特点：完全二叉树的特点：1)1)叶叶子子结结点点只只可可能能在在层层次次最最大的两层上出现。大的两层上出现。2)2)对对任任一一结结点点，若若其其右右分分支支的的子子孙孙的的最最大大层层次次为为L L，则则其其左左分分支支的的子子孙孙的的最最大大
18、层层次次为为L L或或L+1L+1。3)3)满满二二叉叉树树一一定定是是完完全全二二叉叉树，反之不成立。树，反之不成立。第22页/共104页2二叉树的基本性质二叉树的基本性质 性质性质4 4 具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n 1 1。假设二叉树的深度为假设二叉树的深度为k k，则根据性质，则根据性质2 2和完全二叉和完全二叉树的定义有：树的定义有：2 2k-1k-1-1n2-1n2k k-1-1 或或 2 2k-1k-1n2n2k k 于是于是 k-1logk-1log2 2nkndata=ch;t-lchild=creattree(
19、);/*建立它的左子树的二叉链表建立它的左子树的二叉链表*/t-rchild=creattree();/*建立它的右子树的二叉链表建立它的右子树的二叉链表*/return t;生成二叉树链表的算法生成二叉树链表的算法:第33页/共104页 7.4 二叉树的遍历所谓遍历二叉树（所谓遍历二叉树（Traversing Binary TreeTraversing Binary Tree），），就是指按一定的规则和次序访问树中的每个结点，使每就是指按一定的规则和次序访问树中的每个结点，使每个结点被访问且仅只被访问一次。个结点被访问且仅只被访问一次。遍历二叉树是以一定规则将二叉树中的结点排列成遍历二叉树是
20、以一定规则将二叉树中的结点排列成一个线性序列一个线性序列。实质上是对一个非线性结构进行线性化。实质上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个之外）在这些操作，使每个结点（除第一个和最后一个之外）在这些线性序列中有且仅有一个直接前趋和直接后继。线性序列中有且仅有一个直接前趋和直接后继。第34页/共104页 7.4.1 7.4.1 二叉树的先根遍历二叉树的先根遍历(先序法先序法)若二叉树为空，则返回。否则：若二叉树为空，则返回。否则：（1 1）访问根结点；）访问根结点；（2 2）先根遍历左子树；）先根遍历左子树；（3 3）先根遍历右子树；）先根遍历右子树；（4 4）返回。）
21、返回。例如，对下图(a)所示的二叉树进行先根遍历所得到的先根次序的结点序列是ABCDEF。同一先根序列可对应多棵二叉树。例如，图(b)所示的二叉树的先根序列仍然是ABCDEF。可见，由先根序列不能唯一确定二叉树。第35页/共104页 void preorder(struct node *t)/*t为指向二叉树根结点的指针*/if(t!=NULL)visit(t-data)；/*printf(“%c”,t-data);*/preorder(t-lchild);preorder(t-rchild);先根遍历的递归算法如下：第36页/共104页void preorder(struct node*bt
22、)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;ABEC遍历算法遍历算法bt第37页/共104页ABEC遍历算法遍历算法btAvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第38页/共104页ABEC遍历算法遍历算法btAvoid preorder(struct node*bt)if(bt!=NULL)print
23、f(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第39页/共104页ABEC遍历算法遍历算法btAvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第40页/共104页ABEC遍历算法遍历算法btA Bvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lc
24、hild);preorder(bt-rchild);return;第41页/共104页ABEC遍历算法遍历算法btA Bvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第42页/共104页ABEC遍历算法遍历算法bt：A Bvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);r
25、eturn;第43页/共104页ABEC遍历算法遍历算法btA Bvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第44页/共104页ABEC遍历算法遍历算法bt：A Bvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第45页/共104页ABEC遍历算法遍历算
26、法btA Bvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第46页/共104页ABEC遍历算法遍历算法btA Bvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第47页/共104页ABEC遍历算法遍历算法btA B Evoid preorder(struct
27、 node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第48页/共104页ABEC遍历算法遍历算法btA B Evoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第49页/共104页ABEC遍历算法遍历算法btA B Evoid preorder(struct node*bt)if(bt!=NULL)pri
28、ntf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第50页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第51页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);pr
29、eorder(bt-lchild);preorder(bt-rchild);return;第52页/共104页ABEC遍历算法遍历算法bt:A B E Cvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第53页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);p
30、reorder(bt-rchild);return;第54页/共104页ABEC遍历算法遍历算法bt:A B E Cvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第55页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);
31、return;第56页/共104页ABEC遍历算法遍历算法bt:A B E Cvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第57页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node*bt)if(bt!=NULL)printf(“%d”,bt-data);preorder(bt-lchild);preorder(bt-rchild);return;第58页/共104页7.
32、4.2 7.4.2 二叉树的中根遍历二叉树的中根遍历(中序法中序法)若二叉树为空，则返回。否则：若二叉树为空，则返回。否则：（1 1）中根遍历左子树；）中根遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）中根遍历右子树；）中根遍历右子树；（4 4）返回。）返回。例如，对下图(a)所示的二叉树进行中根遍历所得到的中根序列是ABCDEF。同一中根序列可对应多棵二叉树。例如，图(b)所示的二叉树的中根序列仍然是ABCDEF。可见，由中根序列不能唯一确定二叉树。第59页/共104页 中中根遍历的递归算法根遍历的递归算法:voidinorder(structnode*t)/*t为指向二叉树根结
33、构的指针为指向二叉树根结构的指针*/if(t!=NULL)inorder(t-lchild);visit(t-data);/*printf(“%c”,t-data);*/inorder(t-rchild);7.4.2 7.4.2 二叉树的中根遍历二叉树的中根遍历第60页/共104页 7.4.3 7.4.3 二叉树的后根遍历（后序法）二叉树的后根遍历（后序法）若二叉树为空，则返回。否则：若二叉树为空，则返回。否则：（1 1）按后根次序遍历左子树；）按后根次序遍历左子树；（2 2）按后根次序遍历右子树；）按后根次序遍历右子树；（3 3）访问根结点；）访问根结点；（4 4）返回。）返回。例如，对下图
34、(a)所示的二叉树进行后根遍历所得到的后根序列是ABCDEF。同一后根序列可对应多棵二叉树。例如，图(b)所示的二叉树的后根序列仍然是ABCDEF。可见，由后根序列不能唯一确定二叉树。第61页/共104页 7.4.3 7.4.3 二叉树的后根遍历二叉树的后根遍历void postorder(struct node *t)if(t!=NULL)postorder(tlchild)；postorder(trchild)；visit(tdata)；/*printf(“%c”,t-data);*/后根遍历的递归算法：第62页/共104页例 已知某二叉树的前根序列为ABCDEFG，中根序列为CBDAEF
35、G。求该二叉树的后根序列。由前根序列可以推断：A是二叉树的根结点。根据中根遍历的规则可知：在中根序列中，A左侧的C、B、D三个结点构成了A的左子树，而A右侧的E、F、G三个结点构成了A的右子树。A的左子树：前根序列为BCD，中根序列为CBD。A的右子树：前根序列为EFG，中根序列为EFG。此时，确定的二叉树如右图所示。A的左子树：根结点：B B的左子树：仅包含C，即C是B的左孩子。B的右子树：仅包含D，即D是B的右孩子。A的左子树分析完毕。如右图所示。第63页/共104页A的右子树：根结点：E E的左子树：空。E的右子树：前序序列为FG，中序序列为FG。如下左图所示。根结点：F F的左子树：空
36、。F的右子树：仅包含G，即G是F的右孩子。E的右子树分析完毕。A的右子树分析完毕。如下右图所示。二叉树的后根序列:CBDGFEA第64页/共104页 7.4.4 7.4.4 二叉树操作实例#includealloc.h#includestdio.hstructnodechardata;structnode*lchild;structnode*rchild;structnode*creattree()/*建立二叉链表建立二叉链表*/charch;structnode*t;scanf(%c,&ch);if(ch=#)t=NULL;elset=(structnode*)malloc(sizeof(s
37、tructnode);if(t=NULL)printf(outofmemoryn);exit(0);t-data=ch;t-lchild=creattree();t-rchild=creattree();returnt;第65页/共104页voidpreorder(structnode*t)/*前根遍历二叉树前根遍历二叉树*/if(t!=NULL)printf(%3c,t-data);preorder(t-lchild);preorder(t-rchild);voidinorder(structnode*t)/*中根遍历二叉树中根遍历二叉树*/if(t!=NULL)inorder(t-lchi
38、ld);printf(%3c,t-data);inorder(t-rchild);voidpostorder(structnode*t)/*后根遍历二叉树后根遍历二叉树*/if(t!=NULL)postorder(t-lchild);postorder(t-rchild);printf(%3c,t-data);第66页/共104页void main()struct node*root;printf(建立二叉树建立二叉树,按先根次序输入结点序列按先根次序输入结点序列n);root=creattree();printf(n先根遍历次序为先根遍历次序为:n);preorder(root);getch
39、ar();printf(n中根遍历次序为中根遍历次序为:n);inorder(root);printf(n后根遍历次序为后根遍历次序为:n);postorder(root);getchar();第67页/共104页7.5 线索树7.5.1 7.5.1 线索树的结构线索树的结构一个有一个有n n个结点的二叉树，其二叉链表共有个结点的二叉树，其二叉链表共有2n2n个指针域，其中个指针域，其中用于指向孩子结点（左、右子树用于指向孩子结点（左、右子树）的指针域只有的指针域只有n-1n-1个，而另外个，而另外2n-2n-(n-1)=(n-1)=n n1 1个指针域是空（个指针域是空（NULLNULL）的
40、，可以利用这些空指针域来指）的，可以利用这些空指针域来指向结点在遍历序列的前趋或后继结点。其中，用树中向结点在遍历序列的前趋或后继结点。其中，用树中空的左指针空的左指针指指向该结点的向该结点的前趋结点前趋结点，空的右指针空的右指针指向该结点的指向该结点的后继结点后继结点。线索：线索：指向遍历序列中的前趋结点或后继结点的指针。指向遍历序列中的前趋结点或后继结点的指针。线线索索化化：对对二二叉叉树树以以某某种种次次序序进进行行遍遍历历并并加加上上线线索索的的过过程程称称为为线索化。线索化。线索二叉树：线索二叉树：经过线索化后生成的二叉树称为线索二叉树。经过线索化后生成的二叉树称为线索二叉树。第68
41、页/共104页 为了区分结点指针是线索指针还是子树指针，在每个为了区分结点指针是线索指针还是子树指针，在每个结点的指针中增加两个标志域结点的指针中增加两个标志域 Lt 和和 Rt：0 0 指向子树（孩子）的指针指向子树（孩子）的指针 LtLt（或（或RtRt）=1 1 指向前趋或后继结点的线索指向前趋或后继结点的线索LtlchilddatarchildRt线索树的结点结构线索树的结点结构线索树的二叉链表的结点类型定义为:struct node anytype data；struct node *lchild；struct node *rchild；int Lt,Rt;；第69页/共104页AB
42、CDFEBT前根线索树示例前根遍历序列：ABDFCE000111011110第70页/共104页ABCDFEBT中根线索树示例中根遍历序列：BFDACE000001111111第71页/共104页ABCDFEBT后根线索树示例后根遍历序列：FDBECA111111100000第72页/共104页inthread(struct node *T)struct node *p，*pr；/*pr指向指向p的前趋结点的前趋结点*/int top；/*top为栈指针为栈指针*/struct node *sMAX_TREE_SIZE；pr=NULL；top=-1；p=T；建立中根线索树的非递归算法为：建立中
43、根线索树的非递归算法为：线索树的建立实质是将二叉链表中的空指针指向遍历线索树的建立实质是将二叉链表中的空指针指向遍历序列的前趋结点、后继结点序列的前趋结点、后继结点。建立中根线索树，实际上是建立中根线索树，实际上是在中根遍历的过程中修改在中根遍历的过程中修改空指针空指针，即在访问结点的同时，将空指针域逐个用线索替，即在访问结点的同时，将空指针域逐个用线索替代，并将其标志位置代，并将其标志位置1 1。7.5.2 7.5.2 中序线索树的建立中序线索树的建立第73页/共104页do while(p!=NULL)/*沿左孩子指针将结点依次入栈沿左孩子指针将结点依次入栈*/top=top+1；stop
44、=p；p=p-lchild；if(top!=-1)p=stop；top=top-1；/*弹出栈顶结点，访问该结点弹出栈顶结点，访问该结点*/visit(p-data)；if (p-lchild=NULL)/*该结点无左孩子该结点无左孩子*/p-Lt=1；p-lchild=pr；/*建左线索，使左指针指向前趋建左线索，使左指针指向前趋*/else p-Lt=0;if (pr!=NULL)if (pr-rchild=NULL)pr-rchild=p；/*建右线索，使前趋结点的右指针指向建右线索，使前趋结点的右指针指向p*/pr-Rt=1；else pr-Rt=0；pr=p；p=p-rchild；w
45、hile(p!=NULL|top!=-1)；pr-Rt=1；第74页/共104页7.5.3 7.5.3 在在中序线索树中序线索树中检索结点的前趋或后继中检索结点的前趋或后继1求结点求结点Q的前趋的前趋 若给定结点若给定结点Q Q的左标志位的左标志位LtLt1 1，则，则Q Q的左指针所指的的左指针所指的是是Q Q的前趋结点，若的前趋结点，若LtLt0 0，则取，则取Q Q的左子树的根（左孩子）的左子树的根（左孩子），设为，设为P P，并作如下讨论：，并作如下讨论：(1)(1)若若P P没有右子树没有右子树，即，即RtRt1 1，则，则P P为为Q Q的前趋结点。的前趋结点。(2)(2)若若P
46、P有右子树有右子树，则必须连续不断地沿着右子树的，则必须连续不断地沿着右子树的右指针，查询右孩子的标志位，若右指针，查询右孩子的标志位，若RtRt0 0，则通过右指针，则通过右指针找下一个结点（右孩子），若找下一个结点（右孩子），若RtRt1 1，则该结点就是，则该结点就是Q Q的的前趋结点。前趋结点。注意：在连续不断地向右子树查询中，不能注意：在连续不断地向右子树查询中，不能转向左子树。转向左子树。第75页/共104页ABCDFEBT结点F的Lt=1，其左指针指向的结点B即为它的前趋结点。中根遍历序列：BFDACE000001111111结点A的Lt=0，取其左子树的根结点B，B有右子树，沿
47、着B的右指针查询到D结点的Rt=1，则D结点即为A的前趋结点。结点D的Lt=0，取其左子树的根结点F，F没有右子树，则F结点即为D的前趋结点。第76页/共104页2求结点求结点Q的后继的后继 若给定结点若给定结点Q Q的右标志位的右标志位RtRt1 1，则，则Q Q的右指针所指的的右指针所指的是是Q Q的后继结点；若的后继结点；若RtRt0 0，则取，则取Q Q的右子树的根（右孩子）的右子树的根（右孩子），设为，设为P P。(1)(1)若若P P没有左子树没有左子树，即，即LtLt1 1，则，则P P是是Q Q的后继结点。的后继结点。(2)(2)若若P P有左子树有左子树，则必须连续不断地沿着
48、左子树的，则必须连续不断地沿着左子树的左指针，查询左孩子的标志位，若左指针，查询左孩子的标志位，若LtLt0 0，则通过左指针，则通过左指针找下一个结点（左孩子），若找下一个结点（左孩子），若LtLt1 1，则该结点就是，则该结点就是Q Q的的后继结点。后继结点。注意：在连续不断地向左子树查询中，不能注意：在连续不断地向左子树查询中，不能转向右子树转向右子树。第77页/共104页ABCDFEBT结点F的Rt=1，其右指针指向的结点D即为它的后继结点。中根遍历序列：BFDACE000001111111结点A的Rt=0，取其右子树的根结点C，C没有左子树，则C结点即为A的后继结点。结点B的Rt=0
49、，取其右子树的根结点D，D有左子树，沿着D的左指针查询到F结点的Lt=1，则F结点即为B的后继结点。第78页/共104页7.6 树、森林与二叉树的关系树、森林与二叉树的关系(教材第教材第教材第教材第8 8章章章章)在实际应用中，树的形态多种多样，其中每个结点的在实际应用中，树的形态多种多样，其中每个结点的度都可以是任意的，这就给一般树的存储与研究带来了一度都可以是任意的，这就给一般树的存储与研究带来了一定的复杂性。为了处理的方便，通常需将一般树转化为二定的复杂性。为了处理的方便，通常需将一般树转化为二叉树进行处理。叉树进行处理。1树与二叉树的转化树与二叉树的转化 将一棵树将一棵树T T转化为二
50、叉树转化为二叉树BTBT的规则如下：的规则如下：(1)(1)若若T T为空，则为空，则BTBT为空；为空；(2)(2)树树T T的根作为二叉树的根作为二叉树BTBT的根；的根；(3)(3)将树将树T T中结点的第一个子结点中结点的第一个子结点(即最左边的子结点即最左边的子结点)，作为二叉树作为二叉树BTBT中对应结点的左子结点；中对应结点的左子结点；T T中该结点的其他子结中该结点的其他子结点，则依次作为前一结点的右子结点出现在点，则依次作为前一结点的右子结点出现在BTBT中。中。第79页/共104页2森林转化为二叉树森林转化为二叉树 设设F=TF=T1 1，T T2 2，T Tm m 是森林