算法思路
Source
Edit
History

undefined

二叉树

想要存储一颗二叉树，一种是基于指针或者引用的二叉链式存储法；一种是基于数组的顺序存储法

  • 顺序存储法：把根节点存储在下标 i=1 的位置，那左子节点存储在下表 2*i=2 的位置，右子节点存储在 2*i+1=3的位置，依次类推。

如果二叉树是完全二叉树，用数组存储无疑是最节省内存的一种方式

一、遍历

递归的写法每个节点最多被访问两次，所以时间复杂度是 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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// 非递归 前序遍历
void PreOrder(Node* root) {
    if (root == nullptr) return;
    std::stack<Node*> st;
    st.push(root);
    while (!st.empty()) {
        Node* tmp = st.top();
        std::cout << tmp->value << " ";
        st.pop();
        if (tmp->right != nullptr) {
            st.push(tmp->right);
        }
        if (tmp->left != nullptr) {
            st.push(tmp->left);
        }
    }
}

// 非递归 中序遍历
void InOrder(Node* root) {
    if (root == nullptr) return;
    std::stack<Node*> st;
    while (!st.empty() || root != nullptr) {
        while (root != nullptr) {
            st.push(root);
            root = root->left;
        }
        root = st.top();
        std::cout << root->value << " ";
        st.pop();
        root = root->right;
    }
}

// 非递归 后序遍历
// 第一种方法：就是前序遍历的逆序，可以维护两个栈
void PostOrder(Node* root) {
    if (root == nullptr) return;
    std::stack<Node*> st1;
    std::stack<int> res;
    st1.push(root);
    while (!st1.empty()) {
        Node* tmp = st1.top();
        st1.pop();
        res.push(tmp->value);
        if (tmp->left != nullptr) {
            st1.push(tmp->left);
        }
        if (tmp->right != nullptr) {
            st1.push(tmp->right);
        }
    }
    while (!res.empty()) {
        std::cout << res.top() << " ";
        res.pop();
    }
}

// 非递归 后续遍历
// 第二种方法：一个栈
// 与中序遍历不同的是：
// 1. 中序遍历（左根右）中，从栈中弹出的节点，其左子树是访问完了，接下来就可以访问这个节点，然后在访问右子树
// 2. 后序遍历（左右根）中，从栈中弹出的节点，可以确认其左子树访问完了，但是右子树无法确认是否访问过
// 因此，在后序遍历中，引入一个 prev 来记录历史访问记录
// 1. 当访问完一颗子树时，我们就用 prev 指向该节点
// 2. 这样，在回溯到父节点的时候，我们可以依据 prev 是指向左子节点还是右子节点，来判断父节点的访问情况
void PostOrder2(Node* root) {
    if (root == nullptr) return;
    std::stack<Node*> st;
    Node* prev = nullptr;
    // 主要思想：
    // 由于在某棵子树访问完成之后，接着就要回溯到其父节点去
    // 因此可以用 prev 来记录访问历史，在回溯到父节点时，可以由此来判断，上一个访问的节点是否为右子树
    while (root != nullptr || !st.empty()) {
        while (root != nullptr) {
            st.push(root);
            root = root->left;
        }
        // 从栈中拿出元素，此时可以确认此节点的左子树一定访问完了，但是右子树不一定访问了，所以不能弹出
        root = st.top();
        // 如果此节点的右子树为空或者右子树已经访问过，则可以访问此节点了
        if (root->right == nullptr || root->right == prev) {
            // 访问并弹出
            std::cout << root->value << " ";
            st.pop();
            // 并把这个节点用 prev 保存起来，为了确认此节点所代表的子树时左子树还是右子树
            //更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成
            prev = root;
            // 将 root 置空，因为 root 节点已经被访问，并且确认此节点左右子树也被访问，就让此节点消失
            root = nullptr;
        } else {
            // 如果右子树没有被访问，那么访问右子树
            root = root->right;
        }
    }
}

// 层序遍历
void LevelOrder(Node* root) {
    if (root == nullptr) return;
    std::queue<Node*> qu;
    qu.push(root);
    while (!qu.empty()) {
        int cur_level_size = qu.size();
        for (int i = 0; i < cur_level_size; i++) {
            Node* tmp = qu.front();
            std::cout << tmp->value << " ";
            qu.pop();
            if (tmp->left != nullptr) {
                qu.push(tmp->left);
            }
            if (tmp->right != nullptr) {
                qu.push(tmp->right);
            }
        }
        std::cout << std::endl;
    }
}

二、操作

二叉树的删除操作分三种情况
  1. 如果要删除的节点没有子节点，则直接将父节点中指向的节点指针置为 NULL 即可
  2. 如果要删除的节点只有一个子节点，则只需要更新父节点中，指向要删除节点的指针，让其指向要删除节点的子节点即可
  3. 如果要删除的节点有两个子节点，则需要找到这个节点的右子树的最小节点，把它替换到要删除的节点上即可
支持重复数据的二叉查找树
  1. 将二叉查找树中每一个节点存储成一个链表或者支持动态扩容的数组等数据结构，把值相同的数据都存储在同一节点上
  2. 在插入时，遇到相同的节点，则将其插入这个相同节点的右子树上。那么在查找的时候遇到值相同的继续在右子树上查找；删除的时候也要删除所有的

三、二叉查找树对比哈希表

哈希表插入、删除、查找的时间复杂度都为 O(1)。而二叉查找树在比较平衡时，插入、删除、查找的时间复杂度才是 O(logn)

  1. 哈希表中的数据是无序存储的，如果要输出有序的数据，需要先排序；二叉树只需要中序遍历就可以 O(n) 输出有序的数据序列
  2. 哈希表扩容耗时很多，而且当遇到哈希冲突时，性能不稳定，
  3. 尽管哈希表查找速度是常量级别，但哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快；加上哈希函数的耗时，也不一定比平衡二叉查找树的效率高
  4. 哈希表的构造比二叉查找树复杂，需要考虑哈希函数设计、冲突解决办法、扩缩容。平衡二叉树只需要考虑平衡性，而且这个问题的解决方案比较成熟

红黑树

平衡二叉树的定义：二叉树中任意一个节点的左右子树的高度相差不能大于 1

AVL 树是一个高度平衡的二叉树，查找效率非常高，但是为了维持这种高度的平衡，每次插入、删除都要做调整，就比较复杂、耗时。对于频率插入、删除的数据集合，使用 AVL 树的代价有点高

红黑树是一种不严格的平衡二叉树，需要满足如下几个要求

  1. 根节点是黑色的
  2. 每个叶节点都是黑色的空节点，也就是说，叶子节点不存储数据
  3. 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
  4. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点