[toc]
树
| 名称 | 作用 |
|---|---|
| 根 | 树的顶端结点 |
| 孩子 | 当远离根(Root)的时候，直接连接到另外一个结点的结点被称之为孩子(Child); |
| 双亲 | 相应地，另外一个结点称为孩子(child)的双亲(parent); |
| 兄弟 | 具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)。 |
| 祖先 | 结点的祖先(Ancestor)是从根（Root）到该结点所经分支(Branch)上的所有结点。 |
| 子孙 | 反之，以某结点为根的子树中的任一结点都称为该结点的子孙(Ancestor)。 |
| 叶子（终端结点） | 没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点。 |
| 分支(非终端结点) | 至少有一个孩子的结点称为分支(Branch)或非终端结点。 |
| 度 | 结点所拥有的子树个数称为结点的度(Degree)。 |
| 边 | 一个结点和另一个结点之间的连接被称之为边(Edge)。 |
| 层次 | 结点的层次(Level)从根(Root)开始定义起，根为第0层，根的孩子为第1层。以此类推，若某结点在第i层，那么其子树的根就在第i+1层。 |
| 结点的高度 | 结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。 |
| 结点的深度 | 结点的深度是从树的根结点到该结点的边的个数。 （注：树的深度指的是树中结点的最大层次。） |
二叉树
定义 ： 每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒
性质 ：
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
完美二叉树(又名满二叉树)(Perfect Binary Tree)
一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。 (注： 国内的数据结构教材大多翻译为"满二叉树")
例如：
完全二叉树(Complete Binary Tree)
完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
例如：
完满二叉树(Full Binary Tree)
所有非叶子结点的度都是2
例如：
@Chicago_01
