第6章-树.ppt

树的基本概念
二叉树
二叉树的遍历
线索二叉树
树和森林
二叉树应用举例
小结
第6章树
1
(Tree )?
树的基本概念
n(n≥0)个节点构成的一个层次结构
当n=0时,称为空树,记为Φ;当n>0时,称为非空树。
非空树T满足下列条件:
(1)T有且只有一个根节点(root);
(2)T的其余节点可分为互不相交的m(m≥0)个有限集
T1、T2 、... 、Tm , 每个集合Ti(1≤i≤m)是根的子树。
2
树的基本概念
树常用层次结构表示:
还有嵌套表示法、广义表表示法。
A
C
B
E
F
说明:
树可以用广义表表示,但广义表不一定能表示为树。
因为树中各子树不能相交,但广义表允许子表共享。
3

树的基本概念
(1) 父节点(双亲)与子节点(孩子)
如A是B、C、D的父节点, B、C、D是A的孩子
除根节点外,每个节点有且只有1个父节点
A
D
B
E
C
F
(2) 兄弟:具有同一父节点
如B、C、D是兄弟
(3) 根节点:1个,无父节点
叶节点:无子节点
分支节点:其余
4
树的基本概念
(4) 节点的入度(ID):指向节点的分支数目
节点的出度(OD):子节点数
树的度(TD):max(所有节点的出度)
A
D
B
E
C
F
如OD(A)=3,OD(B)=1。叶节点的出度为0。
根的入度为0,其它各节点的入度=1。
度=K的树称为K叉树。
(5) 节点的层次:根为第1层。若某节点在第i层,则其孩子在第i+1层。
树的深度(或高度):总层数
5
树的基本概念
(6) 有序树:树中任一节点的各子树从左到右有序
无序树:否则
(7) 森林(或树林):m(m≥0) 棵互不相交的有序树的有序集合。
6

树的基本概念
性质1:树中节点总数n(n≥0)等于树中各节点的出度之和加1 。即:
(OD(i)为第i节点的出度)
证:除根外,每节点的入度=1
所以树中总的分支数B=n-1或n=B+1。
又:一个节点发出的分支数=该节点的出度,
所以各节点的分支数之和B= 树中各节点的出度之和。
代入n=B+1, 性质得证。
7
树的基本概念
性质2:度=K的树(K叉树)第i(i≥1)层至多有Ki-1个节点。
性质1证明:采用数学归纳法。
i=1时,第1层最多1个节点,故K1-1=1成立。
设K叉树第i-1层至多有K(i-1)-1=Ki-2个节点,
因为是K叉树,所以第i-1层上每个节点最多有K个孩子节点,即
第i层至多有Ki-2•K=Ki-1个节点,证毕。
性质3:深度=h(h≥1)的K(K>1)叉树至多有(Kh-1)/(K-1)个节点。
性质2证明:设深度=h的k叉树最大节点数为S,显然
如何证明?
8
树的基本概念
性质4:包含n(n≥0)个节点的K(K>1)叉树的最小深度为:
证:设有n个节点的K叉树的深度为h,若该树第1~h-1层都是满的,即每层有最大节点数Ki-1(1≤i≤h-1),且其余节点都落在第h层,
则该树的深度最小。
根据性质3有
或:(Kh-1 -1) <n(K-1)≤(K h-1) 即:Kh-1<n(k-1)+1≤Kh
取对数:(h-1)<logk(n(K-1)+1)≤h
因为h是正整数,所以:h=
同样数量的节点,什么情况下树的深度最小?
9
(Binary Tree )?
二叉树
度=2的树。即每个节点最多2个孩子
二叉树
或者是空树;
或者由1个根节点以及左子树和右子树组成,左子树和右子树是二叉树。
(1) 5种基本形态
L
L
R
R

L、R分别为二叉树根的左、右子树
空树
10