二叉树遍历（非递归版）

谁践踏了优雅 2022-06-16 05:16 207阅读 0赞

问题描述：  
以一定的方式输入数据（本文是以先序遍历的方式输入），程序根据数据进行解析，创建二叉树，然后对二叉树进行操作，主要操作包括以下几种：

1.  求二叉树的高度
2.  先序遍历二叉树
3.  中序遍历二叉树
4.  后序遍历二叉树
5.  层序遍历二叉树

先序遍历： 根节点->左子树->右子树  
中序遍历： 左子树->根节点->右子树  
先序遍历： 左子树->右子树->根节点  
层序遍历： 第一层（根节点）->第二层->第三次->….

PS：  
1. 大家可以清楚的看到，先序，中序和后序是相对于根节点而言的  
2. 非递归版代码描述起来比递归版略显复杂  
3. 递归版本可以查看我的另外一篇文章：  
[http://blog.csdn.net/yi\_ming\_he/article/details/71248881][http_blog.csdn.net_yi_ming_he_article_details_71248881]

以下面的例子进行说明：  
![这里写图片描述][SouthEast]

如图所示，根据上面的遍历顺序，我们可以得到以下遍历结果：  
先序遍历： a b d h e c f g  
中序遍历： h d b e a f c g  
后序遍历： h d e b f g c a  
层序遍历： a b c d e f g h

参考代码：

#include <stdio.h>
    #include <malloc.h>
    #include <string.h>
    #include <queue>
    #include <stack>
    
    #define MAXNODE 1024
    char str[MAXNODE];
    
    typedef struct BiTNode
    {
        char data;
        struct BiTNode* lchild;
        struct BiTNode* rchild;
    }BiTNode, *Bitree;
    
    void CreateBiTree(Bitree& T)
    {
       //这是根据先序遍历建立的一棵树
        scanf_s("%s", str, MAXNODE);
        Bitree tempT, tempQ;
        T = (Bitree)malloc(sizeof(BiTNode));
        T->data = str[0];
        T->lchild = NULL;
        T->rchild = NULL;
        std::stack<Bitree>st;
        st.push(T);
        for (int i = 1; i < (int)strlen(str); i++)
        {
            if (str[i] == '#')
            {
                tempT = st.top();
                st.pop();
                if (NULL == tempT->lchild)
                    i++;
            }
            else
            {
                tempT = st.top();
                tempQ = (Bitree)malloc(sizeof(BiTNode));
                tempQ->data = str[i];
                tempQ->lchild = NULL;
                tempQ->rchild = NULL;
                if (tempT->lchild)
                {
                    tempT->rchild = tempQ;
                    st.pop();
                }
                else
                    tempT->lchild = tempQ;
                st.push(tempQ);
            }
        }
    }
    
    void PreOrderTraverseByNonRecursion(Bitree T)
    {
        if (!T)
            return;
    
        std::stack<std::pair<Bitree, bool>> st;
        st.push(std::make_pair(T, false));
        bool bVisited = false;
        while (!st.empty())
        {
            T = st.top().first;
            bVisited = st.top().second;
            st.pop();
            if (!T)
                continue;
            if (bVisited)
                printf("%c ", T->data);
            else
            {
                st.push(std::make_pair(T->rchild, false));
                st.push(std::make_pair(T->lchild, false));
                st.push(std::make_pair(T, true));
            }
        }
    }
    
    void InOrderTraverseByNonRecursion(Bitree T)
    {
        if (!T)
            return;
    
        std::stack<std::pair<Bitree, bool>> st;
        st.push(std::make_pair(T, false));
        bool bVisited = false;
        while (!st.empty())
        {
            T = st.top().first;
            bVisited = st.top().second;
            st.pop();
            if (!T)
                continue;
            if (bVisited)
                printf("%c ", T->data);
            else
            {
                st.push(std::make_pair(T->rchild, false));
                st.push(std::make_pair(T, true));
                st.push(std::make_pair(T->lchild, false));
            }
        }
    }
    
    void PostOrderTraverseByNonRecursion(Bitree T)
    {
        if (!T)
            return;
    
        std::stack<std::pair<Bitree, bool>> st;
        st.push(std::make_pair(T, false));
        bool bVisited = false;
        while (!st.empty())
        {
            T = st.top().first;
            bVisited = st.top().second;
            st.pop();
            if (!T)
                continue;
            if (bVisited)
                printf("%c ", T->data);
            else
            {
                st.push(std::make_pair(T, true));
                st.push(std::make_pair(T->rchild, false));
                st.push(std::make_pair(T->lchild, false));
            }
        }
    }
    
    int GetBiTreeHeightByNonRecursion(Bitree T)
    {
        if (!T)
            return 0;
    
        int nVisitedNodeCount = 0;//已经访问过的节点数
        int nPushQueueNumber = 1;//记录入队列的节点的最大序号
        int nLevelMaxNumber = 1;//记录每一次的最大的序号
        int nTreeHeight = 0;//记录树的高度
        std::queue<Bitree> Q;
        Q.push(T);
        while (!Q.empty())
        {
            T = Q.front();
            Q.pop();
            nVisitedNodeCount++;
            if (T->lchild)
            {
                Q.push(T->lchild);
                nPushQueueNumber++;
            }
    
            if (T->rchild)
            {
                Q.push(T->rchild);
                nPushQueueNumber++;
            }
    
            if (nVisitedNodeCount == nLevelMaxNumber)
            {
                nTreeHeight++;
                nLevelMaxNumber = nPushQueueNumber;
            }
        }
        return nTreeHeight;
    }
    
    void LevelOrderTraverseByNonRecursion(Bitree T)
    {
        if (!T)
            return;
    
        std::queue<Bitree> Q;
        Q.push(T);
        while (!Q.empty())
        {
            T = Q.front();
            Q.pop();
            printf("%c ", T->data);
            if (T->lchild)
                Q.push(T->lchild);
            if (T->rchild)
                Q.push(T->rchild);
        }
    }
    
    int main()
    {
        Bitree T;
        CreateBiTree(T);
        printf("树的高度是: %d\n", GetBiTreeHeightByNonRecursion(T));
    
        printf("先序遍历(非递归)：\n");
        PreOrderTraverseByNonRecursion(T);
        printf("\n");
    
        printf("中序遍历(非递归)：\n");
        InOrderTraverseByNonRecursion(T);
        printf("\n");
    
        printf("后序遍历(非递归)：\n");
        PostOrderTraverseByNonRecursion(T);
        printf("\n");
    
        printf("层序遍历(非递归)：\n");
        LevelOrderTraverseByNonRecursion(T);
        printf("\n");
    
        return 0;
    }

运行结果：  
![这里写图片描述][SouthEast 1]

[http_blog.csdn.net_yi_ming_he_article_details_71248881]: http://blog.csdn.net/yi_ming_he/article/details/71248881
[SouthEast]: /images/20220616/22f54d233ec6475caf7c01b638674698.png
[SouthEast 1]: /images/20220616/590d77bb6c1048a4a47501f5e12d8c23.png