数据结构与算法-树和二叉树共45页文档

⑵ 如果2i>n,则结点i为叶子结点，无左孩子；否则，其 左孩子结点编号是2i。
⑶ 如果2i+1>n,则结点i无右孩子；否则，其右孩子结点
编号是2i+1。
1
2
3
4
5
67
13
8 9 10 11 12
2 二叉树--满二叉树与完全二叉树
m= i/2
…i
i
i+1
i+1 … 2i
2i+1
2i
(a)
2i+1 2i+2
14
巩固练习
若有一棵有16个结点的完全二叉树，按层编号（从1 开始编号），则对于编号为7的结点，它的双亲结点
及右孩子结点的编号分别为___D____。
A 2,14 B. 2,15 C. 3, 14 D. 3,15
将一棵有100个结点的完全二叉树，从根这一层开始 ，每一层从左到右依次对结点进行编号 ，根结点编
2
1 树的基本概念
1 树的定义
树(Tree)是n(n≧0)个结点的有限集合T，若n=0时称 为空树，否则：
⑴ 有且只有一个特殊的称为树的根(Root)结点； ⑵ 若n>1时，其余的结点被分为m(m>0)个互不相交的子 集T1, T2, T3…Tm，其中每个子集本身又是一棵树，称其为 根的子树(Subtree)。
16
3 遍历二叉树
若以L、D、R分别表示遍历左子树、遍历根结点和遍历 右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、 RDL、RLD。若规定先左后右，则只有前三种情况三种情况， 分别是：
DLR——先(根)序遍历。 LDR——中(根)序遍历。 LRD——后(根)序遍历。

5.1.1基本概念
• 二叉树可以定义为结点的有限集合，这个集合或 者为空集，或者由一个根及两棵不相交的分别称 作这个根的左子树和右子树的二叉树组成。
，这时的二叉树称为空二
叉树。二叉树也可以是只有一个结点的集合，这 个结点只能是根；它的左子树和右子树均是空二 叉树。
• 先根次序：
若二叉树不空，则先访问根；然后按先根次序周游左子树； 最后按先根次序周游右子树。
下图所示二叉树，先根次序周游得到的结点序列为：A， B，D，C，E，G，F，H，I
• 后根次序
若二叉树不空，则先按后根次序周游左子树；然后按 后根次序周游右子树；最后访问根。 前图所示的二叉树，按后根次序周游得到的结点序列 为：
分支进入，假设B为分支总数，则有
B=n–1
(2)
又由于二叉树中的分支都是由度为1和2的结点发出
的，所以有
综合(1)、(2)、(3)式B可=得n1 + 2n2
(3)
n0 = n2 + 1
• 性质4 具有n个结点的完全二叉树的深度k为。
• 证明：根据性质2和完全二叉树的定义可知
2k - 1 ＜ n ≤2k+1 – 1
• 如在图的扩充二叉树中： E=2+2+4+4+3+3+3
= 21 I=0+1+1+2+2+3=9
5.1.2 主要性质
• 性质1 在非空二叉树的i层上至多有2i个结点 (i≥0)。 证明：用归纳法来证。
• 性质2 高度为k的二叉树中最多有2k+1 - 1个结 点(k≥0)。 证明：假设第i层上的最大结点个数是mi，由性质 1可知，深度为k的二叉树中最大结点个数M为:

5.1.2 树的存储结构
1. 双亲表示法
树的双亲表示法主要描述的是结 点的双亲关系。
下标 AA B E 0 1 2 3 4 5 6 7 8 9
info A B C D E F G H I J
B
F F
C C
DD GG
HH I
E
I
JJ
paren t -1 0 0 0 1 1 3 6 6 6
图 5-3
typedef struct { TNode item[MAX_TREE_NODE_SIZE]; int n,root; //n为树中当前结点的数目，root为根结点在一 维数组中的位置 }ChildTree; 这种存储结构的特点是寻找某个结点的孩子比 较容易，但寻找双亲比较麻烦，所以，在必要的时候， 可以将双亲表示法和孩子表示法结合起来，即将一维数 组元素增加一个表示双亲结点的域parent，用来指示结 点的双亲在一维数组中的位置。
数据结构课件 数据结构课件
第5章 树和二叉树
本章中主要介绍下列内容：
树的逻辑定义和存储结构 二叉树的逻辑定义、存储结构 二叉树的基本操作算法 树和二叉树的转换 哈夫曼树及其应用
退出
5.1 树 5.2 二叉树 5.3 哈夫曼树及其应用
5.1 树
5.1.1
1. 定义
树的定义和基本运算
树是一种常用的非线性结构。我们可以这样定 义：树是n（n≥0）个结点的有限集合。若n=0，则称 为空树；否则，有且仅有一个特定的结点被称为根， 当n>1时，其余结点被分成m（m>0）个互不相交的子 集T1，T2，...，Tm，每个子集又是一棵树。由此可以 看出，树的定义是递归。
2. 树的基本运算 常用操作： （1） 构造一个树 CreateTree (T) （2）清空以T为根的树 ClearTree(T) （3）判断树是否为空 TreeEmpty(T) （4）获取给定结点的第i个孩子 Child(T,node,i) （5）获取给定结点typedef st(T,node) （6）遍历树Traverse(T) 对树遍历的主要目的是将非线性结构通过遍历 过程线性化，即获得一个线性序列。树的遍历顺序有两 种，一种是先序遍历，即先访问根结点，然后再依次用 同样的方法访问每棵子树；另一种是后序遍历，即先依

(一个前驱、 多个后继)
第一个数据元素
其它数据元素
基 本 术 语
汇报人姓名
汇报日期
结点:
结点的度:
树的度:
叶子结点:
分支结点:
数据元素+若干指向子树的分支
分支的个数
树中所有结点的度的最大值
度为零的结点
度大于零的结点
D
H
I
J
M
(从根到结点的)路径：
孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点
第6章
树和二叉树
6.1 树的类型定义
CONTENTS
6.2 二叉树的类型定义
6.3 二叉树的存储结构
6.4 二叉树的遍历
01
6.5 线索二叉树
6.6 树和森林的表示方法
02
03
04
05
二叉排序树及其平衡化
06
6.1 树的类型定义
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。
结点的层次:
树的深度：
由从根到该结点所经分支和结点构成
A
B
C
D
E
F
G
H
I
J
M
K
L
假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1
树中叶子结点所在的最大层次
森林：
任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林
PART.01
数据对象 D：
D是具有相同特性的数据元素的集合。
若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。

教学进度
• 6.2 二叉树
– 定义
计算机科学与工程系
• 定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)， 或由一个根结点和两棵分别称为左子树和右子树的互不相 交的二叉树构成
• 特点
– 每个结点至多有二棵子树(即不存在度大于2的结点)
– 二叉树的子树有左、右之分，且其次序不能任意颠倒
– 后序遍历：先后序遍历左、右子树，然后访问 根结点
– 按层次遍历：从上到下、从左到右访问各结点
D
L
R
LDR、LRD、DLR RDL、RLD、DRL
教学进度
先序遍历:
A
B
C
D
计算机科学与工程系
D
L
R
A D LR
D LR
B
C
D LR
先序遍历序列：A B D C D
教学进度
中序遍历:
A
B
C
D
计算机科学与工程系
TreeEmpty(T) // 判定树是否为空树
TreeDepth(T) // 求树的深度
TraverseTree( T, Visit() ) // 遍历
教学进度
插入类：
计算机科学与工程系
InitTree(&T) // 初始化置空树
CreateTree(&T, definition) // 按定义构造树
(Subtree)。
空树：不包括任何结点的树。
教5学进度
只有根结点的树 A
计算机科学与工程系
子树
有子树的树
A
根
B
C
D
E
F GH I J
KL
M
教学进度