二叉树的非递归遍历

数据结构

二叉树定义

1
2
3
4
5
6
7
8
9
class TreeNode {
public
    int val;
    TreeNode *left, *right;
    TreeNode(int val) {
        this -> val = val;
        this -> left = this -> right = NULL;
    }
}

前序遍历

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：

对于任一结点P：

  1. 访问结点P，并将结点P入栈;
  2. 判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1; 若不为空，则将P的左孩子置为当前的结点P;
  3. 直到P为NULL并且栈为空，则遍历结束。
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
void preorder1(TreeNode *root) {
    stack<TreeNode *> s;
    if (root == NULL)
        return;
    s.push(root);
    while (!s.empty()) {
        root = s.top();
        s.pop();
        /* 访问根结点 */
        cout << root -> val << endl;
        /* 右子结点先入栈 */
        if (root -> right)
            s.push(root -> right);
        /* 左子结点后进栈 */
        if (root  -> left)
            s.push(root -> left);
    }
}
void preorder2(TreeNode *root) {
    stack<TreeNode *> s;
    while (root != NULL || !s.empty()) {
        while (root != NULL) {
            cout << root -> val << endl;
            s.push(root);
            root = root -> left;
        }
        if (!s.empty()) {
            root = s.top();
            s.pop();
            root = root -> right;
        }
    }
}

中序遍历

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：

对于任一结点P，

  1. 若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
  2. 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子;
  3. 直到P为NULL并且栈为空则遍历结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void inorder(TreeNode *root) {
    stack<TreeNode *> s;
    while (!s.empty() || root != NULL) {
      	/* 首先根结点入栈，然后左子结点入栈 */
        while (root != NULL) {       
            s.push(root);
            root = root -> left;
        }
        if (root != NULL) {
            root = s.top();
            s.pop();
            cout << root -> val << endl;
            root  = root -> right;
        }
}

后序遍历

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。

第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

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
struct StackNode {
    TreeNode *root;
    bool isFirst; // 增加状态变量
}
/* visit(left) -> visit(right) -> root */
void postorder(TreeNode *root) {
    stack<StackNode> s;
    StackNode snode;
    while (!s.empty() || root != NULL) {
        /* 有左孩子，则进栈，将root赋值为root -> left */
        while (root != NULL) {
            snode.isFirst = true;
            snode.root = root;
            s.push(snode);
            root = root -> left;
        }
        if (!s.empty()) {
            snode = s.top();
            s.pop();
            /* 栈顶第一次出现某结点，先pop()再push()，将root赋值为root -> right */
            if (snode.isFirst) {
                snode.isFirst = false;
                s.push(snode);
                root = snode.root -> right;
                /* 结点会出现在栈顶两次，访问结点 */
            } else {
                cout << snode.root -> val << endl;
                root = NULL;
            }
        }
    }
}

第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void postorder(TreeNode *root) {
    stack<TreeNode *> s;
    TreeNode *cur, *pre = NULL;
    if (root == NULL)
        return;
    s.push(root);
    while (!s.empty()) {
        cur = s.top();
      	/* cur不存在左孩子和右孩子 */
        if ((cur -> left == NULL && cur -> right == NULL) ||
            pre != NULL && (pre == cur -> left || pre == cur -> right)) {
                cout << cur -> val << endl;
                s.pop();
                pre = cur;
        } else {
            if (cur -> left)
                s.push(cur -> left);
            if (cur -> right)
                s.push(cur -> right);
        }
    }
}

三合一非递归遍历

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
struct StackNode1 {
    TreeNode *root;
    int state; // 增加状态变量
}
void inorder(TreeNode *root) {
    StackNode1 snode;
    snode.root = root;
    snode.state = 0;
    stack<StackNode1> s;
    while (snode.root != NULL && !s.empty()) {
        while (!s.empty() && (snode.root == NULL || snode.state >= 3)) {
            snode = s.top();
            s.pop();
            snode.state++;
        }
        if (snode.root == NULL || snode.state >= 3)
            break;
        /* 当前是中序遍历，前序遍历和后序遍历只需更改case的值 */
        /* 前序遍历：case 1 -> case 0 -> case 2 */
        /* 后序遍历：case 1 -> case 2 -> case 0 */
        switch (snode.state) {
            case 0:
                s.push(snode);
                snode.root = snode.root -> left;
                break;
            case 1:
                cout << snode.root -> val << endl;
                snode.state++;
                break;
            case 2:
                s.push(snode);
                snode.root = snode.root -> right;
                snode.state = 0;
                break;
            default:
                break;
        }
    }
}
文章目录
  1. 1. 二叉树定义
  2. 2. 前序遍历
  3. 3. 中序遍历
  4. 4. 后序遍历
  5. 5. 三合一非递归遍历
|