This is my study note of Binary tree.

二叉树

什么是二叉树

  • 本身是有序树
  • 树中包含的各个节点的度不能超过2个，只能为0、1、2

Alt text

二叉树的性质

  • 二叉树中，第i层最多有2^(i-1)个结点
  • 如果二叉树深度为k，那么此二叉树总共有2^k-1个结点
  • 二叉树中，终端结点数为n0，度为2的结点数为n2，n0 = n2+1

二叉树的分类

  • 满二叉树

    1
    除了叶子结点，每个结点的度都为2，所以是满二叉树。

    Alt text

  • 完全二叉树

    1
    二叉树除了最后一层为满二叉树，且最后一层的结点依次从左到右分布，则二叉树被称为完全二叉树。

    Alt text
    如右图，由于最后一层的节点没有按照从左到右分布，因此算作普通二叉树。

二叉树的遍历

  • 先序遍历
    1
    2
    3
    4
    访问顺序为：
        1.访问根节点
        2.访问左节点
        3.若当前左节点没有左子树，则访问右节点
    举个简单的例子:
    Alt text

采用先序遍历的流程：

1
2
3
4
5
6
7
1.访问二叉树根节点，找到1
2.访问节点1的左子树，找到节点2
3.访问节点2的左子树，找到节点4
4.访问节点4的左子树失败，访问其父节点2的右节点5
5.访问节点5的左子树节点失败，回退访问节点3，
依次类推访问节点6、7
最终得到序列：1245367
  • 中序遍历
    1
    2
    3
    4
    访问顺序为：
        1.访问左节点
        2.访问根节点
        3.访问右节点
    举个简单的例子:
    Alt text

采用中序遍历的流程：

1
2
3
4
5
6
7
8
1.访问根节点的左子节点2
2.访问节点2的左子节点4
3.访问节点4的左子节点失败，回退访问节点2
4.访问右子节点5
5.访问节点5的左右子节点失败，回退访问节点1
6.访问节点1的右子节点3
依次类推，遍历节点3、6、7
最终得到序列：4251637
  • 后序遍历
    1
    2
    3
    4
    访问顺序为：
        1.访问左节点
        2.访问右节点
        3.访问根节点
    举个简单的例子:
    Alt text

采用后序遍历的流程：

1
2
3
4
5
6
7
1.访问根节点的左子节点2
2.访问节点2的左子节点4
3.访问节点4的左子节点失败，回退访问节点2的右节点5
4.访问节点5的左子节点失败，回退访问节点2
5.回退访问节点1的右子节点3的左子节点6
依次类推，遍历节点3、6、7、1
最终得到序列：4526731

层次遍历（广度优先遍历）的实现过程

各方向上走出第一步，再在各方面上走出第二布，第三步，直到各个方向全部走完。

  • 首先根节点1入队
  • 根节点1出队，出队的过程，左孩子2和右孩子3入队
  • 左孩子2出队，出队的过程，左孩子4和右孩子5入队
  • 根节点3出队，出队的过程，左孩子6和右孩子7入队
  • 不断循环，直到队列内为空