概述

  • 一种相对常见的数据结构，结构像一颗倒立的树。
  • 树本质上是一个无环图，对无环图的各种操作方法，在树这边基本也可以使用
  • 将一个数据结构视为树，要突出的是它的层级关系(方向性)

简单图示

树

特性

相对详细内容请查看 树基础知识

  • 前序/中序/后序遍历一般使用 递归 实现，迭代 实现需要借助 栈 来完成
  • 层序遍历借助 队列 完成
  • 二叉搜索树 通过 中序遍历 获取的数列是 有序 的

复杂度分析(部分操作)

普通树

操作 时间复杂度 空间复杂度
(前序/中序/后序)遍历 O(n) O(log(n))(取决树的高度)(递归为函数深度，迭代为栈空间)
层序遍历 O(n) O(w)(w为树层的最大元素数目)
查找元素 O(n) O(1)
插入节点 O(1) O(1)
删除节点 O(m)(m = 子结点数量) O(1)

二叉搜索树

操作 时间复杂度 空间复杂度
查找元素 O(log(n)) O(1)
插入数据 O(log(n)) O(1)
删除数据 O(log(n)) O(1)

发散/随想/自身理解(?)

  • C++ 中 std::map<>, std::set<> 底层是红黑树实现
  • 一般使用链表实现树，以便实现灵活增删，使用数组实现树也有，一般用于堆(优先队列)，后续再介绍
  • 在大学学习中主要学习二叉树的相关特性，在工作中遇到的树形结构也相对比较常见，例如文件夹、GUI 的控件层次结构等等
  • 本人一般将普通树和图绑在一块看
  • 相对复杂的树(平衡搜索树(AVL)，B/B+树，红黑树)，本人就不太会了，后面有提及再说吧

实现(C++)

这里是简要实现

普通树 ADT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Node {
    int value;
    vector<Node*> child;
};

class Tree {
public:
    Tree() : root(nullptr) {}
    virtual ~Tree() {}
    virtual void Init() = 0;
    virtual void Traversal() {}

private:
    Node* root;
};

二叉树 ADT

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
struct Node {
    int value;
    Node* left;
    Node* right;

    Node(int val) : value(val), left(nullptr), right(nullptr) {}
};


class BinaryTree {
public:
    BinaryTree() : root(nullptr) {}
    virtual ~BinaryTree() { Destroy(root); }
    virtual void Init() {}

    // traversal
    virtual void Traversal() {
        // PreOrder(root);
        // InOrder(root);
        // PostOrder(root);
        // PreOrderIteration(root);
        // InOrderIteration(root);
        // PostOrderIteration(root);
        // LevelOrder(root);
    }

protected:
    virtual void PreOrder(Node* node) {
        if (node == nullptr) return;

        // mid

        PreOrder(node->left);
        PreOrder(node->right);
    }

    virtual void InOrder(Node* node) {
        if (node == nullptr) return;

        InOrder(node->left);

        // mid

        InOrder(node->right);
    }

    virtual void PostOrder(Node* node) {
        if (node == nullptr) return;

        PostOrder(node->left);
        PostOrder(node->right);

        // mid
    }

    virtual void PreOrderIteration(Node* node) {
        if (node == nullptr) return;

        stack<Node*> st;
        st.push(node);
        while (!st.empty()) {
            Node* curNode = st.top();
            st.pop();

            // mid
            if (curNode->right) st.push(curNode->right);
            if (curNode->left) st.push(curNode->left);
        }
    }

    virtual void InOrderIteration(Node* node) {
        if (node == nullptr) return;

        stack<Node*> st;
        st.push(node);
        while (!st.empty()) {
            Node* curNode = st.top();
            st.pop();
            if (curNode == nullptr) {
                curNode = st.top();
                st.pop();
                // mid
            } else {
                if (curNode->right) st.push(curNode->right);

                st.push(curNode);
                st.push(nullptr); // 执行标记

                if (curNode->left) st.push(curNode->left);
            }
        }
    }

    virtual void PostOrderIteration(Node* node) {
        if (node == nullptr) return;

        stack<Node*> st;
        st.push(node);
        while (!st.empty()) {
            Node* curNode = st.top();
            st.pop();
            if (curNode == nullptr) {
                curNode = st.top();
                st.pop();
                // mid
            } else {
                if (curNode->right) st.push(curNode->right);
                if (curNode->left) st.push(curNode->left);

                st.push(curNode);
                st.push(nullptr); // 执行标记
            }
        }
    }

    // 层序遍历
    virtual void LevelOrder(Node* node) {
        if (node == nullptr) return;

        queue<Node*> que;
        que.push(node);
        while (!que.empty()) {
            Node* curNode = que.front();
            que.pop();

            // operate

            if (curNode->left) que.push(curNode->left);
            if (curNode->right) que.push(curNode->right);
        }
    };

    void Destroy(Node* node) {
        if (node) {
            Destroy(node->left);
            Destroy(node->right);
            delete node;
        }
    }

protected:
    Node* root;
};

二叉搜索树(BST)

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
class BST : public BinaryTree {
public:
    BST() : BinaryTree() {}
    virtual ~BST() {}

    void Init(const vector<int> valueVec) {
        for (int i = 0; i < valueVec.size(); ++i) {
            Insert(valueVec[i]);
        }
    }

    bool Insert(int val) {
        root = InsertValue(root, val);
        return true;
    }

    bool Search(int value) {
        if (root == nullptr) return false;
        Node* curNode = root;
        while (curNode != nullptr) {
            if (curNode->value == value) return true;
            else if (curNode->value < value) curNode = curNode->right;
            else curNode = curNode->left;
        }
        return false;
    }

private:
    Node* InsertValue(Node* node, int val) {
        if (node == nullptr) {
            node = new Node(val);
            return node;
        } else {
            if (node->value == val) return nullptr;
            else if (node->value > val) {
                node->left = InsertValue(node->left, val);
            } else {
                node->right = InsertValue(node->right, val);
            }
            return node;
        }
    }
};