1.1 基本的一些概念
不写了,太基本了
1.2 性质
- 结点数=所有结点度数+1
- 度为m的树中,第i层至多有mi-1个结点(i≥1)
- 树中结点最大的度数叫树的度
- 度为m,第2层最多m个,第3层最多m²个....第i层mi-1
- 高度为h的m叉树至多有(mh-1)/(m-1)个结点
- 1层:1
2层最多:m
3层最多:m²
....
累加:S=mh-1+mh-2+mh-3+...+m+1=(mh-1)/(m-1)
- 1层:1
- 有n个结点的m叉树(最大结点数是m就行)最小高度:logm(n(m-1)+1)向上取整
最大高度:好像不咋求,有说是串成链了(n层),也有说最后一层m个,前面是链(n-m+1)层- 最小高度,则每层铺满了,根据第3点:n=(mh-1)/(m-1),可以推导出这里h=logm(n(m-1)+1),再向上取个整,因为如果有零头,说明最后一层有结点但是没满,故而再加一层
错题重点
- 树的路径长度是指树根到每个结点的路径长的总和,根到每个结点的路径长度的最大值是高度减1
- 结点总数n=分支数(度的和)+1,即n=1+n1+2n2+3n3+4n4+……=n0+n1+n2+……
求叶子结点就是求n0