树的定义
- 树是n(n>=0)个结点的有限集。当n=0时,称为空树。
- 当n>1时,其余结点可分为m(m>0)个互不相交的有限集$T_1,T_2,…,T_m$,其中每个集合本身又是一棵树,称为根的子树
- 树的根结点没有前驱,其他结点有且只有一个前驱
- 树的所有结点都可以有零个或多个后继
- 因每个结点都与其唯一前驱结点相连,所有n个点组成的树有n条边;但根结点没有前驱结点,所以n个点组成的树有n-1条边
基本术语
- 祖先。根结点到某结点的唯一路径上的任意结点。在图1中,根结点A到结点K的唯一路径为(ABEK),那么K的祖先有A,B,E,K。(K是自己的祖先吗?)
- 子孙。以某结点为根的子树的任意结点称为该结点的子孙。如图1中,树E以B为根结点,那么E,K,L都为B的子孙。
- 双亲。根结点到某结点的唯一路径上的任意结点最接近某结点的结点。在图1中,根结点A到结点K的唯一路径为(ABEK),最接近结点K的结点是结点E,结点E称为结点K的双亲。根A是树中唯一没有双亲的结点。(为什么双亲只有一个结点?直接叫父结点不言简意赅?)
- 孩子。以某结点为前驱的结点称为某结点的孩子。如图1中,结点K的前驱结点为结点E,称结点K为结点E的孩子。(子结点)
- 堂兄弟。双亲结点在同一层的结点互为堂兄弟。如图1中,G与E,E,H,I,J互为堂兄弟。
- 兄弟。有相同双亲的结点称为兄弟。结点K和结点L有相同的双亲E,即K和L为兄弟。
- 结点的度。树中一个结点的孩子个数称为该结点的度,如结点B的度为2,结点D的度为3.
- 树的度。所有结点的度中,最大的那个度称为树的度。如图1中,树的度为3
- 分支结点(非终端结点)。度大于0的结点称为分支结点。每个结点的分支数就是给结点的度。
- 叶结点(终端结点)。度为0的结点称为叶结点。
- 结点的层次。结点的层次从根结点开始定义,根结点为第1层,它子结点为第2层,以此类推。
- 结点的深度。从根结点开始自顶向下逐层累加,根结点的深度为1。如图1中B的深度为2,G的深度为3。
- 结点的高度。层页结点开始自底向上逐层累加,叶结点的高度为1。如图1中B的高度为3,G的高度为1。
- 树的深度(树的高度),是树中结点的最大层数,图1中树的高度为4
- 有序树和无序树。树中结点的各子树从左到右是有次序的不能互换,称该树为有序树,否则称为无序树。
- 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度就是路径上所经过的边的个数。
- 森林。森林是m(m>=0)棵互补相交的树的集合。把树的根结点去掉就成了森林。
树的性质
- 树中结点数等于所有结点的度数之和加1
- 度为m的数中第i层最多有$m^{i-1}$个结点,$i>=1$。即当前层的最多结点数是上一层最多结点数的m倍
- 高度为h的m叉树最多有$\frac{m^h-1}{m-1}个结点$,推导,第1层只有根结点,即m^0,第2层最多是根结点的m倍,即m^1,第3层最多是第2层的m倍,即m^2,以此类推,共有h层,第h层最多有$m^{h-1}$个结点,$S=m^0+m^1+…+m^{h-1}$,可以看出S是个等比数列,$a_1=m^0=1,公比q=m$,根据等比数列求和公式$\frac{a_1(1-q^n)}{1-q},S=\frac{1-m^h}{1-m}=\frac{m^h-1}{m-1}(分子分母都乘-1)$
- 具有n个结点的m叉树的最小高度为$\lceil log_m(n(m-1)+1) \rceil$。令$n=\frac{m^h-1}{m-1},则m^h-1=n(m-1),即m^h=n(m-1)+1,得到h=log_m(n(m-1)+1)$
注意的知识
总结点数=$n_0+n_1+n_2+…+n_m$
总分支数=$0n_0+1n_1+2n_2+…+mn_m$
总结点数=总分支数+1
需注意的题
1.对于一个具有n个结点,度为4的树来说,树的高度最多是?
高度最多是n-3
2.在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数为?
答案是82。设n为树的总结点数,$n_i$为度为i的结点数,则n=n0+n1+n2+n3+n4=分支数+1。由题得n=204+103+12+101+1=123(n0的分支数为0,不计算),则n0=n-n1-n2-n3-n4=133-10-1-10-20=82,即度为0的结点数(叶结点)为82个