温故而知新。本文将回顾二叉搜索树的基本知识，并用C++将它的三种depth-first search: 前序遍历、中序遍历和后序遍历，以及一种breath first search: 层序遍历算法分别实现出来。

1. BST的结构

首先，我们先定义树的结构：

1
2
3
4
5
6
7
8
9
10
11
12

struct node
{
    int data;
    node *leftchild;
    node *rightchild;
    node(int val)
    {
        data = val;
        leftchild = NULL;
        rightchild = NULL;
    }
};

接下来，我们实现基本的插入节点操作。根据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

void insert(node* root,int val)
{
    node* tmp = new node(val);//创建新节点
    if(root == NULL)
    {
        root = tmp;
        return;
    }
    node* pre = root;
    while(true)
    {
    
        if(pre->data >= val)
        {
            if(pre->leftchild == NULL)
            {
                pre->leftchild = tmp;
                return;
            }
            pre = pre->leftchild;
        }
        else
        {
            if(pre->rightchild == NULL)
            {
                pre->rightchild = tmp;
                return;
            }
            pre = pre->rightchild;
        }
    }
};

2. 前序、中序、后序遍历的递归实现

首先明确一下三种遍历的基本概念：

  • 前序遍历：根节点->左子树->右子树
  • 中序遍历：左子树->根节点->右子树
  • 后序遍历：左子树->右子树->根节点

其中中序遍历比较特别，因为按照中序遍历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

void preordertree(node* root)
{
    if(root == NULL) return;
    if(root!=NULL)
    {
    std::cout << root->data << " ";
    preordertree(root->leftchild);
    preordertree(root->rightchild);
    }
};
void postordertree(node* root)
{
    if(root == NULL) return;
    if(root)
    {
        postordertree(root->leftchild);
        postordertree(root->rightchild);
        std::cout << root->data << " ";
    }
}
void inordertree(node* root)
{
    if(root)
    {
        inordertree(root->leftchild);
        std::cout << root->data << " ";
        inordertree(root->rightchild);
    }
}

3. 前序、中序、后序遍历的非递归实现

3.1 前序遍历的非递归实现

前序遍历的非递归实现主要需要借助stack。对于stack中任意一个节点，先访问其本身并将其pop出来，再将其右节点和左节点分别压入栈中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void iterpreordertree(node* root)
{
    if(root == NULL) return;
    
    std::stack<node *> nstack;
    nstack.push(root);
    
    while(!nstack.empty())
    {
        node* tmp = nstack.top();
        std::cout << tmp->data << " ";
        nstack.pop();
        
        if(tmp->rightchild)
            nstack.push(tmp->rightchild);
        if (tmp->leftchild)
            nstack.push(tmp->leftchild);
    }
    std::cout << std::endl;
}

3.2 中序遍历的非递归实现

中序遍历的非递归实现的主要难点在于：因为首先要寻找到左节点，访问完毕后需要回到根节点，并转换方向寻找右侧子树。这里，我们用一个栈stack和一个节点cur来追踪。首先将cur指定为根节点。

  1. 不断搜寻cur的左子树，并将中间路过的节点压入栈中。
  2. 当左子树搜寻完毕之后，将cur重新赋值为nstack.top()，访问过后将其弹出。
  3. 转换cur到其右子树上，并重复步骤1。
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

void iterinordertree(node* root)
{
    if(root == NULL) return;
    
    std::stack<node *> nstack;
    node* cur = root;
    
    while(cur || !nstack.empty())
    {
        //if cur is not NULL
        if(cur)
        {
            nstack.push(cur);
            cur = cur->leftchild;
        }
        else{
            cur = nstack.top();
            std::cout << cur->data << " ";
            nstack.pop();
            
            cur = cur->rightchild;
        }
    }
    
    std::cout << std::endl;
}

3.3 后序遍历的非递归实现

后序遍历的非递归实现是三者中最难的，需要借助两个stack来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void iterpostordertree(node* root)
{
    if(root == NULL) return;
    
    std::stack<node *> first,second;
    first.push(root);
    
    while(!first.empty())
    {
        node* tmp = first.top();
        first.pop();
        second.push(tmp);
        
        if(tmp->leftchild)
            first.push(tmp->leftchild);
        if (tmp->rightchild)
            first.push(tmp->rightchild);
    }
    while (!second.empty()) {
        std::cout << second.top()->data << " ";
        second.pop();
    }
    std::cout << std::endl;
}

4. 层序遍历

层序遍历利用的是广度优先搜索，利用队列，每次访问一层，并将下一层的节点入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void breathfirst(node* root)
{
    if(root == NULL) return;
    
    std::queue<node *> nqueue;
    nqueue.push(root);
    
    while (!nqueue.empty()) {
        int n = nqueue.size();
        for(int i = 0; i < n; i++)
        {
            node* cur = nqueue.front();
            std::cout << cur->data << " ";
            nqueue.pop();
            if (cur->leftchild)
                nqueue.push(cur->leftchild);
            if(cur->rightchild)
                nqueue.push(cur->rightchild);
        }
    }
    std::cout << std::endl;
}