二叉树

概念

  • 父节点、子节点
  • 兄弟节点：具有相同父节点的子节点
  • 根节点：没有父节点的节点
  • 叶子节点（叶节点）：没有子节点的节点
  • 节点的高度（Height）：节点到叶子节点的最长路径（边数）
  • 节点的深度（Depth）：根节点到这个节点经过的边数
  • 节点的层数（Level）：节点的深度 + 1
  • 树的高度：根节点的高度
  • 二叉树：每个节点最多有两个子节点，左子节点和右子节点
  • 满二叉树：除叶子节点外，其他节点都有左、右两个叶子节点，深度为 k，节点数为 $2^k-1$

完全二叉树

  • 所有叶子节点出现在 k 层和 k-1 层，1～(k-1) 层，必须是最大节点数（根节点都有左右子节点）
  • 第 k 层可以不满，但是子节点都必须出现在树的左侧，例如下图中如果 E 节点有一个右子节点，就不是一个完全二叉树了
  • 将树中的节点从上到下、从左到右编号为 i，构造一个满二叉树同样编号，如果节点的编号都一样则是一个完全二叉树。例如：E 节点如果有一个右子节点，直接编号的话顺序为 10，按照满二叉树编号为 11，编号不同了则不是完全二叉树。

堆也是一种利用了完全二叉树的结构。

完全二叉树
完全二叉树

二叉树存储

链式存储

通过数据、左右指针来存储，然后通过根节点将整个树串起来

1
2
3
4
5
class BinaryNode<T> {
    private T element;
    private BinaryNode<T> left;
    private BinaryNode<T> right;
}

顺序存储（数组）

通过数组下标定位节点，节点 X 的下标为 i，则他的左子节点下标为 2*i，右子节点下标为 2*i + 1，可以发现如果是非完全二叉树就会存在浪费存储空间的情况了。例如：E 右子节点下标为 11，数组下标为 10 的位置就浪费了。

二叉树的遍历

  • 前序遍历：先访问该节点，再访问该节点的左子树，最后访问该节点的右子树
  • 中序遍历：先访问该节点的左子树，再访问该节点，最后访问该节点的右子树
  • 后序遍历：先访问该节点的左子树，再访问该节点的右子树，最后访问该节点

前中后是相对于当前节点被访问的书序来说的。遍历的时间复杂度是 $O(n)$。

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
80
81
82
83
84
85
86
/*************************
* 二叉树的遍历，递归实现  **
*************************/
//先序遍历
public void preOrderTraversalRec(BinaryNode root) {
    if (root != null) {
        System.out.print(root.getElement() + "-");
        preOrderTraversalRec(root.getLeft());
        preOrderTraversalRec(root.getRight());
    }
}

//中序遍历
public void inOrderTraversalRec(BinaryNode root) {
    if (root != null) {
        inOrderTraversalRec(root.getLeft());
        System.out.print(root.getElement() + "-");
        inOrderTraversalRec(root.getRight());
    }
}

//后序遍历
public void postOrderTraversalRec(BinaryNode root) {
    if (root != null) {
        postOrderTraversalRec(root.getLeft());
        postOrderTraversalRec(root.getRight());
        System.out.print(root.getElement() + "-");
    }
}

/*************************
* 二叉树的遍历，非递归实现  **
*************************/
//先序遍历
public void preOrderTraversal(BinaryNode root) {
    Stack<BinaryNode> stack = new Stack<>();
    BinaryNode current = root;
    while (current != null || !stack.empty()){
        if (current != null){
            System.out.print(current.getElement() + "-");
            stack.push(current);
            current = current.getLeft();
        } else {    
            //当访问到最左边的孩子后开始访问右孩子
            current = stack.pop();
            current = current.getRight();
        }
    }
}

//中序遍历
public void inOrderTraversal(BinaryNode root) {
    Stack<BinaryNode> stack = new Stack<>();
    BinaryNode current = root;
    while (current != null || !stack.empty()) {
        if (current != null) {        
            //从根节点开始，如果当前节点有左孩子，则入栈。包括最左孩子节点
            stack.push(current);
            current = current.getLeft();
        } else {
            current = stack.pop();
            System.out.print(current.getElement() + "-");
            current = current.getRight();
        }
    }
}

//后序遍历
public void postOrderTraversal(BinaryNode root) {
    Stack<BinaryNode> stack = new Stack<>();
    Stack<BinaryNode> outStack = new Stack<>();
    BinaryNode current = root;
    while (current != null || !stack.empty()){
        if (current != null){
            outStack.push(current);
            stack.push(current);
            current = current.getRight();
        } else {
            current = stack.pop();
            current = current.getLeft();
        }
    }
    while (!outStack.empty()){
        System.out.print(outStack.pop().getElement() + "-");
    }
}