2022.7.28 高级数据结构——二叉树遍历(非递归思想)

• 1. 先序遍历
• 中序遍历
• 后序遍历
• 层次遍历

规则：根左右

//非递归-先序遍历：右左压栈，
void BTree::PreOrder()
{
    stackss;
    Node* top = nullptr;
    ss.push(m_root);
    while (!ss.empty())
    {
        top = ss.top();
        ss.pop();
        cout << top->m_value << " ";
        if (top->m_right != nullptr)
        {
            ss.push(top->m_right);
        }
        if (top->m_left != nullptr)
        {
            ss.push(top->m_left);
        }
    }
    cout << endl;
}

//中序思想：左根右，先将当前节点的左子树全部入栈，判断栈是否为空，如果不空，获取栈顶，并出栈，然后用p记住当前根的右子树
//查看当前右子树是否有左孩子，如果有继续
void BTree::InOrder()
{
    if (m_root != nullptr)
    {
        stackss;
        Node* p = m_root;
        Node* top = nullptr;
        while (p || !ss.empty())
        {
            while (p != nullptr)
            {
                ss.push(p);
                p = p->m_left;
            }
            if (!ss.empty())
            {
                top = ss.top();
                ss.pop();
                cout << top->m_value << " ";
                p = top->m_right;//当前结点遍历完
            }
        }
            
    }
    cout << endl;
}

//后序思想：左右根，入栈顺序为根左右
// 注意：需要一个指针记住已经遍历过的结点
// 原因：入栈：如果当前结点有左右孩子，根据右左顺序入栈
//       出栈：如果当前结点乜有左右孩子/当前结点右孩子，但是孩子已经被访问过，则需要出。
void BTree::PostOrder()
{
    if (m_root != nullptr)
    {
        stackss;
        Node* top = nullptr, * pre = nullptr;
        ss.push(m_root);
        while (!ss.empty())
        {
            top = ss.top();//获得栈顶
            //判断栈顶元素有无孩子
            //出栈
            if (top->m_left == nullptr && top->m_right == nullptr || pre!=nullptr && top->m_left==pre|| top->m_right == pre)
            {
                cout << top->m_value << " ";
                ss.pop();
                pre = top;//pre指针记住出栈的结点，为了下一次查看
            }
            else
            {
                if (top->m_right != nullptr)
                {
                    ss.push(top->m_right);
                }
                if (top->m_left != nullptr)
                {
                    ss.push(top->m_left);
                }
            }
        }
    }
    cout << endl;
}

//层遍历——要借助队列 
void BTree::LevOrder()
{
    queue qq;
    Node* front = nullptr;
    if (m_root != nullptr)
    {
        qq.push(m_root);
        while (!qq.empty())
        {
            front = qq.front();//获取队头元素
            qq.pop();  //出队
            cout << front->m_value <<" ";
            if (front->m_left != nullptr)
            {
                qq.push(front->m_left);
            }
            if (front->m_right != nullptr)
            {
                qq.push(front->m_right);
            }
        }
    }
    cout << endl;
}

主函数调用：

int main()
{
    BTree bt;//定义了一棵树，树根为nullptr——m_root(nullptr)
    const char* str = "abd**eh***cf*i**g**";
    bt.m_root = bt.Create(str);

    //非递归思想//
    cout << endl;
    cout << " LevOrder ";
    bt.LevOrder();

    cout << endl;
    cout << " PreOrder ";
    bt.PreOrder();

    cout << endl;
    cout << " InOrder ";
    bt.InOrder();

    cout << endl;
    cout << " PostOrder ";
    bt.PostOrder();

    return 0;
}