menu Error0 Blog
二叉树非递归遍历
59 浏览 | 2019-10-28 | 分类:数据结构 | 标签:

需要注意

非递归遍历需要借助这个数据结构来完成

先序

步骤

  1. 把结点 访问压入栈。
  2. 把指针指向左子结点
  3. 重复第1步直到没有左子结点为止。
  4. 再从 顶部拿出结点, 把指针指向此结点的右子结点。
  5. 重复第1步骤 直到栈空或没有结点。

代码

void PreOrder(struct TreeNode* root)
{

    stack<TreeNode*> S;
    struct TreeNode* T = root;
    while (!S.empty()||T)
    {
        while (T)
        {
            cout << T->val << " ";
            S.push(T);
            T = T->left;
        }
        
        if (!S.empty())
        {
            T = S.top();
            S.pop();
            T = T->right;
        }

    }
}

中序

步骤

  1. 把结点压栈 指针指向左子结点
  2. 重复第1步直到没有左子结点为止。
  3. 出栈 把出栈的结点访问
  4. 把右结点压入栈里面
  5. 重复第1步骤 直到栈空或没有结点。

代码

void Middle(struct TreeNode* root)
{
    stack<TreeNode*> S;
    struct TreeNode* T = root;
    while (!S.empty()||T)
    {
        while (T)
        {
            S.push(T);
            T = T->left;
        }
        
        if (!S.empty())
        {
            T = S.top();
            S.pop();
            cout << T->val << " ";
            T = T->right;
        }

    }
}

后序

步骤

  1. 把结点压入 指针指向结点左子结点。
  2. 重复第1步直到没有左子结点为止。
  3. top指针指向栈顶 判断当前结点右边是否 或者 已经遍历过(prev 这个指针 记录被访问过的结点)
  4. 如果 第3步 有任何一条条件符合就 访问 然后prev 记录 出栈。
  5. 如果条件都不符合继续把top的子右节点压入栈中。

代码

void PostOrder(struct TreeNode* root)
{
    if (root == NULL)
        return;
    stack<TreeNode*> S;
    struct TreeNode* cur = root;
    struct TreeNode* top=NULL;
    struct TreeNode* prev = NULL;
    while (!S.empty()|| cur)
    {
        while (cur)
        {
            S.push(cur);
            cur = cur->left;
        }
        top = S.top();
        if (top->right == NULL || top->right == prev)
        {
            cout << top->val << " ";
            prev = top;
            S.pop();
        }
        else {
            cur = top->right;
        }
    }
}
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!

Emoji

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 46

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 48

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 87

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 89