二叉树非递归遍历
麦兜 / 2019-10-28 / 数据结构 / 阅读量 128

需要注意

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

先序

步骤

  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;
        }
    }
}
1 + 7 =
快来做第一个评论的人吧~