二叉树的基本概念

（图1-1 二叉树）

结点的度：指一个结点的拥有多少个孩子结点

如1号结点有俩个孩子，所以1号结点的度为2。而7号结点无孩子，所以7号结点的度为0。

树的度 ：所有结点中最高的度数就是结点的度。

叶子结点：无孩子结点的结点。

分支结点：除了叶子结点的结点（即有孩子的结点）

内部结点：除了叶子结点和根结点的结点

父结点：（相对概念）子结点的父亲结点

子结点：（相对概念）父结点的儿子结点

兄弟结点：一般指同一父结点下的不同儿子结点（特殊情况：（堂兄弟）也有指父亲的父亲的儿子的儿子结点）

层次：层次数等于离根结点的距离

满二叉树与完全二叉树

满二叉树：除最后一层，其他层结点都有左右儿子

完全二叉树：除了最后一层，上面的是满二叉树（并且结点的编号连续）（满二叉树一定是完全二叉树）

非完全二叉树：不是完全二叉树的树。

如

图1-4中，没有6号结点所以不是完全二叉树

二叉树的特性

1.第i层最多有2的 i-1 次方个结点（满二叉树时）

2.== 深度为 k 的二叉树，最多有 2的k次方 - 1的结点 （从第一层到第k层的结点树相加，就是2的k次方 - 1）==

3.如果叶子结点的数量为n，度为2的结点数为m。那么！ n = m + 1 （对任意二叉树适用）

4.对于有 n 个结点的完全二叉树编号为 1 层 到 （log 2 n）+ 1层。则对于任一结点的编号为 i 。它的左儿子编号为2 * i ，它的右儿子编号为2 * i + 1。[ i / 2 ] 为父结点 ( [] 向下取整）

二叉树的遍历

分为前序遍历、中序遍历和后序遍历。

反向构造二叉树

如果知道前序和中序，怎么样构造一棵二叉树

比如

前序：ABHFDECG

中序：HBEDFAGC

根据前序中序的性质，可以知道——前序找根（父结点），中序分左右儿子

（1）

前序：ABHFDECG

中序：HBEDFAGC

由前序知：

根为A

把A代入中序得

HBEDF A GC

HBEDF为A的左子树

GC为A的右子树

（2）

前序：A | {B} H FDE | CG
中序：H {B} EDF |A| GC

然后再看前序 ：A后面是B

可得

左子树中 H B EDF

H是B的左子树

EDF是B的右子树

（3）

前序：A | {B} H FDE | CG
中序：H {B} EDF |A| GC

再看前序：知道FDE中 F在前面，F为父结点

在中序中F，ED在 F 的左边

在前序中，D在E的前面 D为E的父亲在中序中，E在D前面 E是D的左儿子

在中序中，E在D前面 E是D的左儿子

得到：

同理可以构造A的右子树

树转二叉树

把一个普通的树转换为二叉树的思想就是：

• 孩子结点 ——> 左子树
• 兄弟结点 ——> 右子树
• 并且在所有孩子结点中，最左边的是左子树的根结点。
• 并且在所有兄弟结点中，最左边的是右子树的根结点。

根据这个思想有两种方法把树转成二叉树：

一、直接构造

对（1）来说，2、3、4是它的儿子结点。把他们作为（1）的左子树，且2是左子树的根结点。

对于（2）来说，3、4是它的兄弟结点，作为（2）的右子树，并且3是右子树的根结点。

同理，

对于（3）来说，5、6、7是他的儿子结点，把他们作为（3）的左子树，且5是左子树的根结点。

对于（5）来说，6、7是他的兄弟结点，把他们作为（5）的右子树，且6是右子树的根结点。

对于6来说，7是他的兄弟结点，所以7是它的右儿子。

同理，

对于（4）结点。8、9是它的儿子结点，作为左子树。

且8是左子树的根结点。

对于（8）来说，9是8的兄弟结点，所以9是8的右儿子。

这样，就完成了数转二叉树。

二、连线法（快得多）

还可以直接通过连线法来构造。

连续的要点是：

• 父结点连最左边的儿子结点
• 最左边的儿子结点连所有的兄弟结点
• 然后把其他线都砍掉。
• 剩下的稍稍移动一个角度（把连接兄弟结点的线顺时针移）就构成了二叉树。

连接兄弟的线顺时钟移动
连接儿子的线保持这个角度

这样同样构造完成。