《树与二叉树优秀PPT.ppt》由会员分享，可在线阅读，更多相关《树与二叉树优秀PPT.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第3 3章章 树树数据结构:线性结构和非线性结构 线性结构(线性表,栈,队列等)非线性结构:至少存在一个数据元素有不止一个干脆前驱或后继(树,图等)树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它特别类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。2022/11/31先来看一下有关树的实例（c）书的书目2022/11/323.13.1树的基本术语树的基
2、本术语树的基本术语树的基本术语 1 1树的定义树的定义树的定义树的定义树树树树(Tree)(Tree)是是是是n(n0)n(n0)个结点的有限集个结点的有限集个结点的有限集个结点的有限集(记为记为记为记为T)T)，T T为为为为空时称为空树，否则它满足以下两个条件：空时称为空树，否则它满足以下两个条件：空时称为空树，否则它满足以下两个条件：空时称为空树，否则它满足以下两个条件：(1)(1)有且仅有一个结点没有前驱，称该结点为根结有且仅有一个结点没有前驱，称该结点为根结有且仅有一个结点没有前驱，称该结点为根结有且仅有一个结点没有前驱，称该结点为根结点点点点(Root)(Root)；(2)(2)除
3、根结点以外，其余结点可分为除根结点以外，其余结点可分为除根结点以外，其余结点可分为除根结点以外，其余结点可分为m(m0)m(m0)个互不个互不个互不个互不相交的有限集合相交的有限集合相交的有限集合相交的有限集合T0T0，TlTl，Tm-1Tm-1。其中每个集合。其中每个集合。其中每个集合。其中每个集合又构成一棵树，树又构成一棵树，树又构成一棵树，树又构成一棵树，树T0T0，TlTl，Tm-1Tm-1被称为根结被称为根结被称为根结被称为根结点的子树点的子树点的子树点的子树(Subree)(Subree)。每棵子树的根结点有且仅有一。每棵子树的根结点有且仅有一。每棵子树的根结点有且仅有一。每棵子树
4、的根结点有且仅有一个干脆前驱，但可以有个干脆前驱，但可以有个干脆前驱，但可以有个干脆前驱，但可以有0 0个或多个后继。个或多个后继。个或多个后继。个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或树的逻辑结构表示数据之间的关系是一对多，或树的逻辑结构表示数据之间的关系是一对多，或树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关者多对一的关系。它的结构特点具有明显的层次关者多对一的关系。它的结构特点具有明显的层次关者多对一的关系。它的结构特点具有明显的层次关系，是一种特别重要的非线性的数据结构。系，是一种特别重要的非线性的数据结构。系，是一种特别重要的
5、非线性的数据结构。系，是一种特别重要的非线性的数据结构。2022/11/33 图图(a)(a)是一棵只有一个根结点的树；是一棵只有一个根结点的树；图图 (b)(b)是是一一棵棵有有1212个个结结点点的的树树，即即T=AT=A，B B，C C，K K，L L 。A A是是棵棵根根，除除根根结结点点A A之之外外，其其余余的的1111个个结结点点分分为为三三个个互互不不相相交交的的集集合合。T1T1，T2T2和和T3T3是是根根A A的的三三棵棵子子树树，且且本本身身又又都都是是一一棵棵树树。所所以以树树的的定义是是递递归的归的。2022/11/342 2 2 2树的基本术语树的基本术语树的基本
6、术语树的基本术语1.结点的度:一个结点拥有的子树个数,度为零的结点称为叶子结点,其余结点称为非叶子节点或非终结结点。2.树的度:树中全部结点的度的最大值。树中最大分支数为树的度。3.结点的层次及树的深度:根为第一层,根的孩子为其次层,若某结点为第k层,则其孩子为k+1层。树中结点的最大层次称为树的深度或高度。2022/11/353.孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。4.子孙:以某结点为根的子树中的全部结点都被称为是该结点的子孙。5.祖先:从根结点到该结点路径上的全部结点。6.兄弟:同一个双亲的孩子之间互为兄弟。7.堂兄弟:双亲在同一层的结点互为堂兄弟。8
7、.有序树、无序树：假如树中每棵子树从左向右的排列拥有确定的依次，不得互换，则称为有序树，否则称为无序树。9.森林:是m(m=0)棵互不相的树的集合。森林与树概念相近,相互很容 易转换。2022/11/36 3.2.1 3.2.1 二叉树的定义与性质二叉树的定义与性质 二叉树二叉树(Binary Tree)(Binary Tree)是另一种重要的树型结构。是度为是另一种重要的树型结构。是度为2 2的有序树，的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。定义也可以用递归形式给出。1 1
8、二叉树的递归定义二叉树的递归定义 二叉树二叉树(BinaryTree)(BinaryTree)是是n(n0)n(n0)个结点的有限集。它或者是空集个结点的有限集。它或者是空集(n=0)(n=0)，或者同时满足以下两个条件：，或者同时满足以下两个条件：(1)(1)有且仅有一个根结点；有且仅有一个根结点；(2)(2)其余的结点分成两棵互不相交的左子树和右子树。其余的结点分成两棵互不相交的左子树和右子树。3.2 3.2 3.2 3.2 二叉树二叉树二叉树二叉树 例：试分别画出具有例：试分别画出具有3 3个结点的树和具有个结点的树和具有3 3个结点的二叉树的全部不同形态。个结点的二叉树的全部不同形态。
9、2022/11/37 二叉树与树有区分：树至少应有一个结点，而二叉树可以为空；树的子树没有依次，但假如二叉树的根结点只有一棵子树，必需明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。二叉树有5种基本形态：图、图、二叉树的五种基本形态二叉树的五种基本形态(a)a)空二叉树空二叉树 (b)b)只有根结点的二叉树只有根结点的二叉树(c)c)右子树为空的二叉树右子树为空的二叉树 (d)d)左子树为空的二叉树左子树为空的二叉树 (e)e)左右子树均不为空的二叉树左右子树均不为空的二叉树 2022/11/38两种特殊形态的二叉树：满二叉树和
10、完全二叉树。2.满二叉树(FullBinaryTree)深度为k，且有2k-1个结点的二叉树。特点：（1）每一层上结点数都达到最大；（2）度为1的结点n1=0，树叶都在最下一层上。结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。1237654k=3n=23-1=7 满二叉树2022/11/39 3.完全二叉树(Complete BinaryTree)深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。图图 完全二叉树完全二叉树完全二叉树的特点：（1）每个结点i的左子树的深度Lhi-其结点i的右
11、子树的深度Rhi等于0 或1，即叶结点只可能出现在层次最大或次最大的两层上。（2）完全二叉树结点数n满足2k-1-1n2k-1。（3）满二叉树确定是完全二叉树，反之不成立。452132022/11/3101324653241LH1=3RH1=1LH1-RH1=2 非完全二叉树非完全二叉树非完全二叉树非完全二叉树LHLH2 2=0=0RHRH2 2=1=1LH2-RH2=0-1=-12022/11/3114.4.4.4.遍历二叉树遍历二叉树遍历二叉树遍历二叉树 在在在在二二二二叉叉叉叉树树树树的的的的一一一一些些些些应应应应用用用用中中中中，常常常常常常常常要要要要求求求求在在在在树树树树中中中
12、中查查查查找找找找具具具具有有有有某某某某种种种种特特特特征征征征的的的的结结结结点点点点，或或或或者者者者对对对对树树树树中中中中全全全全部部部部结结结结点点点点逐逐逐逐一一一一进进进进行行行行某某某某种种种种处处处处理理理理。这这这这就就就就引引引引入入入入了了了了遍遍遍遍历历历历二二二二叉叉叉叉树树树树的的的的问问问问题题题题，即即即即如如如如何何何何按按按按某某某某条条条条搜搜搜搜寻寻寻寻路路路路径径径径访访访访问树中的每一个结点，使得每一个结点仅切仅被访问一次。问树中的每一个结点，使得每一个结点仅切仅被访问一次。问树中的每一个结点，使得每一个结点仅切仅被访问一次。问树中的每一个结点，
13、使得每一个结点仅切仅被访问一次。遍遍遍遍历历历历二二二二叉叉叉叉树树树树：指指指指按按按按确确确确定定定定的的的的规规规规律律律律对对对对二二二二叉叉叉叉树树树树的的的的每每每每个个个个结结结结点点点点，访问且仅访问一次的处理过程。访问且仅访问一次的处理过程。访问且仅访问一次的处理过程。访问且仅访问一次的处理过程。遍遍遍遍历历历历对对对对线线线线性性性性结结结结构构构构是是是是简简简简洁洁洁洁解解解解决决决决的的的的。而而而而二二二二叉叉叉叉树树树树是是是是非非非非线线线线性性性性的的的的，因因因因而而而而须须须须要要要要找找找找寻寻寻寻一一一一种种种种规规规规律律律律，使使使使二二二二叉叉叉
14、叉树树树树上上上上的的的的结结结结点点点点能能能能排排排排列列列列在在在在一一一一个个个个线性队列上，从而便于遍历。线性队列上，从而便于遍历。线性队列上，从而便于遍历。线性队列上，从而便于遍历。2022/11/312 访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的非线性排列，按访问的先后依次变为某种线性排列。遍历的次序：假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种状况，分别规定为：DLR先（根
15、）序遍历，LDR中（根）序遍历，LRD后（根）序遍历。一、遍历方案 DLR 先序遍历；LDR 中序遍历；LRD 后序遍历2022/11/3132 2）中序遍历二叉树算法思想）中序遍历二叉树算法思想:若二叉树非空，则：若二叉树非空，则：1 1）中序遍历左子树）中序遍历左子树2 2）访问根结点）访问根结点3 3）中序遍历右子树）中序遍历右子树算法描述算法描述:voidInorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)/根非空根非空Inorder(bt-lchild);visit(bt-data)；Inorder(bt-rchild);1 1）先序遍历二叉树算法思想）先序遍
16、历二叉树算法思想:若二叉树非空，则：若二叉树非空，则：1 1）访问根结点）访问根结点2 2）先序遍历左子树）先序遍历左子树3 3）先序遍历右子树）先序遍历右子树算法描述算法描述:voidPreorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)/根非空根非空visit(bt-data)visit(bt-data)；Preorder(bt-lchild);Preorder(bt-rchild);2022/11/314例例1 1遍历结果:先序先序:-+:-+a b-cd/efa b-cd/ef中序中序:a+b c-d-e/fa+b c-d-e/f后序后序:abcd-+ef/-a
17、bcd-+ef/-acdefb+3 3）后序遍历二叉树算法思想）后序遍历二叉树算法思想:若二叉树非空，则：若二叉树非空，则：1 1）后序遍历左子树）后序遍历左子树 2 2）后序遍历右子树）后序遍历右子树 3 3）访问根结点）访问根结点算法描述算法描述:voidPostorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)Postorder(bt-lchild);Postorder(bt-rchild);visit(bt-data)visit(bt-data)；2022/11/315例例2 2遍历结果:先序先序:+-+*3*xxx/1x5中序中序:3*x*x+x1/x+5后序后
18、序:3xx*x+1x/-5+-+*35x/x*xx1 1例例3 3 已知一棵二叉树的中序遍历序列为BDCEAFHG，其后序 遍 历 序 列 为DECBHGFA，试画出这棵二叉树并写出其 先 序 遍 历 序 列。ABFGHCED先序遍历序列：先序遍历序列：ABCDFGH2022/11/316（1 1 1 1）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：#include stdio.h#include stdio.h#includ
19、e stdio.h#include stdio.htypedef char ElemType;typedef char ElemType;typedef char ElemType;typedef char ElemType;typedef struct node /typedef struct node /typedef struct node /typedef struct node /定义链表结构定义链表结构定义链表结构定义链表结构 ElemType data;/ElemType data;/ElemType data;/ElemType data;/定义结点值定义结点值定义结点值定义结
20、点值 struct node*lchild;/struct node*lchild;/struct node*lchild;/struct node*lchild;/定义左子结点指针定义左子结点指针定义左子结点指针定义左子结点指针 struct node*rchild;/struct node*rchild;/struct node*rchild;/struct node*rchild;/定义右子结点指针定义右子结点指针定义右子结点指针定义右子结点指针BTree;BTree;BTree;BTree;preorder(BTree*root)/preorder(BTree*root)/preord
21、er(BTree*root)/preorder(BTree*root)/前序遍历前序遍历前序遍历前序遍历 if(root!=NULL)/if(root!=NULL)/if(root!=NULL)/if(root!=NULL)/假如不是空结点假如不是空结点假如不是空结点假如不是空结点 printf(“%cn”,root-data);/printf(“%cn”,root-data);/printf(“%cn”,root-data);/printf(“%cn”,root-data);/输出当前结点值输出当前结点值输出当前结点值输出当前结点值preorder(root-lchild);/preorde
22、r(root-lchild);/preorder(root-lchild);/preorder(root-lchild);/递归前序遍历左子结点递归前序遍历左子结点递归前序遍历左子结点递归前序遍历左子结点preorder(root-rchild);/preorder(root-rchild);/preorder(root-rchild);/preorder(root-rchild);/递归前序遍历右子结点递归前序遍历右子结点递归前序遍历右子结点递归前序遍历右子结点 return;/return;/return;/return;/结束结束结束结束 二、遍历算法二、遍历算法二、遍历算法二、遍历算法
23、2022/11/317voidinorder(BTree*root)/voidinorder(BTree*root)/中序遍中序遍中序遍中序遍历历历历if(root!=NULL)/if(root!=NULL)/假如不是空假如不是空假如不是空假如不是空结结结结点点点点inorder(root-lchild);/inorder(root-lchild);/递归递归递归递归中序遍中序遍中序遍中序遍历历历历左子左子左子左子结结结结点点点点printf(“%cn”,root-data);/printf(“%cn”,root-data);/输输输输出当前出当前出当前出当前结结结结点点点点值值值值inord
24、er(root-rchild);/inorder(root-rchild);/递归递归递归递归中序遍中序遍中序遍中序遍历历历历右子右子右子右子结结结结点点点点(3)(3)后序遍后序遍后序遍后序遍历历历历的算法的算法的算法的算法实现实现实现实现 voidpostorder(BTree*root)/voidpostorder(BTree*root)/后序遍后序遍后序遍后序遍历历历历if(root!=NULL)/if(root!=NULL)/假如不是空假如不是空假如不是空假如不是空结结结结点点点点postorder(root-lchild);/postorder(root-lchild);/递归递归
25、递归递归后序遍后序遍后序遍后序遍历历历历左子左子左子左子结结结结点点点点postorder(root-rchild);/postorder(root-rchild);/递归递归递归递归后序遍后序遍后序遍后序遍历历历历右子右子右子右子结结结结点点点点printf(“%cn”,root-data);/printf(“%cn”,root-data);/输输输输出当前出当前出当前出当前结结结结点点点点值值值值（2 2 2 2）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算
26、法如下（假定结点的元素值为字符型）：2022/11/3182 2二叉树的性质二叉树的性质性质性质1 1 在二叉树的第在二叉树的第i i层上至多有层上至多有2i-1 2i-1 个结点个结点(i1)(i1)。性质性质2 2 深度为深度为k k的二叉树至多有的二叉树至多有2k-12k-1个结点个结点(k1)(k1)。（深度确定，二叉树的最大结点数也确定）（深度确定，二叉树的最大结点数也确定）性质性质3 3 二叉树中二叉树中,终端结点数终端结点数n0n0与度为与度为2 2的结点数的结点数n2n2有如下关系有如下关系:n0=n2+1 n0=n2+1性质性质4 4 结点数为结点数为n n的完全二叉树，其深
27、度为的完全二叉树，其深度为 log2nlog2n +l+l。性性 质质 5 5 在在 按按 层层 序序 编编 号号 n n个个 结结 点点 的的 完完 全全 二二 叉叉 树树 中中，随随 意意 一一 结结 点点i(1in)i(1in)有：有：i=1i=1时时，结结点点i i是是树树的的根根；否否则则，结结点点i i的的双双亲亲为为结结点点 i/2i/2 (i1)(i1)。2i2in n时时，结结点点i i无无左左孩孩子子，为为叶叶结结点点；否否则则结结点点i i的的左左孩孩子子为为结结点点2i2i。2i+1 2i+1n n时，结点时，结点i i无右孩子；否则，结点无右孩子；否则，结点i i的右
28、孩子为结点的右孩子为结点2i+12i+1。例：若一棵树具有n1个度为1的结点，n2个度为2的结点，,nm个度为m的结点，则这棵树中的叶子结点有多少个。2022/11/3193.2.2 3.2.2 二叉树的存储结构二叉树的存储结构 同线性表一样，二叉树的存储结构也有依次和链表两种结构。同线性表一样，二叉树的存储结构也有依次和链表两种结构。1 1依次存储结构依次存储结构 用用一一组组地地址址连连续续的的存存储储单单元元，以以层层序序依依次次存存放放二二叉叉树树的的数数据据元元素，素，结点的相对位置蕴含着结点之间的关系。结点的相对位置蕴含着结点之间的关系。完全二叉树DCGFEBA bt 3 的双亲为
29、 3/2 =1，即在bt1中；其左孩子在bt2i=bt6中；其右孩子在bt2i+1=bt7中。1 2 3 4 5 6 7 8 9 10 11 A B C D E F G 0 0 0 02022/11/320 这种存储结构适合于完全二叉树，既不奢侈存储空间，又能很快确定结点的存放位置、结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的大量奢侈。D二叉树CGFEBA 一般二叉树也按完全二叉树形式存储，无结点处用0表示。123456789101112 ABCDEABCDE 0000 FGFG 00002022/11/321 例例如如：深深度度为为k k，且且只只有有k k个个结结点点
30、的的右右单单枝枝树树(每每个个非非叶叶结结点点只只有有右孩子右孩子)，需，需2k-12k-1个单元，即有个单元，即有2k-1-k2k-1-k个单元被奢侈。个单元被奢侈。链式存储结构链式存储结构 （二叉链表）设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表 三叉链表 线索链表 用空链域存放指向前驱或后继的线索2022/11/322 由于二叉树每个结点至多只有2个孩子，分别为左孩子和右孩子。因此可以把每个结点分成三个域：一个域存放结点本身的信息，另外两个是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：其中左链域lchild为指向左孩子的指针，右链域rchild为指向右孩
31、子的指针，数据域data表示结点的值。若某结点没有左孩子或右孩子，其相应的链域为空指针。对应的结构类型定义如下：对应的结构类型定义如下：typedef struct nodetypedef struct node ElemType data;ElemType data;struct node*lchild;struct node*lchild;struct node*rchild;struct node*rchild;BTree,*tree;BTree,*tree;其中，其中，treetree是指向根结点的指针。是指向根结点的指针。2022/11/323二叉链表的结点结构 lchild dat
32、a rchildD 二叉树二叉树CEBAACBDE二叉链表二叉链表说明：说明：一一个个二二叉叉链链表表由由根根指指针针rootroot唯唯一一确确定定。若若二二叉叉树树为为空空，则则root=NULLroot=NULL；若结点的某个孩子不存在，则相应的指针为空。若结点的某个孩子不存在，则相应的指针为空。具具有有n n个个结结点点的的二二叉叉链链表表中中，共共有有2 2n n个个指指针针域域。其其中中只只有有n-1n-1个个用来指示结点的左、右孩子，其余的用来指示结点的左、右孩子，其余的n+1n+1个指针域为空。个指针域为空。2022/11/324 和线性表一样，树可以用依次和链式两种存储结构。
33、树的依次存储结构适合树中结点比较“满”的状况。依据树的非线性结构特点，常用链式存储方式来表示树。树常用的存储方法有：双亲存储表示法、孩子链表表示法和孩子兄弟链表表示法。特点：求结点的双亲很简洁，但求结点的孩子须要遍历整个向量。3.3 3.3 树的存储结构树的存储结构 一般接受依次存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域：data域-存放结点的信息；parent域-存放该结点双亲结点的位置1 1双亲存储表示法双亲存储表示法ABCFGDEHI(a)树 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 4 I 4(b)树 的 双 亲 存 储 结 构序 号 d
34、ata parent0123456782022/11/325存储结构描述为：存储结构描述为：#defineMaxTreeSize100/定定义义数数组组空空间间的大小的大小typedefcharDataType；/定定义义数据数据类类型型typedefstructDataTypedata；/结结点数据点数据intparent；/双双亲亲指指针针，指示，指示结结点的双点的双亲亲在数在数组组中的位置中的位置PTreeNode；typedefstructPTreeNodenodesMaxTreeSize;intn；/结结点点总总数数PTree；PTreeT；/T是双亲链表是双亲链表2022/11/3
35、26 2 2孩子链表表示法孩子链表表示法 这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。n个孩子链表的头指针用一个向量表示。图、图、树的孩子链表结构树的孩子链表结构 头指针向量孩子链表头指针向量孩子链表特点：与双亲相反，求孩子易，求双亲难。A B C D E F G (b)树的孩子存储结构01234561234 56ABCFGDE(a)树2022/11/327存储结构描述为：存储结构描述为：存储结构描述为：存储结构描述为：typedefstructCTNodeintchild;/孩子孩子链链表表结结点点structCTNo
36、de*next;*ChildPtr;typedefstruct/孩子孩子链链表表头结头结点点ElemTypedata;/结结点的数据元素点的数据元素ChildPtrfirstchild;/孩子孩子链链表表头头指指针针CTBox;typedefstructCTBoxnodesMaxTreeSize;intn,r,/数的数的结结点数和根点数和根结结点的位置点的位置CTree;2022/11/328孩子孩子孩子孩子链链链链表表示法的表表示法的表表示法的表表示法的类类类类型型型型说说说说明明明明 typedefstructCnode/DataType和和MaxTreeSize由用由用户户定定义义/孩子
37、孩子链链表表结结点点intchild;/孩子孩子结结点在数点在数组组中中对应对应的下的下标标structCNode*next;Cnode;typedefstruct/孩子孩子链链表表头结头结点点DataTypedata;/存放存放树树中中结结点数据点数据CNode*firstchild;/孩子孩子链链表的表的头头指指针针PTNode;typedefstructPTNodenodesMaxTreeSize;Intn,root;/树树的的结结点数和根点数和根结结点的位置点的位置Ctree;CtreeT;/T的孩子链表表示的孩子链表表示 2022/11/329 孩子兄弟链表表示法也是树的一种链式存储
38、结构。用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。这种结构也称为二叉链表。图、图、树的孩子树的孩子-兄弟存储结构兄弟存储结构 特点：双亲只管长子，长子连接兄弟 3 3孩子兄弟链表表示法孩子兄弟链表表示法ABCFGDE(a)树2022/11/330树的孩子兄弟链表的存储结构描述为：树的孩子兄弟链表的存储结构描述为：typedef struct CSNodetypedef struct CSNode ElemType data;ElemType data;struct C
39、SNode*firstchild,*nextsibling;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;CSNode,*CSTree;孩孩子子兄兄弟弟存存储储结结构构的的最最大大优优点点是是可可以以便便利利地地实实现现树树和和二二叉叉树树的的相相互互转转换换和和树树的的各各种种操操作作。但但是是，孩孩子子兄兄弟弟存存储储结结构构的的缺缺点点也也是是查查找找当当前前结结点的双亲结点比较麻烦，须要从树根结点起先逐个结点比较查找。点的双亲结点比较麻烦，须要从树根结点起先逐个结点比较查找。2022/11/3313.63.6 树、森林和二叉树
40、的转换树、森林和二叉树的转换图图图图、森林和对应的二叉树森林和对应的二叉树森林和对应的二叉树森林和对应的二叉树（1）加线,在兄弟之间加一连线（2）抹线,对每个结点，除了其第一个孩子外，去除其与其余孩子之间的关系（3）旋转,对于横着的连线，以树的根结点为轴心，将其顺时针转 45。方法：2022/11/3321 1 1 1树的遍历树的遍历树的遍历树的遍历 所所所所谓谓谓谓树树树树的的的的遍遍遍遍历历历历，就就就就是是是是依依依依据据据据某某某某种种种种依依依依次次次次依依依依次次次次访访访访问问问问树树树树中中中中各各各各个个个个结结结结点点点点，并并并并使使使使得得得得每每每每个个个个结结结结点
41、点点点只只只只被被被被访访访访问问问问一一一一次次次次。也也也也就就就就是是是是把把把把非非非非线线线线性性性性结结结结构构构构的的的的树树树树结结结结点点点点变变变变成线性序列的一种方式成线性序列的一种方式成线性序列的一种方式成线性序列的一种方式 。树树树树的的的的遍遍遍遍历历历历可可可可以以以以按按按按深深深深度度度度优优优优先先先先遍遍遍遍历历历历，也也也也可可可可以以以以依依依依据据据据广广广广度度度度优优优优先先先先（按按按按层层层层次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。次）遍历。深度优先遍历通常有两种方式
42、：前序遍历和后序遍历。次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。(1)(1)(1)(1)前序遍历的递归定义：前序遍历的递归定义：前序遍历的递归定义：前序遍历的递归定义：若树若树若树若树T T T T非空，则：非空，则：非空，则：非空，则：访问根结点访问根结点访问根结点访问根结点R R R R；依依依依据据据据从从从从左左左左到到到到右右右右的的的的依依依依次次次次依依依依次次次次前前前前序序序序遍遍遍遍历历历历根根根根结结结结点点点点R R R R的的的的各各各各子子子子树树树树T1T1T1T1，T2T2T2T2，TkTkTkTk。2022/11/333(2)(2)后序遍历的递
43、归定义：后序遍历的递归定义：后序遍历的递归定义：后序遍历的递归定义：若树若树若树若树T T非空，则：非空，则：非空，则：非空，则：依依依依据据据据从从从从左左左左到到到到右右右右的的的的依依依依次次次次依依依依次次次次后后后后序序序序遍遍遍遍历历历历根根根根T T的的的的各各各各子子子子树树树树TlTl，T2T2，TkTk；访问根结点访问根结点访问根结点访问根结点R R。(3)(3)广度优先（按层）遍历广度优先（按层）遍历广度优先（按层）遍历广度优先（按层）遍历广广广广度度度度优优优优先先先先（按按按按层层层层次次次次）遍遍遍遍历历历历定定定定义义义义为为为为：先先先先访访访访问问问问第第第第
44、一一一一层层层层结结结结点点点点（即即即即树树树树根根根根结结结结点点点点），再再再再从从从从左左左左至至至至右右右右访访访访问问问问其其其其次次次次层层层层结结结结点点点点，依依依依次次次次按按按按层层层层访访访访问问问问，直直直直到到到到树树树树中中中中结结结结点点点点全全全全部部部部被被被被访访访访问问问问为为为为止止止止。对对对对图图图图(a)(a)中中中中的的的的树树树树进进进进行行行行按按按按层层层层次次次次遍遍遍遍历历历历得得得得到到到到树树树树的的的的广度优先遍历序列为：广度优先遍历序列为：广度优先遍历序列为：广度优先遍历序列为：ABCDEFGABCDEFG。说明：说明：说明：
45、说明：前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。2022/11/3342森林的遍历森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。(1)前序遍历森林 若森林非空，则：访问森林中第一棵树的根结点；前序遍历第一棵树中根结点的各子树所构成的
46、森林前序遍历去掉第一棵树外其它树构成的森林。(2)后序遍历森林 若森林非空，则:后序遍历森林中第一棵树中根结点的各子树所构成的森林；访问第一棵树的根结点；后序遍历去掉第一棵树外其它树构成的森林。当用二叉链表作为树和森林的存储结构时，树和森林的前序遍历和后序遍历可用二叉树的前序遍历和中序遍历算法来实现。2022/11/3353.7.3 树的应用哈夫曼树1.哈夫曼树的基本概念 哈夫曼树（Huffman）又称最优二叉树，是一类带权路径长度最短的树，有着广泛的应用。基本概念：树中两个结点之间的路径由一个结点到另一结点的分支构成。两结点之间的路径长度是路径上分支的数目。树的路径长度是从根结点到每一个结点
47、的路径长度之和。在应用中，将树中结点赐予一个有某种意义的实数，称为该结点的权。结点的带权路径长度，是指该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度（Weighted Path Length of Tree）定义为树中全部叶子结点的带权路径长度之和，记为：其中，n表示叶子结点的数目，Wi和Ni分别表示叶子结点Ki的权值和根到叶子结点Ki之间的路径长度。2022/11/3362022/11/3372022/11/3382022/11/3392022/11/3402022/11/3412022/11/3422022/11/3432022/11/3442022/11/3452022/11/346习题：1、对给定的一组权W=14，15，7，4，20，3，确定哈夫曼树，并求出其带权路长。2、假设用于通讯的电文仅由8个字母组成，字母在英文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。3、假设字符a、b、c、d、e、f出现的概率分别为0.07、0.09、0.12、0.22、0.23、0.27，求最优哈夫曼编码，并画出哈夫曼树，试问编码的平均长度是多少？2022/11/347