当前位置：文档之家 › 数据结构第6章2

数据结构第6章2

  • 格式：ppt
  • 大小：454.50 KB
  • 文档页数：78

下载文档原格式

  / 78

合集下载

数据结构-6 树和二叉树

数据结构-6 树和二叉树

第六章树和二叉树一．选择题1. 以下说法错误的是。

A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。

图6-2 4 棵二叉树3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。

A. t->left == NULLB. t->ltag==1C. t->ltag==1 且t->left==NULL D .以上都不对4. 以下说法错误的是。

A.二叉树可以是空集B.二叉树的任一结点最多有两棵子树C.二叉树不是一种树D.二叉树中任一结点的两棵子树有次序之分5. 以下说法错误的是。

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好6. 如图6-3所示的4 棵二叉树，是平衡二叉树。

图6-3 4 棵二叉树7. 如图6-4所示二叉树的中序遍历序列是。

A. abcdgefB. dfebagcC. dbaefcgD. defbagc图6-4 1 棵二叉树8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。

A. acbedB. decabC. deabcD. cedba9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。

A. 前序B.中序C. 后序D. 层次序10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。

数据结构(c语言)第6章二叉树课练答案(含完整实验程序刘玉保留

数据结构(c语言)第6章二叉树课练答案(含完整实验程序刘玉保留

第6章树和二叉树自测卷解答姓名班级一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（×）2.二叉树中每个结点的两棵子树的高度差等于1。

（√）3.二叉树中每个结点的两棵子树是有序的。

（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。

（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。

（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（正确。

用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。

由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。

）即有后继链接的指针仅n-1个。

（√）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有5种形态。

2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

3．一棵具有２５７个结点的完全二叉树，它的深度为9。

（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。

数据结构(朱战立)章 (6)

数据结构(朱战立)章 (6)
30
Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 3 from Peg A to Peg B Move Disk 1 from Peg C to Peg A Move Disk 2 from Peg C to Peg B Move Disk 1 from Peg A to Peg B Move Disk 4 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 2 from Peg B to Peg A Move Disk 1 from Peg C to Peg A
" from peg "， fromPeg， " to peg
/*把n-1个圆盘从auxPeg借助fromPeg移至
29
towers(n-1，auxPeg，toPeg，fromPeg); }设计一个测试主函数如下： ＃include <stdio.h> void main(void) {
Towers(4， 'A'， 'C'， 'B'); }程序运to Peg B
26
Move Disk i from Peg X to Peg Y 这样， 汉
诺塔问题的递归算法可设计如下： void towers(int n，
char fromPeg， char toPeg， char auxPeg)
{
if(n＝＝1)
/*递归出口*/
{
printf("%s%c%s%c＼n"， "move disk
并不是每个问题都适宜于用递归算法求解。 适宜于用递归 算法求解的问题的充分必要条件是：

《数据结构(C语言版 第2版)》(严蔚敏 著)第六章练习题答案

《数据结构(C语言版 第2版)》(严蔚敏 著)第六章练习题答案

《数据结构（C语言版第2版）》（严蔚敏著）第六章练习题答案第6章图1．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。

A．1/2B．1C．2D．4答案：C（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A．1/2B．1C．2D．4答案：B解释：有向图所有顶点入度之和等于所有顶点出度之和。

（3）具有n个顶点的有向图最多有（）条边。

A．n B．n(n-1)C．n(n+1)D．n2答案：B解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。

（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。

A．n B．2(n-1)C．n/2D．n2答案：B所谓连通图一定是无向图,有向的叫做强连通图连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

A．7B．8C．9D．10答案：C解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。

（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。

A．非连通B．连通C．强连通D．有向答案：B解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。

（7）下面（）算法适合构造一个稠密图G的最小生成树。

A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法答案：A解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。

（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

A．栈 B.队列 C.树D．图答案：B解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。

数据结构-C语言描述(第三版)(陈慧南)章 (6)

数据结构-C语言描述(第三版)(陈慧南)章 (6)

第6章 树 例如，设有序表为(21, 25, 28, 33, 36, 43)，若要在表中 查找元素36，通常的做法是从表中第一个元素开始，将待查元素 与表中元素逐一比较进行查找，直到找到36为止。粗略地说，如 果表中每个元素的查找概率是相等的，则平均起来，成功查找一 个元素需要将该元素与表中一半元素作比较。如果将表中元素组 成图6－3所示的树形结构，情况就大为改观。我们可以从根结点 起，将各结点与待查元素比较，在查找成功的情况下，所需的最 多的比较次数是从根到待查元素的路径上遇到的结点数目。当表 的长度n很大时，使用图6－3所示的树形结构组织表中数据，可 以很大程度地减少查找所需的时间。为了查找36，我们可以让36 与根结点元素28比较，36比28大，接着查右子树，查找成功。显 然，采用树形结构能节省查找时间。
第6章 树
E
E
A
F
B
G
CD
LJ
M
N
T1
X
YZ
U T2
B
F
A
DC
G
JL
T3 N
M
(a)
(b)
图6－2 树的例子
(a) 树T1和T2组成森林；(b) 树T3
第6章 树
6.2 二 叉 树
二叉树是非常重要的树形数据结构。很多从实际问题中抽 象出来的数据都是二叉树形的，而且许多算法如果采用二叉树 形式解决则非常方便和高效。此外，以后我们将看到一般的树 或森林都可通过一个简单的转换得到与之相应的二叉树，从而 为树和森林的存储及运算的实现提供了有效方法。
第6章 树
图6－1描述了欧洲部分语言的谱系关系，它是一个后裔图， 图中使用的描述树形结构数据的形式为倒置的树形表示法。在 前几章中，我们学习了多种线性数据结构，但是一般来讲，这 些数据结构不适合表示如图6－1所示的层次结构的数据。为了 表示这类层次结构的数据，我们采用树形数据结构。在本章中 我们将学习多种不同特性的树形数据结构，如一般树、二叉树、 穿线二叉树、堆和哈夫曼树等。

数据结构第六章题目讲解

数据结构第六章题目讲解

数据结构第六章题⽬讲解02⼀选择题：1、以下说法错误的是①树形结构的特点是⼀个结点可以有多个直接前趋②线性结构中的⼀个结点⾄多只有⼀个直接后继③树形结构可以表达(组织)更复杂的数据④树(及⼀切树形结构)是⼀种"分⽀层次"结构⑤任何只含⼀个结点的集合是⼀棵树2．深度为6的⼆叉树最多有( )个结点①64 ②63 ③32 ④313 下列说法中正确的是①任何⼀棵⼆叉树中⾄少有⼀个结点的度为2②任何⼀棵⼆叉树中每个结点的度都为2 ⼆叉树可空③任何⼀棵⼆叉树中的度肯定等于2 ④任何⼀棵⼆叉树中的度可以⼩于24 设森林T中有4棵树，第⼀、⼆、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成⼀棵⼆叉树后，且根结点的右⼦树上有（）个结点。

①n1-1 ②n1③n1+n2+n3④n2+n3+n4⼆．名词解释：1 结点的度 3。

叶⼦ 4。

分⽀点 5。

树的度三填空题⼆叉树第i(i>=1)层上⾄多有_____个结点。

1、深度为k(k>=1)的⼆叉树⾄多有_____个结点。

2、如果将⼀棵有n个结点的完全⼆叉树按层编号，则对任⼀编号为i(1<=i<=n)的结点X有：若i=1,则结点X是_ ____；若i〉1,则X的双亲PARENT(X)的编号为__ ____。

若2i>n，则结点X⽆_ _____且⽆_ _____；否则，X的左孩⼦LCHILD(X)的编号为____。

若2i+1>n，则结点X⽆__ ____；否则，X的右孩⼦RCHILD(X)的编号为_____。

4．以下程序段采⽤先根遍历⽅法求⼆叉树的叶⼦数，请在横线处填充适当的语句。

Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶⼦数count的初值为0*/ {if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))__ __;countleaf(t->lchild,&count);countleaf(t->rchild,&count);}}5 先根遍历树和先根遍历与该树对应的⼆叉树，其结果_____。

数据结构第六章二叉树的应用教案


6.3 哈夫曼树
• • 最优树的定义 如何构造最优树
6.3.1 基本术语
路径和路径长度
若在一棵树中存在着一个结点序列 k1,k2,…,kj，使得ki是ki+1的 双亲(1≤i<j)，则称此结点序列是 从k1到kj的路径从k1到kj所经过的 分支数称为这两点之间的路径长度
结点的权和带权路径长度
权 给结点赋上一个有某种意义 的实数，我们称为权。 带权路径长度 从根结点到该结点之间路径 长度与该结点上权的乘积。
23 设 key = 48
T
20 10 T 23 T 25
T T
30
T
40 35 T
bool Find(BTreeNode* T, ElemType& item) if(T==NULL) return false; //查找失败 else { if(item==T->data) { item=T->data; return true; } else if(item<T->data) //向左子树继续查找 return Find(T->left, item); else return Find(T->right, item); } //向右子树继续查找
ri r2i ri r2i 1
(小顶堆)
或
ri r2i ri r2i 1
(大顶堆)
12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49
是小顶堆
12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49
不是堆
子树上查找；
3）大于根结点的关键字，则继续在右
子树上查找。

云大《数据结构》课程教学课件-第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

数据结构第06章广义表

第6章广义表z6.1 广义表的基本概念z6.2 广义表的存储结构z6.3 广义表的操作算法16.1 广义表的基本概念广义表（列表）的概念-n( ≥0 )个表元素组成的有限序列，记作LS= ( a1, a1, a2, …, a n)LS是表名，a i是表元素，它可以是单个元素(称为原子) ，可以是表(称为子表) 。

n为表的长度。

n= 0 的广义表为空表。

n> 0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。

2广义表举例：（1）A=（）（2）B=（e）（3）C=（a, (b, c, d) )（4）D=（A，B，C）（5）E= (a , E）9任意一个非空广义表，均可分解为表头和表尾。

9对于一个非空广义表，其表头可能是原子，也可能是子表；而表尾一定是子表。

3广义表的基本操作：•结构的创建和销毁InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);•状态函数GListLength(L); GListDepth(L);GListEmpty(L); GetHead(L); GetTail(L);•插入和删除操作InsertFirst_GL(&L, e);DeleteFirst_GL(&L, &e);•遍历Traverse_GL(L, Visit());66. 2 广义表的存储结构z由于广义表中的元素不是同一类型，因此难以用顺序结构表示，通常采用链接存储方法存储广义表，并称之为广义链表。

z由于广义表中有两种数据元素，原子或子表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。

z下面介绍一种广义表的链式存储结构。

78扩展的线性链表表示法：-子表结点由三个域组成：标志域、表头指针域和指向下一个元素的指针域；-原子结点的三个域为：标志域、值域和指向下一个元素的指针域。

《数据结构——C语言描述》第6章：树

Void paintleaf (Btree root) { if (root!=NULL) { if (root ->Lchild==NULL && root ->Rchild==NULL) printf (root ->data); paintleaf (root ->Lchild); paintleaf (root -遍历左子树； （2）访问根结点； （3）中根遍历右子树。 后根遍历二叉树 （1）后根遍历左子树； （2）后根遍历右子树； （3）访问根结点。
先根遍历: -+a*b–cd/ef 中根遍历: a+b*c–d–e/f 后根遍历: abcd-*+ef/-
typedef struct Node { datatype data; struct Node *Lchild; struct Node *Rchild; } BTnode,*Btree;
满二叉树：一棵深度为k且有2k-1个结 点的二叉树称为满二叉树。 完全二叉树：深度为k，有n个结点的 二叉树当且仅当其每一个结点都与深度 为k的满二叉树中编号从1至n的结点一一 对应时，称为完全二叉树。
1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2
1 3 5 7
树的度：树中最大的结点的度数即为 树的度。图6.1中的树的度为3。 结点的层次(level)：从根结点算起， 根为第一层，它的孩子为第二层……。 若某结点在第l层，则其孩子结点就在 第l+1层。图6.1中，结点A的层次为1， 结点M的层次为4。 树的高度(depth)：树中结点的最大层 次数。图6.1中的树的高度为4。 森林(forest)：m(m≥0)棵互不相交的 树的集合。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 兄弟(sibling)结点 具有同一双亲的所有结点 • 祖先(ancestor)结点 从根到该结点所经分支上的 所有结点。 • 子孙(descendant)结点 以某一结点 为根的子树中的 任一结点。 • 结点所处层次(level) 根结点的层数为1，其余结点 的层数为双亲结点的层数加1 • 树的深度(depth) 树中结点的最大层数
2013-6-27 8
二叉树 (Binary Tree)
二叉树的定义
一棵二叉树是结点的一个有限集合，该集合 或者为空，或者是由一个根结点加上两棵分别称 为左子树和右子树的、互不相交的二叉树组成。
2013-6-27
二叉树的五种不同形态
9
二叉树的性质
性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2i-1 个结点。(i 0) 证明：i = 1 时，有2i-1 = 20 =1，成立
33
• 2、求二叉树的深度(后序遍历) • int Depth (BiTree T ) • • • • • • • • • { if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft>depthRight?depthLeft:depthRight);
6.5 线索二叉树 • 何谓线索二叉树？ • 遍历二叉树的结果是，求得结点的一个线性 序列。 • 指向该线性序列中的“前驱”和“后继”的 指针，称作“线索” • 包含“线索”的存储结构，称作“线索链 表”； • 与其相应的二叉树，称作“线索二叉树”
有序树 无序树 森林

2013-6-27
子树的次序不能互换 子树的次序可以互换 互不相交的树的集合
7
树的基本操作
1、初始化 2、求指定结点所在树的根结点 3、求指定结点的双亲结点 4、求指定结点的某一孩子结点 5、求指定结点的最右边兄弟结点 6、将一棵树插入到另一树的指定结点下作为它 的子树 7、删除指定结点的某一子树 8、树的遍历
至多为：
20 + 21 + 22 + 23 + … + 2k-1 = 2k － 1
2013-6-27 11
性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2, 则有 n0＝n2＋1
证明： 1、结点总数为度为0的结点加上度为1的结点再加上度 为2的结点： n = n0 + n1 + n2 2、另一方面，二叉树中一度结点有一个孩子，二 度结 点有二个孩子，根结点不是任何结点的孩子，因此， 结点总数为： n = n1 + 2n2 + 1 3、两式相减，得到：
2013-6-27
28
中序遍历
中序遍历二叉树算法的框架是： • 若二叉树为空，则空操作； • 否则 – 中序遍历左子树 (L)； – 访问根结点 (V)； – 中序遍历右子树 (R)。 遍历结果 a+b*c-d-e/f
2013-6-27
表达式语法树29
中序遍历算法
INORDER(bitree *cnt) { if (cnt) { INORDER(t->lch); printf(“\t%c\n”,t->data);
• • • • • • • • •
2013-6-27
遍历算法的应用举例: 1、统计二叉树中叶子结点的个数(先序遍历) void CountLeaf (BiTree T, int& count) { if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; CountLeaf( T->lchild, count); // 统计左子树中 叶子结点个数 • CountLeaf( T->rchild, count); // 统计右子树中 叶子结点个数 • } • }
lchild
data
rchild
parent
其中，data、lchild以及rchild三个域的意义同二叉 链表结构；parent域为指向该结点双亲结点的指针。 既便于查找孩子结点，又便于查找双亲结点； 相对于二叉链表存储结构而言，它增加了空间开销。
2013-6-27
24
链表表示
2013-6-27
单支树
21
• •
2．链式存储结构 用链表来表示一棵二叉树，即用链来指示着元素的 逻辑关系。通常有两种形式。 • （1）二叉链表存储 • 链表中每个结点由三个域组成，除了数据域外，还有 两个指针域，分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址。当左孩子或右孩子不存在时， 相应指针域值为空（用符号∧或NULL表示）。 •
Ø Ø F G
A B
2013-6-27
C
D E
Ø Ø Ø Ø F
G
20
由于一般二叉树必须仿照完全二叉树那样存 储，可能会浪费很多存储空间，单支树就是 一个极端情况。
•
A B C D
A
B C
D
A ∧B ∧∧∧C ∧∧∧∧∧∧∧D
• (a) 一棵右单支二叉树 (b) 改造后的右单支树对应的完全二叉树
2013-6-27
3
凹入表表示
a
b d e
i j f c g h
2013-6-27 4
嵌套集合表示
a
b
d i
e
j f g
c
h
广义表表示
(a ( b ( d, e ( i, j ),f), c ( g, h ) ) )
2013-6-27 5
1 2
4
3
4
• 结点(node)： • 结点的度(degree)： • 树的度(degree)： • 分支(branch)结点： • 叶(leaf)结点： • 孩子(child)结点： 2013-6-27 • 双亲(parent)结点： 数据元素 + 若干指向子树的分支 结点的子树个数 树中所有结点的度的最大值 度不为0的结点 度为0的结点 某结点子树的根结点 6 某个结点是其子树之根的双亲
2013-6-27 27
•
D 1 L 2 R 3
• 若以D、L、R分别表示访问根结点、遍历根结点的左子 树、遍历根结点的右子树，则二叉树的遍历方式有六 种：DLR、LDR、LRD、DRL、RDL和RLD。 • 限定先左后右，则有三种方式，即DLR（称为先序遍 历）、LDR（称为中序遍历）和LRD（称为后序遍历）。
• } • return depthval;
• }
2013-6-27 34
• 3、建立二叉树的存储结构
• 按给定的先序序列建立二叉链表 • Status CreateBiTree(BiTree &T) { • // 按先序次序输入二叉树中结点的值（一个字符）， 空格字符 表示空树，构造二叉链表表示的二叉树T。 • scanf(&ch); • if (ch==' ') T = NULL; • else { • if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) • exit(OVERFLOW); • T->data = ch; // 生成根结点 • CreateBiTree(T->lchild); // 构造左子树 • CreateBiTree(T->rchild); // 构造右子树 • } 2013-6-27 return OK; } // CreateBiTree 35 •
2013-6-27
22
• 二叉树的链式存储表示
• • • •
typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 • } BiTNode, *BiTree;
2013-6-27
23
• （2）三叉链表存储 • 每个结点由四个域组成，具体结构为： •
2013-6-27
n0 = n2 + 1
12
定义1 满二叉树(Full Binary Tree) 一棵深度为k 且有2k-1个结点的二叉树。 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除 第h层外，其它各层(1h-1)的结点数都达到 最大个数，第h层从右向左连续缺若干结点， 这就是完全二叉树。
2013-6-27 13
1 2 4 5 3 6 7
满二叉树
1
2 3 2
1
3 2
1
3 6 7
4
5
6
4
5
7
(a)完全二叉树
2013-6-27
(b)非完全二叉树
( c)非完全二叉树
14
性质4 具有n个结点的完全二叉树的高度
为 log2n +1
证明：设完全二叉树的高度为h，则有
2h-1 - 1 < n 2h - 1 2h-1 <= n < 2h

若i == 1, 则 i 无双亲 若i > 1, 则 i 的双亲为i /2

若2*i <= n, 则 i 的左子女为2*i；否则，i无左子女，必 若2*i+1 <= n, 则 i 的右子女为2*i+1，否则，i无右子
定是页结点，二叉树中i> n/2 的结点必定是页结点 女

2013-6-27 16
25
二叉树链表表示的示例
2013-6-27 26

6.3 遍历二叉树和线索二叉树