二叉树示意图

     A  
   /   \
  B     C
 / \   / \
D   E F   G

二叉树简介

树是一种简单的非线性结构，所以元素之间具有明显的层次特性。

• 每个节点只有一个前件，称为父节点；（B和C的父节点为A)
• 没有前件的节点只有一个，称为根节点，简称根； (A节点为根节点，A没有前件)
• 每个节点可以有多个后节点，称为该节点的子节点； （B和C都为A的子节点）
• 没有后件(子节点)的节点，称为叶子节点； (D、E、F、G均为叶子节点)
• 一个节点拥有的后件个数，称为该节点的度；（A、B、C的度是2，D、E、F、G的度为0）
• 所有节点中最大的度，称为树的度； （A、B、C的度是2， D、E、F、G的度都为0，所以树的度为2）
• 树的最大层次，称为树的深度； (上面的树最大层次是3，所以树的深度是三层)

二叉树的特性

• 非空二叉树只有一个根节点；（A没有父节点，故A为根节点）
• 每个节点最多有两棵子树，且分别称为该节点的左子树和右子树。
  二叉树的度可以为0(叶子节点) ，如果叶子节点为1(只有一颗子树)或2(有两棵子树)；

二叉树的性质

在二叉树的第k层上，最多有2^(k - 1)并且（k >= 1）个节点 (第k层共有多少个节点)；

例子：
如上图所示，一共三层，故已知k=3；2^(3-1)= 4；
从上面的示意图可以看出第三层一共4个节点，分别为D、E、F、G；

深度为m的二叉树最多有2^m-1个结点；

例子：
如上图所示，一共三层，故树的深度为3。m=3; 2^3-1 = 7;
从上面的示意图可以看出一共为7个节点。

在任意一个二叉树中，度为0的结点(即叶子节点)总比度为2的结点多一个。

解释：
如上图所示，A、B、C的度均为2，D、E、F、G度为0。

具有n个节点的二叉树，其深度至少为[log2n] + 1个,其中log2n表示取log2n的整数；

解释：
log2n什么意思？笔者写博客的时候也查了下百度，真是愧对当年的数学老师，废话不多说。
log2(n)= x 等价于 2^x=n;
例子：
如上图所示，二叉树一共有7个节点，故n=7。 logn2(7)+1 = 2+1 = 3；注：logn2(7)取整所以为2，不需要四舍五入。再看看上面图，是不是至少为3层？

二叉树及其基本性质

满二叉树：

除最后一层外，每一层上的所有节点都有两个子节点，如下图：

     A  
   /   \
  B     C
 / \   / \
D   E F   G

完全二叉树:

除最后一层外，每一层上的节点数都达到最大值；在最后一层上至缺少右边的若干节点，如下图：

     A  
   /   \
  B     C
 / \   / 
D   E F   

• 设置完全二叉树共有n个节点。如果从根节点开始，按层序（每一层从左至右）用自然数1，2..n给节点编号(k=1, 2, ..n)，有以下结论：

     1  
   /   \
  2     3
 / \   / 
4   5 6   

1. 若k=1，则该节点为根节点，它没有父节点；若k>1，该节点的父节点的编号为INT(k/2)，取整。
   例子：
   如上图，假设k=3 INT(3/2)=1. 假设k=5 INT(5/2)=2。
2. 若2k≤n，则编号为k 的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点)
   解释：
   n为二叉树的最大节点个数，上图最大节点个数为6。
   例子：
   如上图，先取2这个节点，k=2，2x2<=6成立，说明2有子节点。 再取4，k=4，2x4<=6不成立，说明4没有子节点。
3. 若2k+1<=n，则编号为k的节点的右节点编号为2k+1，否则该节点无右子节点；
   例子：
   如上图, 先取2这个节点，k=2, 2x2+1<=6成立，得到5，5为2的右节点。 k=3, 2*3+1<=6不成立，所以3节点无右子节点。

二叉树的遍历

二叉树的遍历是指不重复的访问二叉树中的所有节点。
以下为遍历走势图：

      1  
     ↙  ↘
    2    3
   ↙ ↘  ↙ 
  4   5 6

前序遍历(DLR)：

若二叉树为空，则结束返回；否则：

• 访问根节点；
• 前序遍历左子树；
• 前序遍历右子树;

遍历顺序为1→2→4→5→3→6

中序遍历(LDR)：

若二叉树为空，则结束返回；否则：

• 中序遍历左子树；
• 访问根节点；
• 中序遍历右子树；

遍历顺序为2→4→5→1→6→3

后序遍历(LRD)：

若二叉树为空，则结束返回；否则：

• 后序遍历左子树；
• 后序遍历右子树；
• 访问根节点；

遍历顺序为4→5→2→1→3→6