树

什么是树

树是一种类似于链表的数据结构，不过链表的结点是以线性方向简单地指向其后继结点，而树的一个结点可以指向许多结点。树是一种典型的非线性结构。

术语

• 根节点：根节点是一个没有双亲结点的结点（如上图A）。
• 边：边是从双亲结点到孩子结点的连接（如上图所有的链接）。
• 叶子结点：没有孩子结点的结点叫做叶子结点（ 如E、J、K、H、I）。
• 兄弟结点：拥有相同双亲结点的所有孩子结点（B、C、D是A的兄弟结点，E、F是B的兄弟结点）。
• 结点的大小：指子孙的个数，包括其自身。（子树C的大小为3）
• 树的层：位于相同深度的所有结点的集合叫做树的层（B、C和D具有相同的层）。树结点位于0层。

• 结点的深度：是指从根结点到该结点的路径长度（G点的深度为2，A-C-G）。
• 结点的高度：是指从该结点到最深结点的路径长度。树的高度是指从根结点到树中最深结点的路径长度。只含有根结点的树的高度为0。在前面的例子中，B的高度为2（B-F-J）。
• 树的高度：是树中所有结点高度的最大值。

二叉树

如果一棵树中的每个结点有0、1或者2个孩子为结点，那么这棵树就称为二叉树。空树也是一棵有效的二叉树。一棵二叉树可以看作由根节点和两棵不相交的子树（分别称为左子树和右子树）组成。

1.二叉树的类型

严格二叉树：二叉树中的每个结点要么有两个孩子结点，要么没有孩子结点。

满二叉树：二叉树中的每个结点恰好有两个孩子结点且所有叶子结点都在同一层。

完全二叉树：除了最后一层外，每一层值的结点数均达到最大值。

2.二叉树的性质

假定树的高度为h，且根节点的深度为0。

• 满二叉树的结点个数n为2^(h+1)-1。因为该树共有h层，所以每一层结点的个数都是满的，即有[2 ^0 + 2^1 + 2^2 +....+2^h = 2^(h+1)-1]。
• 完全二叉树的结点个数为2^h ~ 2^(h+1)-1
• 满二叉树的叶子结点个数是2^h。
• 对于n个结点的完全二叉树，空指针的个数是n+1。