二叉树的性质

祖先和子孙
根结点到该结点的唯一路径上的任意结点，如上a）图：1是4的祖先，4是1的子孙

双亲、孩子、兄弟、堂兄弟
如上a）图：2是4的双亲，5是2的孩子，4和5是兄弟，4和6是堂兄弟，1（根结点）是树中唯一没有双亲的结点，

结点的度、树的度
有几个孩子结点的度就是多少，如上b）图：1的度是3，2的度是2，3的度是0
树的度等于树中结点度最大的那个，如a）图中树的度为2，b）图中树的度为3

分支结点 vs 叶子结点
分支结点度大于0的结点，又称非终端结点
叶子结点度等于0的结点，又称终端结点

结点的深度、高度、层次
深度是从根结点开始自顶向下
高度是从叶结点开始自底向上
树的高度\深度是树中结点的最大层数

路径和路径长度
两个结点之间的路径由两个结点之间所经过的结点序列构成
路径上所经过的边的个数就是路径长度

树的性质

1. 树中的结点数 = 所有结点的度数之和 + 1
2. 度为m的树中第i层至多有m^i-1 个结点
3. 高度为h的m叉树至多有(m^h - 1) / (m - 1)个结点
4. 具有n个结点的m叉树的最小高度为log₂[n(m-1)+1] （向上取整）

二叉树的性质