数据结构-从概念到C++实现（第4版）课件 第四章 树和二叉树

4-1引言v第四章树和二叉树文件系统许多问题抽象出的数据模型具有层次关系例1

操作系统的文件目录结构。表达式树例2一个算术表达式可以用表达式树来表示，并且具有以下两个特点（1）叶子结点是操作数；（2）分支结点是运算符。后序遍历转换为后缀表达式（逆波兰式）：abcd

-*+ef/-aefbcd-+/*-表达式：a+b*(c–d)–e/f随处可见的树结构例3

计算机系统中随处可见的树结构。例4

日常生活中随处可见的树结构。随处可见的树结构例4

日常生活中随处可见的树结构。吉林省市区街道朝阳南关二道高新宽城绿园双阳九台湖西桂林永昌红旗清和……吉林长春四平通化辽源松原白城白山延边随处可见的树结构知识树思维导图关于树结构什么是树？在逻辑上有什么特点？有哪些基本术语？如何存储树结构？什么是二叉树？在逻辑上有什么特点？有哪些基本性质？如何存储二叉树？如何实现二叉树的遍历操作？最优二叉树及应用4-2树的逻辑结构v第四章树和二叉树树的定义和基本术语树的抽象数据类型定义树的遍历操作学什么？4-2-1树的定义和基本术语v第四章树和二叉树树的定义树：n（n≥0）个结点的有限集合数据元素树的定义是采用递归方法，当n＝0时，称为空树；任意一棵非空树T满足以下条件：（1）有且仅有一个特定的称为根的结点；（2）当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。ACBGFEDHIACBGFDACBGFDE互不相交的含义是什么？结点：结点不能属于多个子树边：子树之间不能有关系互不相交没有回路树的逻辑特征树结构具有层次性树的基本术语ACBGFEDHI树的度：树中各结点度的最大值结点的度：结点所拥有的子树的个数分支结点：度不为0的结点，也称为非终端结点叶子结点：度为0的结点，也称为终端结点ACBGFEDHI双亲：这个结点称为它孩子结点的双亲结点孩子：树中某结点子树的根结点称为这个结点的孩子结点兄弟：具有同一个双亲的孩子结点互称为兄弟a1ana2ai-1ai在线性结构中，逻辑关系表现为前驱——后继在树结构中，逻辑关系表现为双亲——孩子树的基本术语ACBGFEDHI路径：结点序列n1,n2,…,nk称为一条由n1至nk的路径，当且仅当满足如下关系：结点ni是ni+1的双亲（1<=i<k）路径长度：路径上经过的边的个数在树结构中，路径是唯一的祖先、子孙：如果有一条路径从结点x到结点y，则x称为y的祖先，而y称为x的子孙树的基本术语ACBGFEDHI结点所在层数：根结点的层数为1；对其余结点，若某结点在第k

层，则其孩子结点在第k+1层树的深度（高度）：树中所有结点的最大层数树的宽度：树中每一层结点个数的最大值深度=4宽度=4树的基本术语线性结构和树结构的比较开始结点（只有一个）：无前驱根结点（只有一个）：无双亲终端结点（只有一个）：无后继叶子结点（可以多个）：无孩子其它元素：一个前驱，一个后继其它结点：一个双亲，多个孩子一对一

一对多ACBGFEDHIa1ana2ai-1ai线性结构树结构4-2-2树的抽象数据类型定义v第四章树和二叉树树的抽象数据类型定义树的应用很广泛，在不同的实际应用中，树的基本操作不尽相同ADTTreeDataModel

树由一个根结点和若干棵子树构成，树中结点具有层次关系OperationInitTree：初始化一棵树

DestroyTree：销毁一棵树PreOrder：前序遍历树PostOrder：后序遍历树LevelOrder：层序遍历树endADT简单起见，只讨论树的遍历树的遍历什么是遍历？线性结构如何遍历？简言之，遍历是对数据集合进行没有遗漏、没有重复的访问树的遍历：从根结点出发，按照某种次序访问树中所有结点，并且每个结点仅被访问一次抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据先序（根）、后序（根）和层序（次）等a1ana2ai树的先序遍历操作定义：若树为空，则空操作返回；否则（1）访问根结点（2）从左到右先序遍历根结点的每一棵子树先序：ABDEHIFCG树的遍历树的后序遍历操作定义：若树为空，则空操作返回；否则（1）从左到右后序遍历根结点的每一棵子树（2）访问根结点后序：DHIEFBGCAACBGFEDHI树的层序遍历操作定义：从树的根结点开始，自上而下逐层遍历，同一层从左到右对结点逐个访问层序：ABCDEFGHI4-3树的存储结构v第四章树和二叉树思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系数据元素及其逻辑关系在存储器中的表示实现树的存储结构，关键是什么?什么是存储结构?树中结点之间的逻辑关系是什么?CBGFEDHIA学什么？4-3-1树的双亲表示法v第四章树和二叉树双亲表示法CBGFEDHIA树的双亲表示法：用一维数组存储树中各个结点（一般按层序存储）的数据信息以及该结点的双亲在数组中的下标012345678dataparent

ABCDEFGHI

-100111224如何定义树的双亲表示法?template<typename

DataType>struct

PNode

{

DataTypedata;

intparent;};012345678

A-1B0C0D1E1F1G2H2I

4dataparent如何查找双亲结点？时间性能？O(1)如何查找孩子结点？时间性能？O(n)数据表示firstChild

136

-18-1-1-1-1双亲表示法CBGFEDHIA4-3-2树的孩子表示法v第四章树和二叉树孩子表示法CBGFEDHIA如何表示结点的孩子呢？方案一：指针域的个数等于树的度

datachild1child2……childd其中：data：数据域，存放该结点的数据信息

child1~childd：指针域，指向该结点的孩子∧AB∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧缺点：浪费空间CBGFEDHIA方案二：指针域的个数等于该结点的度

datadegreechild1child2……childd其中：data：存放该结点的数据；degree：存放该结点的度；

child1~childd：指针域，指向该结点的孩子孩子表示法如何表示结点的孩子呢？A2B3C2E1I0G0H0F0D0缺点：结点结构不一致CBGFEDHIA方案三：将结点的所有孩子构成一个单链表12∧345∧7∧68∧∧∧∧∧∧firstChild

012345678

ABCDEFGHIdata孩子表示法如何表示结点的孩子呢？如何定义树的孩子表示法呢？12∧345∧7∧68∧∧∧∧∧∧firstChild

012345678

ABCDEFGHIdatachildnext孩子结点datafirstChild表头结点孩子表示法structChildNode//孩子结点{

intchild;ChildNode*next;};template<typenameDataType>structTreeNode//表头结点{DataTypedata;ChildNode*firstChild;//指向孩子链表的头指针};如何定义树的孩子表示法呢？孩子表示法childnext孩子结点datafirstChild表头结点ACBGFEDHI如何查找孩子结点？时间性能？O(1)12∧345∧7∧68∧∧∧∧∧∧firstchild

012345678

ABCDEFGHIdata孩子表示法ACBGFEDHI如何查找双亲结点？时间性能？O(n)12∧345∧7∧68∧∧∧∧∧∧firstchild

ABCDEFGHIdata012345678

ABCDEFGHIdata

parent-100111224孩子表示法4-3-3树的孩子兄弟表示法v第四章树和二叉树孩子兄弟表示法CBGFEDHIA树的孩子兄弟表示法（二叉链表）：链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针某结点的第一个孩子是惟一的某结点的右兄弟是惟一的设置两个分别指向该结点的第一个孩子和右兄弟的指针CBGFEDHIA

B∧

D

C

F

I

G∧

H∧

E∧∧∧∧∧∧∧

A孩子兄弟表示法树的孩子兄弟表示法（二叉链表）：链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针如何定义树的孩子兄弟存储结构?firstChilddata

rightSibtemplate<typenameDataType>structTNode{

DataTypedata;

TNode<DataType>*firstChild,*rightSib;};

孩子兄弟表示法

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧ACBGFEDHI

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧如何查找兄弟结点？时间性能？O(1)孩子兄弟表示法如何查找孩子结点？时间性能？O(n)已知该结点指针：O(1)4-4二叉树的逻辑结构v第四章树和二叉树二叉树的定义二叉树的基本性质二叉树的抽象数据类型定义学什么？二叉树的构造二叉树的遍历操作4-4-1二叉树的定义v第四章树和二叉树二叉树的定义二叉树：是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二叉树是度为2的树吗？AB二叉树是度小于等于2的树吗？ABACBDEFGACBDEFG二叉树有什么特点？（1）每个结点最多有两棵子树（2）二叉树是有序的，其次序不能任意颠倒

为什么要研究二叉树？（1）二叉树是最简单的树结构（2）将树转换为二叉树，

从而利用二叉树解决树的有关问题二叉树的特点斜树斜树：左斜树和右斜树的统称左斜树：所有结点都只有左子树的二叉树ABD右斜树：所有结点都只有右子树的二叉树ABD斜树有什么特点呢？（1）每一层只有一个结点（2）结点个数与其深度相同斜树是树结构的特例，是从树结构退化成了线性结构满二叉树满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层的二叉树ABCDEFHIJKLMNOGABCDEFLMG所有分支结点都有左右子树，但叶子不在同一层满二叉树有什么特点呢？（1）叶子只能出现在最下一层满二叉树是树结构的特例，是最丰满的二叉树ABCDEFHIJKLMNOG（4）在同样深度的二叉树中叶子结点个数最多（2）只有度为0和度为2的结点（3）在同样深度的二叉树中结点个数最多满二叉树满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树L完全二叉树完全二叉树：在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树ABCDEFHIJKMNOGABCDEFHIJKMG完全二叉树有什么特点呢？（1）叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面ABCDEFHIJG（3）深度为k

的完全二叉树在

k-1层上一定是满二叉树（2）完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子（4）在同样结点个数的二叉树中，完全二叉树的深度最小完全二叉树完全二叉树：在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树4-4-2二叉树的基本性质v第四章树和二叉树二叉树的性质性质5-1：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0＝n2＋1ACBE证明:设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：

n＝n0＋n1＋n2

在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：

n＝n1＋2n2＋1两式联立，可以得到：

n0＝n2＋1性质5-2：二叉树的第

i

层上最多有2i-1个结点（i≥1）证明：采用归纳法证明。当

i=1时，只有一个根结点，而2i-1=20=1，结论成立。假设

i=k时结论成立，即第

k层上最多有2k-1个结点。考虑

i=k+1时的情形。由于第

k+1层上的结点是第

k层上结点的孩子，而二叉树中每个结点最多有两个孩子，故在第

k+1层上的最多大结点个数有2×2k-1＝2k个结点，则在

i=k+1时结论也成立。由此，结论成立。二叉树的性质性质5-3：一棵深度为k

的二叉树中，最多有2k-1个结点证明：设深度为k的二叉树中结点个数最多为n，则深度为k且具有2k-1个结点的二叉树一定是满二叉树二叉树的性质证明：设具有n

个结点的完全二叉树的深度为k，则2k-1-12k-1…2k-1第k层…第k-1层对不等式取对数，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1二叉树的性质性质5-4：具有n个结点的完全二叉树的深度为log2n+1。由于k

是整数，故必有

k＝log2n+1性质5-5：对一棵具有n

个结点的完全二叉树中从1开始按层序编号，对于编号为i（1≤i≤n）的结点（简称结点i），有：（1）如果i＞1，则结点i

的双亲结点的编号为i/2，否则结点i

无双亲结点（2）如果2i≤n，则结点i

的左孩子的编号为2i，否则结点i

无左孩子（3）如果2i+1≤n，则结点i

的右孩子的编号为2i+1，否则结点i

无右孩子12345689107二叉树的性质4-4-3二叉树的抽象数据类型定义v第四章树和二叉树二叉树的抽象数据类型定义ADTBiTreeDataModel

二叉树由一个根结点和两棵互不相交的左右子树构成，结点具有层次关系OperationInitBiTree：初始化一棵空的二叉树

CreateBiTree：建立一棵二叉树

DestroyBiTree：销毁一棵二叉树PreOrder：前序遍历二叉树InOrder：中序遍历二叉树PostOrder：后序遍历二叉树LevelOrder：层序遍历二叉树endADT简单起见，只讨论二叉树的遍历二叉树的遍历二叉树的遍历：从根结点出发，按照某种次序访问树中所有结点，并且每个结点仅被访问一次抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据限定先左后右：先序、中序、后序根结点D左子树L右子树R二叉树按照什么次序对二叉树进行遍历呢？二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD

层序遍历：按二叉树的层序编号的次序访问各结点二叉树的先序遍历操作定义：若二叉树为空，则空操作返回；否则：（1）访问根结点（2）先序遍历根结点的左子树（3）先序遍历根结点的右子树ACBDEFG先序：ABDGCEF二叉树的遍历二叉树的中序遍历操作定义：若二叉树为空，则空操作返回；否则：（1）中序遍历根结点的左子树（2）访问根结点（3）中序遍历根结点的右子树中序：DGBAECF二叉树的后序遍历操作定义：若二叉树为空，则空操作返回；否则：（1）后序遍历根结点的左子树（2）后序遍历根结点的右子树（3）访问根结点ACBDEFG后序：GDBEFCA二叉树的遍历层序：ABCDEFG二叉树的层序遍历操作定义：从二叉树的根结点开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问若已知一棵二叉树的先序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？ABCABC先序遍历序列：ABC若已知一棵二叉树的先序序列和后序序列，能否唯一确定这棵二叉树呢？后序遍历序列：CBA二叉树的构造先序：ABCDEFG

HI中序：BCA

EDGHFIADEFG

HIBC先序：BC中序：BC先序：DEFGHI中序：EDGHFIDEFGHIABC二叉树的构造例4-1已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABCDEFGH和CDBAFEHG，请确定该二叉树。先序：FG

HI中序：GHFIADEBCFGIH层序：

ABCDEFGHI中序：

DBGEHACIFACIFDBGEHCAB二叉树的构造例4-2已知一棵二叉树的层序遍历序列和中序遍历序列分别为ABCDEFGHI和DBGEHACIF，请构造该二叉树。层序：

A

B

CDEFGHI中序：

DBGEHA

CIFGEHDIFCABDEGHFI4-5二叉树的存储结构v第四章树和二叉树二叉树的顺序存储结构二叉链表三叉链表学什么？4-5-1二叉树的顺序存储结构v第四章树和二叉树二叉树的顺序存储结构顺序存储结构的要求是什么？用一组连续的存储单元依次存储数据元素，由存储位置表示元素之间的逻辑关系如何利用数组下标来反映结点之间的逻辑关系?完全二叉树中结点的编号可以唯一地反映结点之间的逻辑关系二叉树的顺序存储结构是用一维数组存储二叉树的结点，结点的存储位置（下标）应能体现结点之间的逻辑关系——父子关系ABCDEFHIJ编号为下标

A12345678910

B

C

D

E

F

G

H

I

JconstMaxSize=100;template<typenameDataType>structSeqBiTree{

DataTypedata[MaxSize];intbiTreeNum;};如何定义二叉树的顺序存储结构呢？二叉树的顺序存储结构如果从下标0开始存储，如何表示逻辑关系？ABCDFEG152361310以编号为下标

A12345678910111213

B

C∧

D

F∧

∧

∧

E

∧

∧

G将二叉树按完全二叉树编号：（1）根结点的编号为1（2）若某结点

i有左孩子，则其左孩子的编号为2i（3）若某结点

i有右孩子，则其右孩子的编号为2i+1对于普通的二叉树，如何顺序存储呢？二叉树的顺序存储结构二叉树的顺序存储结构一般仅存储完全二叉树顺序存储一棵右斜树会发生什么情况？ACOG缺点：浪费存储空间二叉树的顺序存储结构4-5-2二叉链表v第四章树和二叉树如何用链接存储方式存储二叉树呢？firsta1a2an∧二叉链表：二叉树的每个结点对应一个链表结点，存放结点的数据信息和指示左右孩子的指针二叉链表的存储方法lchild

datarchildACBDEFGACBDEFGGFEDB∧∧∧∧∧∧∧∧CAroot二叉链表的存储方法叶子结点的标志？左右孩子指针均为空二叉链表的存储结构定义GFEDBA∧∧∧∧∧∧∧∧Ctemplate<typenameDataType>structBiNode{

DataTypedata;BiNode<DataType>*lchild,*rchild;};root如何定义二叉链表的结点呢？n个结点的二叉链表有多少个空指针？2n-(n-1)=n+1个空指针三叉链表的存储方法GFEDBA∧∧∧∧∧∧∧∧C如何查找双亲？时间性能？O(n)在二叉链表中增加一个指向双亲的指针域

lchild

dataparentrchildrootA∧B∧D∧E∧F∧CG∧∧∧∧ACBDEFGroot三叉链表的存储方法二叉链表的类定义二叉树的抽象数据类型定义？template<typenameDataType>classBiTree{public:

BiTree(){root=CreateBiTree(root);}

~BiTree(){ReleaseBiTree(root);}

voidPreOrder(){PreOrder(root);}

voidInOrder(){InOrder(root);}

voidPostOrder(){PostOrder(root);}

voidLevelOrder();private:

BiNode<DataType>*CreateBiTree(BiNode<DataType>*bt);

voidReleaseBiTree(BiNode<DataType>*bt);

voidPreOrder(BiNode<DataType>*bt);

voidInOrder(BiNode<DataType>*bt);

voidPostOrder(BiNode<DataType>*bt);

BiNode<DataType>*root;};InitBiTree：初始化一棵空的二叉树

CreateBiTree：建立一棵二叉树

DestroyBiTree：销毁一棵二叉树PreOrder：前序遍历二叉树InOrder：中序遍历二叉树PostOrder：后序遍历二叉树LevelOrder：层序遍历二叉树先序遍历算法template<typenameDataType>voidBiTree<DataType>::PreOrder(BiNode<DataType>*bt){

if(bt==nullptr)return;

//递归调用的结束条件

else{

cout<<bt->data;

//访问根结点bt的数据域

PreOrder(bt->lchild);

//先序递归遍历bt的左子树

PreOrder(bt->rchild);

//先序递归遍历bt的右子树

}}按照先左后右的方式扫描二叉树，区别仅在于访问结点的时机LRACBDPre(*A)

（1）APre(A->lchild);

Pre(*B)

（2）BPre(B->lchild);

Pre(∧)Pre(*D)

（3）DPre(D->lchild);

Pre(∧)Pre(∧)Pre(B->rchild);Pre(D->rchild);约定：*A表示根指针指向结点Aif(bt==nullptr)return;else{

①

cout<<bt->data;

②

PreOrder(bt->lchild);

③

PreOrder(bt->rchild);}先序遍历算法ACBDPre(*A)

（1）APre(A->lchild);

Pre(*B)

（2）BPre(B->lchild);

Pre(∧)Pre(*D)

（3）DPre(D->lchild);

Pre(∧)Pre(∧)Pre(B->rchild);Pre(D->rchild);Pre(∧)Pre(∧)Pre(*C)

（4）CPre(C->lchild);

Pre(A->rchild);Pre(C->rchild);得到先序遍历序列：ABDCif(bt==nullptr)return;else{

①

cout<<bt->data;

②

PreOrder(bt->lchild);

③

PreOrder(bt->rchild);}先序遍历算法遍历序列：AABCBDCEFGDEFGACBDEFG队列Q初始化；2.如果二叉树非空，将根指针入队；入队出队3.3若结点q存在左孩子，则将左孩子指针入队；3.4若结点q存在右孩子，则将右孩子指针入队；3.循环直到队列Q为空3.1q=队列Q的队头元素出队；3.2访问结点q的数据域；

层序遍历算法template<typenameDataType>voidBiTree<DataType>::LevelOrder(){

BiNode<DataType>*Q[100],*q=nullptr;

intfront=-1,rear=-1;

if(root==nullptr)return;

Q[++rear]=root;

while(front!=rear)

{

q=Q[++front];cout<<q->data;

if(q->lchild!=nullptr)Q[++rear]=q->lchild;

if(q->rchild!=nullptr)Q[++rear]=q->rchild;

}}时间复杂度？每个结点进队一次出队一次O(n)O(n)层序遍历算法遍历是二叉树各种操作的基础，可以在遍历的过程中建立一棵二叉链表在内存中建立一棵二叉链表，如何输入二叉树的信息？构造二叉链表如何由一种遍历序列生成该二叉树？扩展二叉树：将每个结点的空指针引出一个虚结点，其值为一特定值如'#'ACBD先序：AB#D##C##ACBD#####template<typename

DataType>BiNode<DataType>*BiTree<DataType>::CreateBiTree(BiNode<DataType>*bt){

charch;

cin>>ch;

//输入结点的数据信息，假设为字符

if(ch==‘#’)bt=nullptr;

//建立一棵空树

else{

bt=newBiNode<DataType>;

bt->data=ch;

bt->lchild

=CreateBiTree(bt->lchild);//递归建立左子树

bt->rchild

=CreateBiTree(bt->rchild);//递归建立右子树

}

returnbt;}构造二叉链表销毁二叉链表为什么要销毁内存中的二叉链表？二叉链表是动态存储分配，二叉链表的结点是在程序运行过程中动态申请的，在二叉链表变量退出作用域前，要释放二叉链表的存储空间template<typenameDataType>voidBiTree<DataType>::ReleaseBiTree(BiNode<DataType>*bt){

if(bt==nullptr)return;

else{

ReleaseBiTree(bt->lchild);

//释放左子树

ReleaseBiTree(bt->rchild);

//释放右子树

deletebt;

//释放根结点

}}4-6森林v第四章树和二叉树森林的逻辑结构树、森林与二叉树的转换学什么？4-6-1森林的逻辑结构v第四章树和二叉树CBGFEDHIEHIA对于树：删去根结点就变成了森林对于森林：增加一个根结点，将森林中的每一棵树作为这个根结点的子树，则森林就变成了一棵树森林的定义森林：m（m≥0）棵互不相交的树的集合森林的遍历ABCEFDGJIH第3棵是度为2的树还是二叉树？森林的遍历：按照某种次序依次遍历构成森林的m（m≥0）棵树先序（根）、后序（根）先序：ABCDEFGHIJ后序：BADEFCHJIG4-6-2树、森林与二叉树的转换v第四章树和二叉树树与二叉树的对应关系A∧BC∧E∧D∧F∧∧G∧∧CBFEDGAACBEGDF

A

B

D

E

F

G∧∧∧∧∧∧

C∧Page02逻辑关系有什么变化?

树：兄弟关系二叉树：双亲和右孩子

树：双亲和长子二叉树：双亲和左孩子CBFEDGAACBEGDF树与二叉树的对应关系树转换为二叉树CBFEDGA将一棵树转换为二叉树的方法是：（1）加线——树中所有相邻兄弟之间加一条连线（2）去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。（3）层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。ACBEGDF树的先序遍历等价于二叉树的先序遍历！树的后序遍历等价于二叉树的中序遍历！树转换为二叉树CBFEDGAACBEGDF二叉树根结点的右子树为空树的根结点没有兄弟树的先序和后序遍历序列？二叉树的先序和中序遍历序列？森林转换为二叉树（1）将森林中的每棵树转换为二叉树（2）将每棵树的根结点视为兄弟，在所有根结点之间加上连线（3）按照二叉树结点之间的关系进行层次调整将一个森林转换为二叉树的方法是ABCEFDGJIHABCEFDGJIHABCDEFGJIHABCDEFGJIH森林转换为二叉树二叉树转换为树（森林）将一棵二叉树还原为树或森林，具体转换方法是（1）加线——若某结点x

是其双亲y

的左孩子，则把结点x

的右孩子、右孩子的右孩子、……，与结点y

连线（2）去线——删去所有双亲结点与右孩子结点的连线（3）层次调整——整理由（1）、（2）两步所得到的树（森林），使之层次分明。ACBEGDFCBFEDGA4-7最优二叉树v第四章树和二叉树哈夫曼算法学什么？哈夫曼编码最优二叉树（哈夫曼树）的基本概念最优二叉树叶子结点的权值：对叶子结点赋予的一个有意义的数值量二叉树的带权路径长度：从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和取决于具体问题第k个叶子的权值从根结点到第k个叶子的路径长度最优二叉树（哈夫曼树）：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树323428324552345432最优二叉树最优二叉树有什么特点?（1）权值越大的叶子结点越靠近根结点（2）只有度为0和度为2的结点，不存在度为1的结点4-7-1哈夫曼算法v第四章树和二叉树哈夫曼算法【问题】给定一组权值，构造最优二叉树1.初始化：由n个权值构造n棵只有一个根结点的二叉树，得到一个二叉树集合F＝{T1，T2，…，Tn}；2.重复下述操作，直到集合F中只剩下一棵二叉树

2.1选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左右子树根结点的权值之和；

2.2删除与加入：在F中删除作为左右子树的两棵二叉树，并将新建立的二叉树加入到F中；【想法——哈夫曼算法的基本思想】例给定权值集合{2，4，5，3}初始化选取与合并删除与加入245323

54523

5运行实例23

545

923

545

914【算法——数据表示】如何存储哈夫曼树呢？23

545

914采用数组还是链表呢？

n

个叶子结点合并

n-1次n-1个分支结点哈夫曼树共有2n-1个结点设数组huffTree[2n-1]须存储哪些关系呢？选取根结点权值最小的二叉树存储parent信息作为左右子树进行合并存储lchild和rchild信息weightlchildrchildparent哈夫曼算法23

545

914weightlchildrchildparentstructElemType{

intweight;/*假定权值为整数*/

intparent,lchild,rchild;};函数原型：voidHuffmanTree(ElemTypehuffTree[],intw[],intn)哈夫曼算法【算法——数据表示】如何存储哈夫曼树呢？【算法——数据处理过程】-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1例给定权值集合{2，4，5，3}24530123456weightparentlchildrchildfor(i=0;i<2*n-1;i++){huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}算法描述：哈夫曼算法-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-124530123456weightparentlchildrchildfor(i=0;i<n;i++)huffTree[i].weight=w[i];算法描述：例给定权值集合{2，4，5，3}哈夫曼算法【算法——数据处理过程】2453-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-124530123456weightparentlchildrchild4523

5i1i25huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;算法描述：k例给定权值集合{2，4，5，3}哈夫曼算法【算法——数据处理过程】2453-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-