5-二叉树

参考链接

• 基本数据结构：二叉树（binary tree）

二叉树首先是一棵树，每个节点都不能有多于两个的儿子，也就是树的度不能超过2。二叉树的两个儿子分别称为“左儿子”和“右儿子”，次序不能颠倒。如图1是一个简单的二叉树。

img

二叉树的种类

一种是满二叉树，除了最后一层的叶子节点外，每一层的节点都必须有两个儿子节点。如图2是一个满二叉树。

img

另一种是完全二叉树，一棵二叉树去掉最后一层后剩下的节点组成的树为满二叉树，最后一层的节点从左到右连续，没有空出的节点，这样的树称为完全二叉树。如图3是一棵完全二叉树。

img

二叉树的实现

见下一节，二叉查找树

二叉树的遍历

二叉树的遍历有三种，分别为先序遍历，中序遍历和后序遍历。这三种遍历方式是根据根节点的读取顺序来分的：

• 先序遍历：就是最先读取根节点，然后再读取左子树（按照同样的方法读取子树上的节点），最后读取右子树；
• 中序遍历：就是第二个读取根节点，最先要读取的是左子树，然后根节点，最后右子树；
• 后序遍历：就是最后一个读取根节点，最先读取的是左子树，第二个读取右子树，最后读取根节点。