树
本文最后更新于：2024年5月30日 早上
树的定义
关键词:n 个节点的有限集合
充要条件:
- 任意一颗树，都且只有一个被称之为根的节点
- n>1 时，其余节点可分为 m 个互不相交的有限集 T1,T2…Tm,其中每个集合又是一颗树，并且称之为根的子树
逻辑结构：
- 分层，递归
- 根无前驱，其它节点，有且只有一个前驱
- 节点可以有零个或多个后续
基本术语
- 节点的度:该节点的孩子个数
- 树的度：节点最大的度
树的性质
- 所有的节点数=所有节点度数个数之和+1
- 高度为 h 的 m 叉树，至多有 (m^h-1)(m-1)个节点，其实这个就是等比求和的公式而已
- 具有 n 个节点的 m 叉树的最小高度为 [logm(n(m-1)+1)]:以 m 为底，这是向上取整！！
- 重要：b+1=n1+n2+n0+1 :(b 为分支树=n1+2n2 意思是，度为 1，发出 n1 个分支，度为 2:发出 2n2 个分支)