树

树的定义

关键词: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 个分支)