文档介绍：数据结构与算法
树的定义
二叉树
树的存储结构
树和二叉树的遍历
哈夫曼树
树
数据结构
2
树和图
树和图都是非常重要的非线性数据结构。
树是以分支关系定义的层次结构
数据结构
3
第一节树的定义
定义:树(tree)是n(n>0)个结点的有限集T,其中:
有且仅有一个特定的结点,称为树的根(root)
当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree)
特点:
树中至少有一个结点——根
树中各子树是互不相交的集合
数据结构
4
树的例子
A
只有根结点的树
A
B
C
D
E
F
G
H
I
J
K
L
M
有子树的树
根
子树
子树
子树
数据结构
5
树的基本术语
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶子(Leaf)或终端结点。度不为0的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。
结点的子树的根称为该结点的孩子(child),相应地,该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(sibling)。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。
数据结构
6
树的基本术语
结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。+1 层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。
如果将树中结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树。在有序树中最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子。
森林(Forest)是m(m>0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。
数据结构
7
树的术语例
A
B
C
D
E
F
G
H
I
J
K
L
M
结点A的度:3
结点B的度:2
结点M的度:0
叶子:K,L,F,G,M,I,J
结点A的孩子:B,C,D
结点B的孩子:E,F
结点I的双亲:D
结点L的双亲:E
结点B,C,D为兄弟
结点K,L为兄弟
树的度:3
结点A的层次:1
结点M的层次:4
树的深度:4
结点F,G为堂兄弟
结点A是结点F,G的祖先
数据结构
8
树的基本操作
数据结构
9
第二节二叉树
定义:二叉树是n(n0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成
特点
每个结点至多有二棵子树(即不存在度大于2的结点)
二叉树的子树有左、右之分,且其次序不能任意颠倒
A
只有根结点
的二叉树
空二叉树
A
B
右子树为空
A
B
左子树为空
A
B
C
左、右子树
均非空
有三个节点的树有几种形态
数据结构
10
二叉树性质
性质1:在二叉树的第i层上至多有2i-1个结点(i ≥1)
性质2:深度为k的二叉树至多有2k-1个结点(k1)
证明:用归纳法证明之
i=1时,只有一个根结点, 是对的
假设对所有j(1j<i)命题成立,即第j层上至多有个结点
那么,第i-1层至多有个结点
又二叉树每个结点的度至多为2
第i层上最大结点数是第i-1层的2倍,即
故命题得证
证明:由性质1,可得深度为k 的二叉树最大结点数是