基本概念

二叉树是一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

度：结点拥有的子树数称为结点的度。

终端结点：度为0的结点称为叶子或者终端结点。

深度：树中结点的最大层次称为树的深度或高度。

完全二叉树：可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左到右。深度为$k$的，有$n$个结点的二叉树，当且仅当其每一个结点都与深度为$k$的满二叉树编号从$1$至$n$一一对应时，称之为完全二叉树。

性质

  • 在二叉树的第$i$层上至多有$2^{i-1}$个结点($i \geq 1$)。
  • 深度为$k$的二叉树至多有$2^k-1$个结点($k \geq 1$)。如果是$2^k-1$则为满二叉树。
  • 对于任何一颗二叉树$T$，如果其终端结点树为$n_0$，度为2的结点树为$n_2$，则$n_0 = n_2 +1$
  • 具有$n$个结点的完全二叉树，其深度k满足$ \log_{2}n< k \leq \log_2n+1$，$k$的值其实就是$\log_2n+1$向下取整
  • 如果对一颗有$n$个结点的完全二叉树的结点按层序编号，则对任一结点$i$($1\leq i \leq n$)，有
    • 如果$i = 1$，则结点是二叉树的根，无双亲；如果$i > 1$，则其双亲结点$i/2$取整。
    • 如果$2i > n$，则结点$i$无左孩子（结点$i$为叶子结点）；否则其左孩子是结点$2i$。
    • 如果$2i+1 > n$，则结点无右孩子；否则其右孩子结点$2i+1$

存储结构

  1. 顺序存储结构
  2. 链式存储结构

遍历二叉树

学习网站： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

假如以L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历方式。若限定先左后右，则只有三种情况，分别称之为先（根）序遍历、中（根）序遍历、后（根）序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。

  • 先序遍历二叉树的操作定义为：

    若二叉树为空，则空操作；否则

  1. 访问根结点；
  2. 先序遍历左子树；
  3. 先序遍历右子树。

  • 中序遍历二叉树的操作定义为：

    若二叉树为空，则空操作；否则

  1. 中序遍历左子树；
  2. 访问根结点；
  3. 中序遍历右子树。

  • 后序遍历二叉树的操作定义为：

    若二叉树为空，则空操作；否则

  1. 后序遍历左子树；
  2. 后序遍历右子树；
  3. 访问根结点。

定义二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    public static TreeNode create(Integer[] nums, int index) {
        TreeNode top = null;
        if (index < nums.length) {
            Integer value = nums[index];
            if (value == null) {
                return null;
            }
            top = new TreeNode(value);
            top.left = create(nums, index * 2 + 1);
            top.right = create(nums, index * 2 + 2);
            return top;
        }
        return top;
    }
}

深度优先搜索（DFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
  * 前序遍历 中--左--右(DLR)
  * @param root
  */
public static void preorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.println(root.getData() + "->");
        preorderTraversal(root.getLeftNode());
        preorderTraversal(root.getRightNode());

    }
}

/**
  * 中序遍历 左--中--右(LDR)
  * @param root
  */
public static void inorderTraversal(TreeNode root) {
    if (root != null) {
        inorderTraversal(root.getLeftNode());
        System.out.println(root.getData() + "->");
        inorderTraversal(root.getRightNode());

    }
}

/**
  * 后序遍历 左--右--中(LRD)
  * @param root
  */
public static void postorderTraversal(TreeNode root) {
    if (root != null) {
        postorderTraversal(root.getLeftNode());
        postorderTraversal(root.getRightNode());
        System.out.println(root.getData() + "->");
    }
}

宽度优先搜索（BFS）

相关：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-ci-bian-li-by-leetcode/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();

    public void helper(TreeNode node, int level) {
        // start the current level
        if (levels.size() == level)
            levels.add(new ArrayList<Integer>());

        // fulfil the current level
        levels.get(level).add(node.val);

        // process child nodes for the next level
        if (node.left != null)
            helper(node.left, level + 1);
        if (node.right != null)
            helper(node.right, level + 1);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return levels;
        helper(root, 0);
        return levels;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<List<Integer>>();
        if (root == null) return levels;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int level = 0;
        while ( !queue.isEmpty() ) {
            // start the current level
            levels.add(new ArrayList<Integer>());

            // number of elements in the current level
            int level_length = queue.size();
            for(int i = 0; i < level_length; ++i) {
                TreeNode node = queue.remove();

                // fulfill the current level
                levels.get(level).add(node.val);

                // add child nodes of the current level
                // in the queue for the next level
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            // go to next level
            level++;
        }
        return levels;
    }
}

遍历图解

旋转

什么是旋转

  • 左旋：是以节点的”右分支”为轴，进行逆时针旋转。我们将左旋操作定义为 left_rotate.
  • 右旋：是以节点的“左分支”为轴，进行顺时针旋转。我们将右旋操作定义为 right_rotate.

为什么要旋转

在解释这个道理之前，我们先看看执行旋转后，二叉树中节点的深度有什么变化。在上图中，二叉树执行左旋后，a 分支所有节点的深度比以前多 1，b 分支保持不变，c 分支所有节点比以前少 1.

这就意味着，通过合适的左旋和右旋操作，我们可以调整二叉树的深度。另一方面，通过合适的左旋和右旋，我们可以把二叉树变换成任意的形状！

如上图，如何把二叉树通过若干次左旋和右旋操作变换成链，答案：

1
2
3
4
5
6
left_rotate(4);
right_rotate(10);
right_rotate(8);
right_rotate(5);
right_rotate(4);
right_rotate(2);

旋转算法

  • 定义二叉树结构
1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode parent;
}
  • 旋转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package example;

public class TreeUtil {

    public static TreeNode leftRotate(TreeNode node) {
        TreeNode root = node.parent;
        TreeNode x = node;
        TreeNode y = node.right;
        TreeNode b = node.right.left;

        if (root.left == node) {
            root.left = y;
        } else {
            root.right = y;
        }
        y.parent = root;

        x.right = b;
        b.parent = x;

        y.left = x;
        x.parent = y;

        return y;
    }

    public static TreeNode rightRotate(TreeNode node) {
        TreeNode root = node.parent;
        TreeNode y = node;
        TreeNode x = node.left;
        TreeNode b = node.left.right;

        if (root.left == node) {
            root.left = x;
        } else {
            root.right = x;
        }
        x.parent = root;

        y.left = b;
        b.parent = y;

        x.right = y;
        y.parent = x;

        return x;
    }

    public static void main(String[] args) {

        TreeNode xx = new TreeNode("xx");

        TreeNode x = new TreeNode("x");
        TreeNode y = new TreeNode("y");
        TreeNode a = new TreeNode("a");
        TreeNode b = new TreeNode("b");
        TreeNode c = new TreeNode("c");

        xx.left = x;
        x.parent = xx;

        x.left = a;
        a.parent = x;

        x.right = y;
        y.parent = x;

        y.left = b;
        b.parent = y;

        y.right = c;
        c.parent = y;

        x = TreeUtil.leftRotate(x);
        x = TreeUtil.rightRotate(x);

        System.out.println("end");
    }
}