当前位置：文档之家 › 第06章-树和二叉树

第06章-树和二叉树

  • 格式：ppt
  • 大小：2.66 MB
  • 文档页数：206

下载文档原格式

  / 206

合集下载

树和二叉树 PPT课件

树和二叉树 PPT课件

C
E
D
F
C
D
C

D
F
E F 二叉链表
E
二叉树
三叉链表
三叉链表的静态结构
root data parent lchild rchild 0 1 2 3 4 5 A B C D E F -1 0 1 1 3 3 1 2 -1 4 -1 -1 -1 3 -1 5 -1 -1
A
B C E D F
0
1 3 7 8 9 4 5
2 6
4. 二叉树的存储结构
顺序表示
1
2 4 5 6 3 7 7 4 8 2 5 9 1 3 6 10 9
8 9 10
1 2 3 4 5 6 7 8 910
完全二叉树 的顺序表示
1 2 3 4 0 5 6 7 8 0 0 0 0 910
一般二叉树 的顺序表示
链表表示
第六章 树和二叉树




1. 2. 3. 4. 5. 6.
树的定义和基本术语 二叉树 遍历二叉树与线索二叉树 树与森林 赫夫曼树 及其应用 二叉树的计数
6.1 树的定义和基本术语
树的定义
树是由 n (n 0) 个结点组成的有限集合。如果 n = 0， 称为空树；如果 n > 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直 接后继，但没有直接前驱； 当n > 1，除根以外的其它结点划分为 m (m >0) 个互不 相交的有限集 T1, T2 ,…, Tm，其中每个集合Ti本身又是一 棵树，并且称为根的子树(SubTree)。
特点
每个结点至多只有两棵非空子树（二叉树中 不存在度大于2的结点）
2.五种形态

数据结构树和二叉树习题及答案

数据结构树和二叉树习题及答案

习题六树和二叉树一、单项选择题1．以下说法错误的是（）A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达（组织）更复杂的数据D.树（及一切树形结构）是一种”分支层次”结构E.任何只含一个结点的集合是一棵树2.下列说法中正确的是（）A.任何一棵二叉树中至少有一个结点的度为 2B.任何一棵二叉树中每个结点的度都为 2C.任何一棵二叉树中的度肯定等于 2D.任何一棵二叉树中的度可以小于 23.讨论树、森林和二叉树的关系，目的是为了（）A.借助二叉树上的运算方法去实现对树的一些运算B.将树、森林按二叉树的存储方式进行存储C.将树、森林转换成二叉树D.体现一种技巧，没有什么实际意义4．树最适合用来表示（）A.有序数据元素 B .无序数据元素C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C ．15 D ．不确定6.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F对应的二叉树根结点的右子树上的结点个数是（）。

A．M1 B ．M1+M2 C ．M3 D ．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250 B ．500 C ．254 D ．505 E ．以上答案都不对8.设给定权值总数有n 个，其哈夫曼树的结点总数为（）A.不确定 B . 2n C . 2n+1 D . 2n-19.二叉树的第I层上最多含有结点数为（）I I-1 I-1 IA．2I B ．2I-1-1 C ．2I-1D ．2I-110．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+111.利用二叉链表存储树，则根结点的右指针是（）。

《数据结构》习题汇编06第六章树和二叉树试题

《数据结构》习题汇编06第六章树和二叉树试题

第六章树和二叉树试题一、单项选择题1.树中所有结点的度等于所有结点数加（）。

A. 0B. 1C. -1D. 22.在一棵树中，（）没有前驱结点。

A. 分支结点B. 叶结点C. 根结点D. 空结点3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。

A. 2B. 1C. 0D. -14.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。

A. nB. n-1C. n+1D. 2*n5.在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），最多具有（）个结点。

A. 2iB. 2i+1C. 2i-1D. 2n6.在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（）。

A. 2h-1B. 2h+1C. 2h-1D. 2h7.在一棵具有35个结点的完全二叉树中，该树的高度为（）。

假定空树的高度为-1。

A. 5B. 6C. 7D. 88.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。

假定树根结点的编号为0。

A. ⎣(n-1)/2⎦B. ⎣n/2⎦C. ⎡n/2⎤D. ⎣n/2⎦ -19.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（）。

假定根结点的编号为0A. 2iB. 2i-1C. 2i+1D. 2i+210.在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结点，其双亲结点的编号为（）。

A. ⎣(i+1)/2⎦B. ⎣(i-1)/2⎦C. ⎣i/2⎦D. ⎣i/2⎦-111.在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（）结点。

A. 兄弟B. 子女C. 祖先D. 子12.在一棵树的静态双亲表示中，每个存储结点包含（）个域。

A. 1B. 2C. 3D. 413.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为（）。

树和二叉树的知识点总结

树和二叉树的知识点总结

树和二叉树的知识点总结一、树的基本概念1. 树的定义：树是一种非线性数据结构，由 n（n>=1）个结点组成的有限集合。

对于每个非终端节点，都有一个被称为根的结点，且除根节点外，其他结点可以分为 m（m>=0）个互不相交的子集合，而每个子集合本身又是一个树。

2. 树的基本特点：树是一种分层数据的抽象模型，具有层级关系的数据结构。

树的结点包括根结点、子节点、叶子结点、父节点等。

3. 树的术语解释：树的根节点是树的顶端结点，没有父节点；子节点是一个结点向下连接的结点；叶子结点是没有子节点的结点；父节点是有一个或多个子节点的结点。

二、树的分类1. 二叉树：一种特殊的树，每个结点最多有两个子结点，分别为左子结点和右子结点。

二叉树的子树有左子树和右子树，必须遵循左子树 < 根节点 < 右子树的顺序。

2. 平衡树：每个结点的左子树和右子树的高度之差不能超过1的二叉树。

3. 满二叉树：每个结点要么没有子节点，要么有两个子节点的二叉树。

4. 完全二叉树：除了最底层，所有层的结点数都达到最大，并且最底层的结点都依次从左到右排列。

三、二叉树的基本概念1. 二叉树的特点：每个结点最多有两个子结点，分别为左子结点和右子结点。

二叉树的子树都遵循左子树 < 根节点 < 右子树的顺序。

2. 二叉树的遍历：分为前序遍历、中序遍历和后序遍历。

前序遍历先访问根节点，再递归左右子树；中序遍历先递归左子树，再访问根节点，最后递归右子树；后序遍历先递归左右子树，最后访问根节点。

3. 二叉树的存储：二叉树的存储方式可以采用链式存储和顺序存储。

链式存储是通过结点间的指针链接，顺序存储是通过数组或列表进行存储。

四、二叉树的应用1. 二叉搜索树：是一种特殊的二叉树结构，对于任意节点，其左子树上的结点值都小于该节点的值，右子树上的结点值都大于该节点的值。

2. 堆：是一种特殊的完全二叉树，分为最大堆和最小堆。

最大堆的每个结点的值都大于或等于其子节点的值，最小堆的每个结点的值都小于或等于其子节点的值。

树和二叉树——精选推荐

树和二叉树——精选推荐

第6章 树和二叉树内容概要：本章主要介绍树，二叉树，最优二叉树的相关概念和操作，存储结构和相应的操作，并在综合应用设计中，给出了对应算法的C 语言实现。

教学目标1．理解各种树和森林与二叉树的相应操作。

2．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其他操作。

3．熟练掌握二叉树和树的各种存储结构及其建立的算法。

4．掌握哈夫曼编码的方法。

5．通过综合应用设计，掌握各种算法的C 语言实现过程。

基本知识点：树和二叉树的定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码重点：二叉树的性质、二叉树的遍历及其应用，构造哈夫曼树。

难点：编写实现二叉树和树的各种操作的递归算法。

本章知识体系结构：课时安排：6个课时树的定义 树树的性质 树的逻辑表示法 树形表示法 树的存储结构 双亲存储结构 文氏表示法凹入表示法 括号表示法 孩子存储结构 孩子双亲存储结构二叉树二叉树的定义 二叉树的性质二叉树的逻辑表示法（采用树的逻辑表示法）二叉树的存储结构二叉树的顺序存储结构先序遍历 中序遍历 后序遍历二叉树的遍历 二叉树的链式存储结构（二叉链） 由先序序列和中序序列构造二叉树 由中序序列和后序序列构造二叉树二叉树的构造 二叉树的线索化 哈夫曼树二叉树和树之间的差别 二叉树与树、森林之间的转换二叉树和树课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握树、二叉树的基本概念和术语，二叉树的性质教学重点二叉树的定义、二叉树的性质、链式存储结构教学难点二叉树的性质、链式存储二叉树的基本操作组织教学一、树的定义二、树的基本概念三、二叉树的定义、性质四、二叉树的顺序存储结构和链式存储结构五、小结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握二叉树遍历的三种方法及二叉树的基本操作教学重点二叉树的遍历算法教学难点中序与后序遍历的非递归算法组织教学一、复习二叉树的定义二、遍历二叉树的三种方法三、递归法遍历二叉树四、二叉树的基本操作五、总结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标理解树与森林的转换，掌握哈夫曼树教学重点哈夫曼树教学难点树与森林的转换组织教学一、导入二、树与森林三、哈夫曼树四、小结作业习题6课堂情况及课后分析前面几章讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，可用于描述客观世界中具有单一前驱和后继的数据关系。

计算机二级考点归纳(树与二叉树)

计算机二级考点归纳(树与二叉树)

•1、树的基本概念树(tree）是一种简单的非线性结构。

在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。

每一个结点可以有多个后件，它们称为该结点的子结点。

没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件个数称为该结点的度。

叶子结点的度为 0。

在树中，所有结点中的最大的度称为树的度。

• 2、二叉树及其基本性质（1）二叉树的定义二叉树是一种很有用的非线性结构，具有以下两个特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。

由以上特点可以看出，在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。

另外，二叉树中的每个结点的子树被明显地分为左子树和右子树。

在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。

当一个结点既没有左子树也没有右子树时，该结点即为叶子结点。

（2）二叉树的基本性质二叉树具有以下几个性质：性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点；性质2：深度为m的二叉树最多有2m-1个结点；性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

性质4：具有n个结点的二叉树，其深度至少为［log2n］+1，其中［log2n］表示取log2n的整数部分。

在二叉树的遍历中，无论是前序遍历，中序遍历还是后序遍历，二叉树的叶子结点的先后顺序都是不变的。

3、满二叉树与完全二叉树满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。

在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m－1个结点。

完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现：对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+1。

数据结构详细教案——树与二叉树

数据结构详细教案——树与二叉树一、教学目标1.了解树和二叉树的基本概念和特点；2.掌握树和二叉树的基本操作；3.能够通过递归遍历树和二叉树。

二、教学重难点1.树和二叉树的基本概念和特点；2.递归遍历树和二叉树。

三、教学内容1.树的概念和特点1.1树的定义树是n（n>=0）个节点的有限集。

当n=0时，称为空树；如果不为空树，则1. 树有且仅有一个特殊节点被称为根（Root）；2.其余节点可分为m（m>0）个互不相交的有限集T1，T2，...，Tm，其中每个集合又是一棵树。

1.2节点间的关系- 父节点（parent）是当前节点的直接上级节点；- 子节点（child）是当前节点的直接下级节点；- 兄弟节点（sibling）是具有同一父节点的节点；- 祖先节点（ancestor）是通过从当前节点到根的任意路径可以到达的节点；- 子孙节点（descendant）是通过从该节点到子树的任意节点可以到达的节点。

1.3树的特点-树是一个有层次的结构，可以看作是一个鱼骨图；-树中的每个节点都可以有多个子节点，但只有一个父节点；-树中的节点之间是唯一的，不存在重复节点；-树中的任意两个节点之间都有且仅有一条路径连接。

2.二叉树的概念和特点2.1二叉树的定义二叉树是一种特殊的树结构，它的每个节点最多只能有两个子节点，分别称为左子节点和右子节点。

2.2二叉树的特点-二叉树的度最大为2，即每个节点最多有两个子节点；-二叉树的第i层最多有2^(i-1)个节点；-对于任意一颗二叉树，如果其叶子节点数为n0，度为2的节点数为n2，则有n0=n2+1；-完全二叉树是一种特殊的二叉树，除了最后一层的叶子节点外，每一层的节点都是满的。

四、教学过程1.讲解树和二叉树的基本概念和特点，引导学生理解树和二叉树的定义和节点间的关系。

2.分析树和二叉树的基本操作，并通过实例演示操作过程，让学生掌握操作的步骤和方法。

3.运用递归算法遍历树和二叉树的过程，详细讲解前序遍历、中序遍历和后序遍历的定义和实现方法。

第六章-树和二叉树


之
树 和 二 叉 树 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]); }

二叉树


6-2-2 二叉树的基本操作与存储实现
1、二叉树的基本操作 Initiate(bt)
Create(x, lbt, rbt)
InsertL(bt, x, parent) InsertR(bt, x, parent) DeleteL(bt,parent) DeleteR(bt,parent)
Search(bt,x)
BiTree DeleteL(BiTree bt, BiTree parent){ BiTree p; if(parent==NULL||parent->lchild==NULL){ cout<<“删除出错”<<endl; return NULL; } p=parent->lchild; parent->lchild =NULL; delete p; return bt ; }
a b c e 0 1 2 3 4 5 a b c d e ^ 6 7 8 9 10 ^ ^ ^ f g
d
f
g
特点：结点间关系蕴含在其存储位置中。浪费空间， 适于存满二叉树和完全二叉树。
二、链式存储结构 1、二叉链表存储法
A
B C E G D B A ^
lchild data rchild
F
^ C ^ typedef struct BiTNode { DataType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; ^ E
二叉树的五种基本形态

A
A
A B
A
B 空二叉树
B
C 左、右子树 均非空
只有根结点 的二叉树
右子树为空
左子树为空

第6-10章 树和二叉树--答案

第6章树和二叉树一、基础知识题1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。

[解答]二叉树的叶结点有⑥、⑧、⑨。

分支结点有①、②、③、④、⑤、⑦。

结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、⑧的层次为3；结点⑨的层次为4。

2．使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。

[解答]（1）顺序表示（2）二叉链表表示3．在结点个数为n（n>1）的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？[解答]结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。

4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

[解答]具有3个结点的树具有3个结点的二叉树5．如果一棵树有n1个度为1的结点，有n2个度为2的结点，…，n m个度为m的结点，试问有多少个度为0的结点？试推导之。

[解答]总结点数n=n0+n1+n2+…+n m总分支数e=n-1= n0+n1+n2+…+n m-1=m×n m+(m-1)×n m-1+…+2×n2+n1则有 n 0=∑=+-mi i n i 21))1((6．试分别找出满足以下条件的所有二叉树：（1） 二叉树的前序序列与中序序列相同； （2） 二叉树的中序序列与后序序列相同； （3） 二叉树的前序序列与后序序列相同。

[解答]（1） 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；（2） 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； （3） 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。

7．填空题（1）对于一棵具有n 个结点的树，该树中所有结点的度数之和为 n-1 。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
5
插入类：
InitTree(&T) // 初始化置空树
CreateTree(&T, definition) // 按定义构造树
Assign(T, cur_e, value) // 给当前结点赋值
InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树
6
删除类：
T3
8
基本术语
9
结点: 数据元素+若干指向子树的分支
结点的度: 分支的个数
树的度: 树中所有结点的度的最大值
叶子结点: 度为零的结点
D
HI J
分支结点: 度大于零的结点
M
10
(从根到结点的)路径：
A
由从根到该结点所
B
CБайду номын сангаас
D
经分支和结点构成。 E F G H I J
孩子结点、双亲结点、 K L
M
兄弟结点、堂兄弟
祖先结点、子孙结点
结点的层次: 假设根结点的层次为1,第l 层
的结点的子树根结点的层次 为l+1
树的深度：树中叶子结点所在的最大层次
11
森林：
root
F
A
是 m（m≥0）棵互 不相交的树的集合
B
C
D
E F GH I J
KL
M
任何一棵非空树是一个二元组
Tree = （root，F） 其中：root 被称为根结点，
不相交的有限集T1, T2, …, Tm, 其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。
3
基本操作： 查找类 插入类 删除类
4
查找类：
Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历
ClearTree(&T) // 将树清空 DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i)
// 删除结点p的第i棵子树
7
例如:
A
B
C
D
E
F GH I J
K
L
M
A( B(E, F(K, L)), C(G), D(H, I, J(M)) )
树根
T1
T2
第六章 树和二叉树
6.1 树的类型定义 6.2 二叉树的类型定义
6.3 二叉树的存储结构 6.4 二叉树的遍历
6.5 线索二叉树 6.6 树和森林的表示方法
6.7 树和森林的遍历 6.8 赫夫曼树与赫夫曼编码
2
数据对象 D：
D是具有相同特性的数据元素的集合。
数据关系 R：
若D为空集，则称为空树； 否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n>1时，其余结点可分为m (m>0)个互
23
性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）
证明：
基于上一条性质，深度为 k 的二叉 树上的结点数至多为
20+21+ +2k-1 = 2k-1
24
性质 3 ：
对任何一棵二叉树，若它含有n0 个叶子 结点、n2 个度为 2 的结点，则必存在关
系式：n0 = n2+1。
21
二叉树 的重要特性
22
性质 1 ： 在二叉树的第 i 层上至多有 2i-1 个结点。(i≥1)
用归纳法证明：
归纳基： i = 1 层时，只有一个根结点， 2i-1 = 20 = 1；
归纳假设：假设对所有的 j，1≤ j i，命题成立; 归纳证明：二叉树上每个结点至多有两棵子树，
则第 i 层的结点数至多 = 2i-2 2 = 2i-1 。
19
InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);
20
ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR);
F 被称为子树森林
12
有向树：
(１) 有确定的根； (２) 树根和子树根之间为有向关系。
有序树：
子树之间存在确定的次序关系。
无序树：
子树之间不存在确定的次序关系。
13
对比树型结构和线性结构 的结构特点
14
线性结构
第一个数据元素 (无前驱)
最后一个数据元素 (无后继)
其它数据元素 (一个前驱、
一个后继)
完全二叉树：树中
a
所含的 n 个结点和 满二叉树中编号为 1 至 n 的结点一一
b de
c fg
对应。
hi j
26
性质 4 ：
具有 n 个结点的完全二叉树的深度为
log2n +1
证明： 设 完全二叉树的深度为 k
证明：
设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1 + 2n2
而 b = n-1 = n0 + n1 + n2 - 1
由此， n0 = n2 + 1
25
两类特殊的二叉树：
1
满二叉树：指的是
2
3
深度为k且含有2k-1 4 5 6 7
个结点的二叉树。 8 9 10 11 12 13 14 15
N L
N R
N
L
R
17
二叉树的主要基本操作： 查找类 插入类 删除类
18
Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());
树型结构
根结点 (无前驱)
多个叶子结点 (无后继)
树中其它结点 (一个前驱、
多个后继)
15
二叉树或为空树；或是由一个根结
点加上两棵分别称为左子树和右子树
的、互不交的二叉树组成。
根结点
A
右子树
B
E
C
F
D
左子树
G HK
16
二叉树的五种基本形态：
空树
只含根结点
右子树 为空树
N
左子树 为空树
左右子 树均不 为空树