当前位置：文档之家 › 5_树和二叉树

5_树和二叉树

  • 格式：pptx
  • 大小：714.31 KB
  • 文档页数：65

下载文档原格式

  / 65

合集下载

数据结构与算法系列研究五——树、二叉树、三叉树、平衡排序二叉树AVL

数据结构与算法系列研究五——树、二叉树、三叉树、平衡排序二叉树AVL

数据结构与算法系列研究五——树、⼆叉树、三叉树、平衡排序⼆叉树AVL树、⼆叉树、三叉树、平衡排序⼆叉树AVL⼀、树的定义树是计算机算法最重要的⾮线性结构。

树中每个数据元素⾄多有⼀个直接前驱，但可以有多个直接后继。

树是⼀种以分⽀关系定义的层次结构。

a.树是n(≥0)结点组成的有限集合。

{N.沃恩}(树是n(n≥1)个结点组成的有限集合。

{D.E.Knuth})在任意⼀棵⾮空树中：⑴有且仅有⼀个没有前驱的结点----根(root)。

⑵当n>1时，其余结点有且仅有⼀个直接前驱。

⑶所有结点都可以有0个或多个后继。

b. 树是n(n≥0)个结点组成的有限集合。

在任意⼀棵⾮空树中：⑴有⼀个特定的称为根（root）的结点。

⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的⼦集T1，T2，…，Tm。

每个集合本⾝⼜是⼀棵树，并且称为根的⼦树（subtree）树的固有特性---递归性。

即⾮空树是由若⼲棵⼦树组成，⽽⼦树⼜可以由若⼲棵更⼩的⼦树组成。

树的基本操作1、InitTree(&T) 初始化2、DestroyTree(&T) 撤消树3、CreatTree(&T,F) 按F的定义⽣成树4、ClearTree(&T) 清除5、TreeEmpty(T) 判树空6、TreeDepth(T) 求树的深度7、Root(T) 返回根结点8、Parent(T,x) 返回结点 x 的双亲9、Child(T,x,i) 返回结点 x 的第i 个孩⼦10、InsertChild(&T,&p,i,x) 把 x 插⼊到 P的第i棵⼦树处11、DeleteChild(&T,&p,i) 删除结点P的第i棵⼦树12、traverse(T) 遍历树的结点：包含⼀个数据元素及若⼲指向⼦树的分⽀。

●结点的度: 结点拥有⼦树的数⽬●叶结点: 度为零的结点●分枝结点: 度⾮零的结点●树的度: 树中各结点度的最⼤值●孩⼦: 树中某个结点的⼦树的根●双亲: 结点的直接前驱●兄弟: 同⼀双亲的孩⼦互称兄弟●祖先: 从根结点到某结点j 路径上的所有结点（不包括指定结点）。

5(选讲)树和二叉树解析

5(选讲)树和二叉树解析

树。所以树的定义是递归的 。
2018/10/13 8
2．树的基本术语
树的结点包含一个数据元素及若干指向其子树的分支。
1. 树的结点:包含一个DE和指向其子树的所有分支; 2. 结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点; 3. 树的度:树中所有结点的度的最大值 Max(D(I)) 含义:树中最大分支数为树的度; 4. 结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结 点为第k层,则其孩子为k+1层. 树中结点的最大层次称为树的深度或高度 5.森林:是m(m>=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换. 6 .有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的 顺序，不得互换，则称为有序树，否则称为无序树。
广度优先（按层次）遍历定义为：先访问第一层结点（即树根结点）， 再从左至右访问第二层结点，依次按层访问 ……，直到树中结点全部被 访问为止。对图6-6 (a)中的树进行按层次遍历得到树的广度优先遍历序 列为：ABCDEFG。 说明： ① 前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。（6.2 节将介绍二叉树） ② 后序遍历树恰好等价于中序遍历该树所对应的二叉树。
2018/10/13 13
树的先序遍历算法描述如下： void Preorder(Btree *root) { if (root!=NULL) {printf(“%c\n”,root->data); //访问根结点 //先根遍历k叉树
for(i=0;i<k;i++)
preorder(root->t[i]); //递归前序遍历每一个子结点 }
祖父 家族关系表示： R={<祖父，伯父>,<祖父，父亲>，<祖父，叔父>， <伯父，堂兄>,<伯父，堂姐>，<父亲，本人>， <叔父，堂弟>,<堂兄，侄儿>}

《数据结构及其应用》笔记含答案 第五章_树和二叉树

《数据结构及其应用》笔记含答案 第五章_树和二叉树

第5章树和二叉树一、填空题1、指向结点前驱和后继的指针称为线索。

二、判断题1、二叉树是树的特殊形式。

（）2、完全二叉树中，若一个结点没有左孩子，则它必是叶子。

（）3、对于有N个结点的二叉树，其高度为。

（）4、满二叉树一定是完全二叉树，反之未必。

（）5、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。

（）6、若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。

（）7、不使用递归也可实现二叉树的先序、中序和后序遍历。

（）8、先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。

（）9、赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

（）110、在赫夫曼编码中，出现频率相同的字符编码长度也一定相同。

（）三、单项选择题1、把一棵树转换为二叉树后，这棵二叉树的形态是（A）。

A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

2、由3个结点可以构造出多少种不同的二叉树？（D）A．2 B．3 C．4 D．5解释：五种情况如下：3、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（D）。

A．250 B． 500 C．254 D．501解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。

4、一个具有1025个结点的二叉树的高h为（C）。

A．11 B．10 C．11至1025之间 D．10至1024之间解释：若每层仅有一个结点，则树高h为1025；且其最小树高为⎣log21025⎦ + 1=11，即h在11至1025之间。

《树和二叉树》习题[1]

《树和二叉树》习题[1]

一、选择题1．对于先序遍历和中序遍历结果相同的二叉树为（BF ）；对于先序遍历和后序遍历结果相同的二叉树为（ B ）A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左孩子的二叉树F.所有结点只有右孩子的二叉树。

2．下列关于哈夫曼树的叙述错误的是( D)。

A．哈夫曼树的根结点的权值等于所有叶结点的权值之和B．具有n个叶结点的哈夫曼树共有2n-l个结点C．哈夫曼树是带权外路径长度最短的二叉树D．哈夫曼树一个结点的度可以是0、1或23．设T2是由树T转换得到的二叉树，则T中结点的后序序列是T2结点的( B )。

A．先序序列B．中序序列C．后序序列D．层次序列4．设有一个度为3的树，其叶结点数为n0，度为1的结点数为nl，度为2的结点数为n2，度为3的结点数为n3，则n0与nl，n2，n3满足关系（B ）。

A．n0 =n2+1 B．n0=n2+2*n3+1 C．n0=n2+n3+1 D．n0= nl+n2+n3二、填空题1．一棵有124个叶结点的完全二叉树，最多有______248__个结点。

在有n个结点的哈夫曼树中，其叶子结点数为__2/N+1_______。

2．若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是_____13__。

3．已知某二叉树的先序序列为ABDECF，中序序列为DBEAFC。

则其后序序列为_____DEBFCA_____。

4. 二叉树结点数n与边数e的关系为__N=E+1__________。

5. 己知二叉排序树的先序序列，___能_____唯一确定该二叉排序树。

6. 完全二叉树采用_顺序__存储结构，满足存储空间少，方便的查找任意结点的双亲与孩子。

三、综合题1．设有n个结点的二叉树，度为2的结点数为n2,度为l的结点数为n1，叶结点数为n0，试分别写出哈夫曼树、完全二叉树和单枝二叉树n1的取值。

答案：哈夫曼树：0 在哈夫曼树中，只能有度为0或2 的结点是严格二叉树完全二叉树：当n为奇数时，度为1的结点树为0当n为偶数时，度为1的结点树为1单支二叉树：n1=n-12．找出满足下列条件的二叉树：（1）先序和中序的访问序列相同；根节点没有左孩子的二叉树或者只有根结点（2）中序和后序的访问序列相同；只有左孩子的二叉树（3）先序和后序的访问序列相同；只有根节点的二叉树3．已知二叉树的中序遍历序列为DEBAFCG ，后序遍历序列为EDBFGCA ，试画出该二叉树。

第5章 树与二叉树习题参考答案【VIP专享】

第5章 树与二叉树习题参考答案【VIP专享】

2. 一棵具有 n 个结点的二叉树，其深度最多为 n ，最少为 [log2n]+1 。 3. 一棵具有 100 个结点的完全二叉树，其叶结点的个数为 50 。37 4. 以{5，9，12，13，20，30}为叶结点的权值所构造的哈夫曼树的带权路径长度是 217
对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料电试力卷保相护互装作置用调与试相技互术关，通系电1，力过根保管据护线生高0不产中仅工资2艺料22高试2可中卷以资配解料置决试技吊卷术顶要是层求指配，机置对组不电在规气进范设行高备继中进电资行保料空护试载高卷与中问带资题负料2荷试2，下卷而高总且中体可资配保料置障试时2卷，32调需3各控要类试在管验最路；大习对限题设度到备内位进来。行确在调保管整机路使组敷其高设在中过正资程常料1工试中况卷，下安要与全加过，强度并看工且25作尽52下可22都能护可地1关以缩于正小管常故路工障高作高中；中资对资料于料试继试卷电卷连保破接护坏管进范口行围处整，理核或高对者中定对资值某料，些试审异卷核常弯与高扁校中度对资固图料定纸试盒，卷位编工置写况.复进保杂行护设自层备动防与处腐装理跨置，接高尤地中其线资要弯料避曲试免半卷错径调误标试高方中等案资，，料要编试求5写、卷技重电保术要气护交设设装底备备置。4高调、动管中试电作线资高气，敷料中课并设3试资件且、技卷料中拒管术试试调绝路中验卷试动敷包方技作设含案术，技线以来术槽及避、系免管统不架启必等动要多方高项案中方；资式对料，整试为套卷解启突决动然高过停中程机语中。文高因电中此气资，课料电件试力中卷高管电中壁气资薄设料、备试接进卷口行保不调护严试装等工置问作调题并试，且技合进术理行，利过要用关求管运电线行力敷高保设中护技资装术料置。试做线卷到缆技准敷术确设指灵原导活则。。：对对在于于分调差线试动盒过保处程护，中装当高置不中高同资中电料资压试料回卷试路技卷交术调叉问试时题技，，术应作是采为指用调发金试电属人机隔员一板，变进需压行要器隔在组开事在处前发理掌生；握内同图部一纸故线资障槽料时内、，设需强备要电制进回造行路厂外须家部同出电时具源切高高断中中习资资题料料电试试源卷卷，试切线验除缆报从敷告而设与采完相用毕关高，技中要术资进资料行料试检，卷查并主和且要检了保测解护处现装理场置。设。备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。

云大《数据结构》课程教学课件-第6章 树和二叉树(147P)_OK

云大《数据结构》课程教学课件-第6章 树和二叉树(147P)_OK

^d ^ ^ e ^ 三叉链表
3）二叉链表是二叉树最常用的存储结构。还有其它链接方 法，采用何种方法，主要取决于所要实施的各种运算频度。
例:若经常要在二叉树中寻找某结点的双亲时，可在每个结 点上再加一个指向其双亲的指针域parent，称为三叉链表。
lchild data parent rchild
2021/8/16
2021/8/16
9
6.2 二 叉 树
6.2.1 二叉树的概念
一、二叉树的定义： 二叉树(Binary Tree)是n(n>=0)个结点的有限集，它或者是 空集(n=0)或者由一个根结点和两棵互不相交的，分别称 为根的左子树和右子树的二叉树组成。 可以看出，二叉树的定义和树的定义一样，均为递归定 义。
A
集合3
集合1
BCD
EF
G
集合2
2021/8/16
3
2、树的表示方法 1）树形图法
A
BCD
EF
G
2）嵌套集合法
3）广义表形式 ( A(B, C(E,F), D(G) )
4）凹入表示法
2021/8/16
A B
D
CG
EF
A B C E DF G
4
3、 树结构的基本术语
1）结点的度(Degree)：为该结点的子树的个数。 2）树的度：为该树中结点的最大度数。
7）路径(Path)：若树中存在一个结点序列k1,k2,…,kj,使得ki是 ki+1的双亲(1<=i<j)，则称该结点序列是从ki到kj一条路径 (Path)
路径长度：路径的长度为j-1,其为该路径所经过的边的数 目。
A
BCD
EF
G

第六章-树和二叉树

第六章-树和二叉树

之
树 和 二 叉 树 13
1 2 3 A B C
4 5 6 7 0 D E F
8 0
9 10 0 G
¾ 二叉树顺序存储的算法描述
数 据 结 构
¾ 初始化二叉树
之
树 和 二 叉 树 14
#define Max_Size 100 typedef int TElemType; typedef TElemType SqBT[Max_Size+1]; void InitBT(SqBT bt){//设置空树 int i; for(i=1;i<=Max_Size;i++) bt[i]=0; }
数 据 结 构
之
树 和 二 叉 树 19
¾ 后序遍历顺序二叉树算法 void PostBT(SqBT bt,int i){ if(i>Max_Size||!bt[i]) return; PostBT(bt,2*i); PostBT(bt,2*i+1); printf("%3d ",bt[i]); }
数 据 结 构
之
树 和 二 叉 树 4
5. 孩子结点、双亲结点、兄弟结点、堂兄弟 结点、祖先结点、子孙结点…… 6. 结点的层次从根开始，根为第一层，根的 孩子为第二层；若某结点在第L层，则其 子树的根就在第L+1层。 7. 树的深度或高度：树中结点的最大层次。 8. 有序树：如果将树中结点的各子树看成是 从左至右有次序的；反之，则是无序树。 9. 森林：是m棵互不相交的树的集合。
数 据 结 构
之
树 和 二 叉 树 25
¾ 打印一维数组 void printSq(SqBT bt){ int i; printf("\nSeqArray:"); for(i=1;i<=Max_Size;i++) printf("%3d ",bt[i]); }

数据结构与算法第5章课后答案

数据结构与算法第5章课后答案

page: 1The Home of jetmambo - 第 5 章树和二叉树第 5 章树和二叉树(1970-01-01) -第 5 章树和二叉树课后习题讲解1. 填空题⑴树是n（n&ge;0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m （m＞0）个（）的集合，每个集合都是根结点的子树。

【解答】有且仅有一个，互不相交⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲⑶一棵二叉树的第i（i&ge;1）层最多有（）个结点；一棵有n（n&gt;0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

【解答】2h -1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸深度为k的二叉树中，所含叶子的个数最多为（）。

【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。

⑹具有100个结点的完全二叉树的叶子结点数为（）。

【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。

则该树中有（）个叶子结点。

【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

第5章 树和二叉树

第5章 树和二叉树
A
B A
C
D
E
F
G
H
I
J
K
L
T1
T2
M
2015年10月20日
T3
树的其它表示方式
A D K L F C G E B H M J I
A
A B E K L F C G
B C D
嵌套集合
E
D H M
F
G
H
I
J
I J
K
L
M
凹入表示
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
广义表
2015年10月20日
北京林业大学信息学院
2015年10月20日
二叉树的链式存储
PARENT
lchild
data
rchild
DATA
lchild
data
parent rchild
LCHILD
RCHILD
北京林业大学信息学院
2015年10月20日
二叉链表
A A ^ B D lchild data rchild
B
C
E
G
F
二叉树的五种不同形态
2015年10月20日
练习
具有3个结点的二叉树可能有几种不同形态？普通树呢？ 5种/2种
2015年10月20日
二叉树的抽象数据类型定义
ADT BinaryTree{ 数据对象D: D是具有相同特性的数据元素的集合。 数据关系R: 若D=Φ，则R= Φ ； 若D≠Φ，则R= {H}；存在二元关系： ① root 唯一 //关于根的说明 ② Dj∩Dk= Φ //关于子树不相交的说明 ③ …… //关于数据元素的说明 ④ …… //关于左子树和右子树的说明 //至少有20个 基本操作 P： }ADT BinaryTree

数据结构第六章：树和二叉树

数据结构第六章：树和二叉树

性质2：深度为 的二叉树至多有 个结点(k≥ 性质 ：深度为k的二叉树至多有2 k 1 个结点 ≥1)
证明：由性质 ，可得深度为k 证明：由性质1，可得深度为 的二叉树最大结点数是
(第i层的最大结点数 ) = ∑ 2 i 1 = 2 k 1 ∑
i =1 i =1
k
k
10
性质3：对任何一棵二叉树 ，如果其终端结点数(即 性质 ：对任何一棵二叉树T，如果其终端结点数 即 叶节点)为 度为2的结点数为 的结点数为n 叶节点 为n0，度为 的结点数为 2，则n0=n2+1 证明： 为二叉树 中度为1的结点数 为二叉树T中度为 证明：n1为二叉树 中度为 的结点数 因为：二叉树中所有结点的度均小于或等于2 因为：二叉树中所有结点的度均小于或等于 所以：其结点总数n=n0+n1+n2 所以：其结点总数 又二叉树中，除根结点外， 又二叉树中，除根结点外，其余结点都只有一个 分支进入； 分支进入； 为分支总数， 设B为分支总数，则n=B+1 为分支总数 又：分支由度为1和度为 的结点射出，∴B=n1+2n2 分支由度为 和度为2的结点射出， 和度为 的结点射出 于是， 于是，n=B+1=n1+2n2+1=n0+n1+n2 ∴n0=n2+1
7
结点A的度：3 结点 的度： 的度 结点B的度：2 结点 的度： 的度 结点M的度：0 结点 的度： 的度 结点A的孩子： ， ， 结点 的孩子：B，C，D 的孩子 结点B的孩子 的孩子： ， 结点 的孩子：E，F 树的度： 树的度：3 E K 结点A的层次： 结点 的层次：1 的层次 结点M的层次 的层次： 结点 的层次：4 L B F A C G H M

数据结构 第六章 树和二叉树

数据结构 第六章 树和二叉树

F
G
H
M
I
J
结点F，G为堂兄弟 结点A是结点F，G的祖先
5
树的基本操作
树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作： 1）InitTree(&T); 2）DestroyTree(&T); 3）CreateTree(&T, definition); 4）ClearTree(&T); 5）TreeEmpty(T); 6）TreeDepth(T); 7） Root(T); 8） Value(T, &cur_e); 9） Assign(T, cur_e, value); 10）Paret(T, cur_e); 11）LeftChild(T, cur_e); 12）RightSibling(T, cur_e); 13）InsertChild(&T, &p, i, c); 14）DeleteChild(&T,&p, i); 15）TraverseTree(T, Visit( ));
1
2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2
1
3
5 7
证明：设二叉树中度为1的结点个数为n1 根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2
又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点 数为 n0*0+n1*1+n2*2(分支数） 而一棵二叉树中，除根结点外所有都为孩子结点，故该二叉 树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1
文件夹1
文件夹n

第六章 树与二叉树

第六章 树与二叉树
44
森林的遍历
(4) 广度优先遍历(层次序 遍历) ：
数据结构
若森林F为空，返回； 否则 依次遍历各棵树的根 结点； 依次遍历各棵树根结 点的所有子女； 依次遍历这些子女结 森林的二叉树表示 点的子女结点。
45
二叉树的计数 由二叉树的前序序列和中序序列可唯 一地确定一棵二叉树。例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如 下：
三个结点构成的不同的二叉树
8
用二 叉 树 表达实际问题
例2 双人比赛的所有可能的结局
开始
甲
开局连赢两局 或五局三胜
乙
甲
甲 甲 乙
乙
乙 甲 乙 甲 甲 乙
甲
乙 甲
乙
乙
甲
乙甲
乙
甲
乙 甲 乙
二叉树的性质
数据结构
性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2i －1个结点。(i 1) [证明用数学归纳法] 性质2 高度为k的二叉树最多有 2k-1个结点。 (k 0) [证明用求等比级数前k项和的公式]
前序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 – 访问根结点 (V)； – 前序遍历左子树 (L)； – 前序遍历右子树 (R)。
遍历结果 -+a*b-cd/ef
27
数据结构
后序遍历 (Postorder Traversal)
后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 – 后序遍历左子树 (L)； – 后序遍历右子树 (R)； – 访问根结点 (V)。
数据结构
36
左子女-右兄弟表示法 第一种解决方案

第五章习题

第五章习题

三、填空题
9． n个结点的各棵树中，其深度最小的那棵树的深度 是 2 。它共有 n-1 个叶子结点和 1 个非叶子结点， 其中，深度最大的那棵树的深度是 n ，它共有 1 个 叶子结点和 n-1 个非叶子结点。
10．先根遍历树林正好等同于 先序 遍历对应的二叉树，后 根遍历树林正好等同于按 中序 遍历对应的二叉树。 11．若一个二叉树的叶子结点是某子树的中序遍历序列中的 前序 最后一个结点，则它必是该子树的______序列中的最后一个 结点。
C,E,F,G,
二、判断题
× 1.二叉树是度为2的有序树。
× 2. 完全二叉树一定存在度为1的结点。 √
√
3．深度为K的二叉树中结点总数≤2k-1。 4. 一个树的叶结点，在前序遍历和后序遍历 下，皆以相同的相对位置出现。 但是，如果我们还知道该树的根结点是哪一个， 则可以确定这棵二叉树。 一个栈。
C A
10．深度为h的满m叉树的第k层有（ ）个结 点。(1=<k=<h) A．mk-1 B．mk-1 C．mh-1 D．mh-1
一、选择题
11．高度为 K的二叉树最大的结点数为（ A．2k B．2k-1 C．2k -1 D．2k-1-1 12. 一棵树高为K的完全二叉树至少有（ A．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k ）。
第五章 树和二叉树
习题讨论
、选择题
1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式 为ABC*+DE/-，其前缀形式为( ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
D
C
2. 设有一表示算术表达式的二叉树（见下图），它所表示的算 术表达式是（ ） A. A*B+C/(D*E)+(F-G) / B. (A*B+C)/(D*E)+(F-G) + + C * C. (A*B+C)/(D*E+（F-G）) * D E F G D. A*B+C/D*E+F-G A B
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
t->c[i]=creaTree(); return t;
3度树，#代表NULL，建树输入序列为：
ABE###F####C###DGI## #J###K###H####
}
编程：建树，并返回树根和该树中结点数量。
要知其然，更要知其所以然。
13/65
m度树的前序遍历建树算法
tree * creaTree (){
if (t->c[i]!=NULL){ printf(","); kuohao(t->c[i]);}
A( B, C( F,G,H), D, E(J,I) )
printf(")");
}
要知其然，更要知其所以然。
20/65
算法：括号表示转孩子指针表示
假定m度树t的括号表示存于a[0..len-1]中。
void creaTree ( tree **t ){
int i; tree* t;
int i;
char c=getchar();
char c=getchar();
if (c=='#') return NULL; if (c=='#' ) { *t=NULL; return; }
t= malloc(sizeof(tree)); *t=malloc(sizeof(tree));
8 I -1 -1 -1
9 J -1 -1 -1
10 K -1 -1 -1
要知其然，更要知其所以然。
7/65
树的存储结构：孩子指#d针efin表e m示3 法
A
B CD
EF G
H
IJK
typedef struct k{ char data; struct k* c[m];
} tree; root
A
分析：括号表示转孩子指针表示，实质是根据括号表示建树。根 据树的定义，建树必须区分出根和子树，怎样区分？
括号表示中含：字母、"("、")"、","等字符，遇到各表示何种含义？
1B
4
2 C∧
3D
6
4 E∧
typedef struct { char data; childNode *firstChild;
} treeNode;
5 F∧
6G
8
7 H∧
8 I∧
typedef struct {
9 J∧
node treelist [M]; int length, r、树的 深度或高度
JK
4、树枝、路径及其长度
有关树的更多性质参见
5、有序树、无序树、森林 《离散数学》相关内容。
要知其然，更要知其所以然。
4/65
1.2 树的逻辑结构和存储结A构
B
CD
树型结构的逻辑描述
E
F
G HI
JK
a. 括号表示法
A(B(E,F),C,D(G,H(J,K),I))
特点： "（"前面的元素一定 括号表示：
A(B,C(F,G,H),D,E(J,I))
为某棵树或子树的根结点。
要知其然，更要知其所以然。
18/65
算法：输出树的括号表示 A B C DE
括号表示规则：
1、空树不表示； 2、若树t只有根，则K(t)=A； 3、否则， K(t)=A( K(T1) ,K(T2),…, K(Tm) )
m度树的前序遍历建树算法
tree * creaTree (){ int i; tree* t; char c=getchar(); if (c=='#') return NULL; t= malloc(sizeof(tree));
A
B CD
EF G
H
IJK
t->d=c; for (i=0; i<m; i++)
江西师范大学·计算机信息工程学院·计算机科学系
目录
第1章 绪论和预备知识 第2章 线性表 第3章 字符串、数组和特殊矩阵 第4章 递归技术 第5章 树和二叉树 第6章 图 第7章 检索 第8章 内排序
要知其然，更要知其所以然。
2/65
第5章 树和二叉树
树
本章重点
基本概念和术语 逻辑和存储结构 遍历及线性表示
0、空则返回； 1、输出左括号"("； 2、输出第1个非空孩子； 3、对其余非空孩子，按：
"，孩子" 形式输出； 4、输出右括号")".
while(i<m && t->c[i]==NULL) i++; if (i>=m) return; //无子则返回 printf("( "); kuohao(t->c[i]); i++; for(i=i; i<m; i++)
kuohao(t->c[i]);
printf(","); } printf(")"); }
优化使 其符合 预期。
要知其然，更要知其所以然。
19/65
算法：输出树的括号表示 void kuohao(tree *t){ int i=0;
美化输出算法思想
if (t==NULL) return; printf("%c ", t->d);
p=出队元素；
p=outQueue(Q);
访问p;
Visit(p);
p的所有非空孩子依次入队；
p的所有孩子依次入队;
}
}
}
要知其然，更要知其所以然。
15/65
算法：输出树的凹入表示
B
E
F
A
C
D
G HI
JK
分析：
1、自上而下输出有何规律？ 2、包含空格、字符、#，且每行 总长固定。空格数如何变化？
A
B ^ C^^^ D ^
E^^^ F^^^ G
H ^^^
I^^^ J^^^ K^^^
要知其然，更要知其所以然。
8/65
树的A存储结构：孩子链表表示法
B CD
EF G
H
IJK
root
data firstChild
0A
1
# define M 50 typedef struct c {
int child; struct c* next; } childNode;
5F 1
6G 3
7H 3
8I 6
9J 6
10 K 6
要知其然，更要知其所以然。
6/65
树的存储结构：孩子数组表示法
A BC EF G
IJ
#define M 100 #define m 3 typedef struct {
char data; int c[m]; } node;
data c[0] c[1] c[2]
二叉树 基本概念和性质 存储结构 遍历和相关算法
1. 掌握树的链式存储结构，以及树 的各种遍历算法；
2. 掌握二叉树的相关基本性质； 3. 掌握二叉树遍历的递归算法，以
及前序、中序的非递归算法、 4. 掌握二叉树与树/森林相互转换；
穿线树、二叉树和树/森林间的相互转换
要知其然，更要知其所以然。
凹
B
入
E
表
F
示
C
法
D
G
H
J
K
I
要知其然，更要知其所以然。
16/65
算法：输出树的凹入表示
B
E
F
A
C
D
G HI
JK
总体采用前序遍历：
算 if ( t==NULL) return; 法 输出根; 思 调整空格和#号数量， 想 按相同方式
输出所有孩子；
void aoruOut(tree * t, int kg, int jh){ int i;//kg：空格数，jh：#数 if (t==NULL) return; /*下面四行输出根*/ for(i=1; i<=kg; i++) printf(" "); printf("%c ",t->d); for(i=1; i<=jh; i++) printf("##"); printf("\n"); for(i=0; i<m; i++)//输出所有孩子 aoruOut(t->c[i], kg+2, jh-2);
}
要知其然，更要知其所以然。
17/65
树的线性表示：括号表示
假定t由根A和其m棵子树T1，T2，……Tm构成，K(t)是t的括号表示
括号表示规则：
1、空树不表示； 2、若树t只有根，则K(t)=A； 3、否则， K(t)=A( K(T1) ,K(T2),…, K(Tm) )
A B C DE
FGHJ I
层次遍历：空树返回；否则从根开始从上至下从左至右逐层遍历各个结点。
A
B CD
EF G
H
IJK
前序遍历：ABEFCDGIJKH
后序遍历：EFBCIJKGHDA
层次遍历：ABCDEFGHIJK
关键：类似于以 ab+ 作为公 式书写逆波兰式。
要知其然，更要知其所以然。
11/65
m度树的前序/后序遍历算法
(C) A
(b) 嵌套 集合 表示 法
A C
B EF
D G
I
HK J
B
凹
E