二叉树（Binary Tree）

特征

1. 每个节点最多有两个“叉”，即两个子节点，分别是左子节点和右子节点。但是，并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

1

分类

1. 满二叉树

编号 2

1. 叶子节点全都在最底层，
2. 除了叶子节点之外，每个节点都有左右两个子节点。

2. 完全二叉树

编号 3

1. 除了最后一层，其他层的节点个数都要达到最大。
2. 最后一层的叶子节点都靠左排列，

2

完全二叉树的优点

可以使用顺序存储法，消耗的空间少。

如果节点 X 存储在数组中下标为 i 的位置，
左子节点：存储下标位置为 2 * i，
右子节点：存储下标位置为 2 * i + 1。

通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。仅仅“浪费”了一个下标为 0 的存储位置。

3

如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。

遍历

• 先根遍历
• 中根遍历
• 后根遍历

// 逻辑，不同的遍历把1、2、3顺序调换一下即可
遍历函数(Node node){
  1. 打印当前节点的值；
  2. 遍历node的左子树；
  3. 遍历node的右子树；
}
// 伪代码
void preOrder(Node node){
  if (node == null) return;
  print (node.value);
  preOrder(node.left);
  preOrder(node.right);
}