首页 > 代码库 > 二叉树非递归访问

二叉树非递归访问

2024-07-05 15:06:04   215人阅读

二叉树非递归访问，借助一个栈，来模拟递归调用过程。

?
1
2
3
4
5
6
struct TreeNode {
     char val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

1. 先序遍历

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void PreOrder(TreeNode *root)
{
    if (root == NULL)
        return;
 
    stack<TreeNode*> s;
    s.push(root);
 
    while (!s.empty())
    {
        TreeNode *node = s.top();
        s.pop();
 
        if (node->right != NULL)
            s.push(node->right);
        if (node ->left != NULL)
            s.push(node->left);
 
        cout << node->val << " ";
    }
     
}

2. 中序遍历

中序遍历，有一个很有意思的规律，从左子树返回，就要访问根节点。

所以，记录一下当前访问状态是下降（访问左子树）状态，还是从左子树返回状态。

从左子树返回后，要访问根节点，同时，如果根节点有右子树，要访问右子树。

右子树访问结束后，整棵访问完的子树又相当于一个左子树。

?
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
void InOrder(TreeNode *root)
{
    if (root == NULL)
        return;
 
    stack<TreeNode*> s;
    s.push(root);
 
    TreeNode *prev = NULL;
    while (!s.empty())
    {
        TreeNode *curr = s.top();
                //当前是下降过程
        if (!prev || prev->left == curr || prev->right == curr)
        {
            if (curr->left != NULL)
                s.push(curr->left);
        }
        else  // 从左子树返回
        {
            s.pop();
            cout << curr->val << " ";
 
            if (curr->right != NULL)
                s.push(curr->right);
        }
 
        prev = curr;
    }
}

3. 后序遍历

后序遍历，要在第二次返回的时候访问根节点。

?
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 PostOrder(TreeNode *root)
{
    if (root == NULL)
        return;
 
    stack<TreeNode*> s;
    s.push(root);
 
    TreeNode *prev = NULL;
    TreeNode *curr = NULL;
 
    while (!s.empty())
    {
        curr = s.top();
        if (!prev || prev->left == curr || prev->right == curr)
        {
            if (curr->left != NULL)
                s.push(curr->left);
            else if (curr->right != NULL)
                s.push(curr->right);
        }
        else if (curr->left == prev) //左子树返回
        {
            if (curr->right != NULL)
                s.push(curr->right);
        }
        else                         //从右子树返回 或 无右子树
        {
            s.pop();
            cout << curr->val << " ";
        }
        prev = curr;
    }
}

比较简单的一种后序访问就是采用双栈策略。

?
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
void PostOrder(TreeNode *root)
{
    if (root == NULL)
        return;
 
    stack<TreeNode*> s;
    stack<TreeNode*> result;
 
    TreeNode *curr = NULL;
 
    s.push(root);
    while (!s.empty())
    {
        curr = s.top();
        s.pop();
 
        result.push(curr);
        if (curr->left != NULL)
            s.push(curr->left);
        if (curr->right != NULL)
            s.push(curr->right);
    }
 
    while (!result.empty())
    {
        curr = result.top();
        result.pop();
 
        cout << curr->val << " ";
    }
}

按照后序遍历的顺序，将最后要访问的结点压入result栈的栈底。

　　


联系
我们