目录

一、相关概念

1、节点的度

2、树的高度

3、叶子节点

4、内部节点

5、父节点

6、兄弟节点

7、层次

二、考法1：二叉树的特性

三、二叉树的遍历

1、前序遍历

2、中序遍历

3、后序遍历

4、层次遍历

四、考法1：二叉树的遍历

---

一、相关概念

1、节点的度

• 就是指当前节点，子序的个数。节点6的度是2。

2、树的高度

• 就是指树的层次个数。图中树的高度是4。

3、叶子节点

• 也称终端节点。就是指度为0的节点。4、5、7、8都是叶子节点。

4、内部节点

• 就是指度不为0的节点，也称为非终端节点、分支节点。

• 除根节点之外的分支节点可以称为内部节点。

5、父节点

• 是相对的。

• 如图，2是4、5的父节点。

6、兄弟节点

• 在同一级的节点称为兄弟节点。

• 如图4、5。

7、层次

• 就是指树的层次，一共有多少层。图中树有4层。

二、考法1：二叉树的特性

• 注意：一般这种考题如果考的是特殊的树，会在题目中有说明，一定仔细读题。

• 根节点编号为1，对于编号为i的节点，其左孩子节点为2i，右孩子节点为2i+1，图解如下图。

三、二叉树的遍历

1、前序遍历

（1）遍历顺序

• 根左右。

（2）概念

• 也叫先序遍历。是指先遍历根，再按先序遍历的方式遍历左子序，然后再按先序遍历的方式遍历右自序。

（3）先序遍历的方式

• 先遍历根节点，再把左子序分成多颗树，每棵树按照根左右的方式遍历；右子序同理

（4）举例：

• 如上图前序遍历结果为：12457836

2、中序遍历

（1）遍历顺序

• 左根右。

（2）概念

• 是指先按中序遍历的方式遍历左子序，再遍历根，再按中序遍历的方式遍历右子序。

（3）中序遍历的方式

• 把左子序从上到下分为多个树，然后按照先左后根最后右的方式遍历每一颗树，以次类推。左子序遍历完成加上根节点，然后右子序按左子序方式遍历即可。

（4）举例：

• 如上图中序遍历结果为：42785136

3、后序遍历

（1）遍历顺序

• 左右根

（2）概念

• 是指先按后序遍历的方式遍历左子序，再按后续遍历的方式遍历右子序，最后遍历根。

（3）后序遍历的方式

• 把左子序从上到下分为多个树，然后按照先左后右的方式遍历每一颗树，以次类推。遍历右子序同理，最后加上根节点即可。

（4）举例

• 如图后序遍历结果为48752631

4、层次遍历

（1）遍历顺序

• 从上往下，从左往右。

（2）层次遍历的方式

• 先将树分层，然后按照从上往下、同一层有多个的话就再按从左往右的顺序遍历每一层。

（3）举例说明

• 如下图层次遍历的结果为：

四、考法1：二叉树的遍历