Traverse Tree

发表于 | 分类于

Traverse Tree(遍历树的三种方法)

题目描述：

给定一棵树的头结点；给出先序遍历、中序遍历和后序遍历树的结果。

例子：

先序遍历是先遍历根节点，然后左节点，最后右节点；中序遍历是先遍历左节点，然后根节点最后右节点；后序遍历是最后遍历根节点。先序中序后序是以根节点为标准。

解题思路：

树的遍历主要是利用递归的方式进行查找。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class printTree{
public:
    void preOrder(treeNode* root){
        if (root == NULL)
            return;
        std :: cout << root->val << std :: endl;//先根遍历
        preOrder(root->left);
        preOrder(root->right);
    }
    void inOrder(treeNode* root){
        if (root == NULL)
            return;
        inOrder(root->left);
        std :: cout << root->val << std :: endl; //中序遍历
        inOrder(root->right);
    }
    void postOrder(treeNode* root){
        if (root == NULL)
            return;
        postOrder(root->left);
        postOrder(root->right);
        std :: cout << root->val << std :: endl;//后序遍历
    }
};

解题思路2：

当然我们也可以使用非递归的方式对树进行遍历；主要的思路是在于将节点入栈后，根据不同的将左节点和右节点的压栈方式能够得到不同的遍历结果。

对于先根遍历而言，我们将某节点出栈后，先将该节点的右节点入栈，然后左节点入栈；对于中序遍历而言，我们是不断将最左侧的节点入栈，然后在弹出某节点后，将该节点的右侧节点入栈即可实现中序遍历；对于后序遍历而言我们利用了2个栈的方式，首先将根节点放入栈1，每次弹出的节点都放入栈2，并且将弹出节点的左侧和右侧节点压入栈1；不断进行直到栈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
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
class printTreeUnrecur{
public:
    void preOrder(treeNode* root){
        if (root == NULL)
            return;
        std::stack<treeNode*> stk;
        stk.push(root);
        treeNode* tmp;
        while(!stk.empty()){
            if (stk.top() != NULL){
                tmp = stk.top();
                cout << tmp->val << endl;
                stk.pop(); //先打印出栈节点
                stk.push(tmp->right);
                stk.push(tmp->left);//先压入右侧节点在压入左侧节点
            }
            else{
                stk.pop();
            }
        }
    }
    void inOrder(treeNode* root){
        if (root == NULL)
            return;
        stack<treeNode*> stk;
        treeNode* tmp;
        while(root != NULL || !stk.empty()){
            if (root != NULL){
                stk.push(root);
                root = root->left;//先不断将左侧节点压栈
            }else{
                tmp = stk.top();
                cout << tmp->val << endl;//打印出栈的节点
                stk.pop();
                root = tmp->right; //遍历出栈节点的右侧节点
            }
        }
    }
    void postOrder(treeNode* root){
        if (root == NULL)
            return;
        std::stack<treeNode*> stk1;
        std::stack<treeNode*> stk2;
        stk1.push(root);
        treeNode* tmp;
        while(!stk1.empty()){
            tmp = stk1.top();
            stk1.pop();
            stk2.push(tmp); //出栈压入栈2中
            if (tmp->left != NULL)
                stk1.push(tmp->left);
            if (tmp->right != NULL)
                stk1.push(tmp->right);
                //将出栈节点的左侧和右侧节点压入栈1
        }
        while(!stk2.empty()){
            tmp = stk2.top();
            cout << tmp->val << endl;
            stk2.pop();//打印栈2中的数据即为遍历结果
        }
    }
};