二叉树遍历的通用写法

二叉树的前中后序遍历的通用写法。

使用一个栈模拟遍历的操作。

首先声明树的结构体和命令的结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x)
    {
        val=x;
        left=NULL;
        right=NULL;
    }
};
struct Command
{
    string s;
    TreeNode* node;
    Command(string s,TreeNode* node):s(s),node(node){}
};

Command 结构体有两个成员，分别是执行的操作和执行的节点。

在前序遍历中，知道每到达一个节点，先打印这个节点，然后遍历左节点，然后遍历右节点，所以将这三条命令推入栈中，因为是栈，所以先推入遍历右节点的命令，然后推入遍历左节点的命令，最后再推入打印当前节点的命令。

后序遍历和中序遍历就只需要更改else中推入三条命令的顺序就可以了。

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
前序遍历
vector<int> preorder(TreeNode* root)
{
    vector<int> res;
    if(root==NULL)
    {
        return res;
    }
    stack<Command> stack;
    //初始化
    stack.push(Command("go",root));
    while(!stack.empty())
    {
        Command command =stack.top();
        stack.pop();
        if(command.s=="print")
        {
            res.push_back(command.node->val);
        }
        else
        {//如果是go,就模拟系统推入三条命令。
            assert(command.s=="go");
            if(command.node->right)
            {
                stack.push(Command("go",command.node->right));
            }
            if(command.node->left)
            {
                stack.push(Command("go",command.node->left));
            }
            stack.push(Command("print",command.node));
        }
    }
    return res;
}
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
中序遍历
vector<int> inorder(TreeNode* root)
{
    vector<int> res;
    if(root==NULL)
    {
        return res;
    }
    stack<Command> stack;
    //初始化
    stack.push(Command("go",root));
    while(!stack.empty())
    {
        Command command =stack.top();
        stack.pop();
        if(command.s=="print")
        {
            res.push_back(command.node->val);
        }
        else
        {
            assert(command.s=="go");
            if(command.node->right)
            {
                stack.push(Command("go",command.node->right));
            }
            stack.push(Command("print",command.node));
            if(command.node->left)
            {
                stack.push(Command("go",command.node->left));
            }
        }
    }
    return res;
}
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
后序遍历
vector<int> postorder(TreeNode* root)
{
    vector<int> res;
    if(root==NULL)
    {
        return res;
    }
    stack<Command> stack;
    //初始化
    stack.push(Command("go",root));
    while(!stack.empty())
    {
        Command command =stack.top();
        stack.pop();
        if(command.s=="print")
        {
            res.push_back(command.node->val);
        }
        else
        {
            assert(command.s=="go");
            stack.push(Command("print",command.node));
            if(command.node->right)
            {
                stack.push(Command("go",command.node->right));
            }
            if(command.node->left)
            {
                stack.push(Command("go",command.node->left));
            }
        }
    }
    return res;
}