文档介绍：引言
在前面几章里讨论的数据结构都属于线性结构,线性结构的特点是逻辑结构简单,易于进行查找、插入和删除等操作,主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非如此简单,如人类社会的族谱、各种社会组织机构以及城市交通、通讯等,这些事物中的联系都是非线性的,采用非线性结构进行描绘会更明确和便利。
所谓非线性结构,是指在该结构中至少存在一个数据元素,有两个或两个以上的直接前驱(或直接后继)元素。树结构和图结构是非常重要的非线性结构。
第六章树和二叉树
本章内容
树的定义和基本术语
二叉树
二叉树的定义及基本运算
二叉树的性质
二叉树的存储结构
遍历二叉树和线索二叉树
遍历二叉树
线索二叉树
树和森林
树的存储结构
森林与二叉树的转换及遍历
赫夫曼树及应用
赫夫曼树(最优二叉树)
赫夫曼编码
树
树是n个结点的有限集合(可以是空集),在任一棵非空树中: (1)有且仅有一个称为根的结点。 (2)其余结点可分为互不相交的子集,而且这些子集本身又是一棵树,称为根的子树。
J
I
A
C
B
D
H
G
F
E
K
L
M
从逻辑结构看: 1)树中只有树根没有父结点; 2)除根外,其余结点都有且仅一个父结点;
3)树中的结点,可以有零个或多个孩子结点;
4) 没有孩子的结点称为叶子结点,或终端结点;
5)除根外的其他结点,都存在唯一一条从根到该结点的路径;
J
I
A
C
B
D
H
G
F
E
K
L
M
树的基本术语
树的结点:包含一个数据元素及若干指向子树的分支;
孩子结点:结点的子树的根称为该结点的孩子;
父结点:B 是A的孩子,则A是B的父亲;
兄弟结点:同一双亲的孩子结点;
堂兄弟结点:其父结点在同一层上的结点;
祖先结点: 从根到该结点所经分支上的所有结点;
子孙结点:以某结点为根的子树中任一结点都称为该结点的子孙;
结点的度: 结点的孩子数目
J
I
A
C
B
D
H
G
F
E
K
L
M
树的基本运算
找树的根结点
求树的高度
找指定结点的父结点
找指定结点的孩子结点
在树中插入、删除一个结点
遍历树
......
J
I
A
C
B
D
H
G
F
E
K
L
M
树的表示
J
I
A
C
B
D
H
G
F
E
K
L
M
G
C
K
L
E
F
B
M
H
J
I
D
A
(a)
(A(B(E(k,L),F),C(G),D(H(M),I(),J())))
(b)
二叉树
二叉树的定义:二叉树要么为空,要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。
注意:二叉树的子树有严格的左右之分,而树没有。
A
C
B
F
E
D
G
二叉树的子树要区分左子树和右子树,即使只有一棵子树也要进行区分。这是二叉树与树的最主要的差别。下面列出了二叉树的5种基本形态, (c)和(d)是不同的两棵二叉树。
(a)
空二叉树
A
A
B
A
B
A
C
B
(b)
只有根的
二叉树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
二叉树的5种基本形式
二叉树的性质
性质1
在二叉树的第i层上至多有2i-1个结点
性质2
深度为k的二叉树至多有2k-1个结点
性质3
任何一个二叉树中度为2的结点数目(n2)比度为0的结点数目(n0)少1,即n2= n0-1。
G
K
J
C
F
A
B
E
I
H
D