二叉树的先序、中序、后序、层序遍历的递归与非递归实现 C++

先序遍历 递归算法

void PreOrder(BiTree T)
{
    if (T != NULL)
    {
        cout << T->data << " ";
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

非递归算法

// 二叉树的先序遍历_非递归算法
void PreOrder2(BiTree T)
{
    stack<BiTree>S;
    BiTree p = T;
    while (p || !S.empty())
    {
        if (p){
            S.push(p);
            cout << p->data << " ";
            p = p->lchild;
        } else{
            p = S.top();
            S.pop();
            p = p->rchild;
        }
    }
}

中序遍历 递归算法

// 二叉树的中序遍历_递归算法
void InOrder(BiTree T)
{
    if (T != NULL)
    {
        InOrder(T->lchild);
        cout << T->data << " ";
        InOrder(T->rchild);
    }
}

非递归算法

// 二叉树的中序遍历_非递归算法
void InOrder2(BiTree T)
{
    stack<BiTree>S;
    BiTree p = T;
    while (p || !S.empty())
    {
        if (p){
            S.push(p);
            p = p->lchild;
        } else{
            p = S.top();
            S.pop();
            cout << p->data << " ";
            p = p->rchild;
        }
    }
}

后序遍历 递归算法

// 二叉树的后序遍历_递归算法
void PostOrder(BiTree T)
{
    if (T != NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout << T->data << " ";
    }
}

非递归算法

// 二叉树的后序遍历_非递归算法
void PostOrder2(BiTree T)
{
    stack<BiTree>S;
    BiTree p = T;
    BiTree r;
    while (p || !S.empty())
    {
        if (p){
            S.push(p);
            p = p->lchild;
        } else{
            p = S.top();
            if (p->rchild && p->rchild!=r)  // 右子树存在，且未被访问过
                p = p->rchild;
            else{
                S.pop();
                cout << p->data << " ";
                r = p;
                p = nullptr;    // 重制p指针
            }
        }
    }
}

层序遍历 非递归算法

// 二叉树的层序遍历
void LevelOrder(BiTree T)
{
    queue<BiTree>Q;
    BiTree p;
    Q.push(T);
    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
        cout << p->data << " ";
        if (p->lchild != NULL)
            Q.push(p->lchild);
        if (p->rchild != NULL)
            Q.push(p->rchild);
    }
}

可执行C++程序

输入可根据终端提示进行输入二叉树
或者使用现成样例：

1 2 0 4 6 0 0 0 3 0 5 0 0

#include 
#include 
#include 
using namespace std;
typedef int ElemType;
// 二叉树的链式存储构造
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 二叉树的初始化
void InitBiTree(BiTree T);
// 递归初始化二叉树
void InitChild(BiTree T);
// 二叉树的先序遍历_递归算法
void PreOrder(BiTree T);
// 二叉树的先序遍历_非递归算法
void PreOrder2(BiTree T);
// 二叉树的中序遍历_递归算法
void InOrder(BiTree T);
// 二叉树的中序遍历_非递归算法
void InOrder2(BiTree T);
// 二叉树的后序遍历_递归算法
void PostOrder(BiTree T);
// 二叉树的后序遍历_非递归算法
void PostOrder2(BiTree T);
// 二叉树的层序遍历
void LevelOrder(BiTree T);
// ----------------------
//         main
int main()
{
    BiTree T;
    T = (BiTree) malloc(sizeof(BiTNode));
    InitBiTree(T);
    cout << "二叉树的先序遍历_递归结果为：";
    PreOrder(T);
    cout << endl;
    cout << "二叉树的先序遍历_非递归结果为：";
    PreOrder2(T);
    cout << endl;
    cout << "二叉树的中序遍历_递归结果为：";
    InOrder(T);
    cout << endl;
    cout << "二叉树的中序遍历_非递归结果为：";
    InOrder2(T);
    cout << endl;
    cout << "二叉树的后序遍历_递归结果为：";
    PostOrder(T);
    cout << endl;
    cout << "二叉树的后序遍历_非递归结果为：";
    PostOrder2(T);
    cout << endl;
    cout << "二叉树的层序遍历_非递归结果为：";
    LevelOrder(T);
    cout << endl;
    return 0;
}
// ----------------------
// 二叉树的初始化
void InitBiTree(BiTree T)
{
    ElemType Input;
    cout << "请输入根节点：" ;
    cin >> Input;
    T->data = Input;
    InitChild(T);
    cout << endl << "二叉树已初始化完毕" << endl;
    cout << "--------------------------" << endl;
}
// 递归初始化二叉树
void InitChild(BiTree T)
{

    ElemType Input;
    cout << "请输入结点" << T->data << "的左孩子（输入0表示无左孩子）：";
    cin >> Input;
    if (Input != 0)
    {
        BiTree temp;
        temp = (BiTree) malloc(sizeof(BiTNode));
        T->lchild = temp;
        temp->data = Input;
        InitChild(T->lchild);
    }
    cout << "请输入结点" << T->data << "的右孩子（输入0表示无右孩子）：";
    cin >> Input;
    if (Input != 0)
    {
        BiTree temp;
        temp = (BiTree) malloc(sizeof(BiTNode));
        T->rchild = temp;
        temp->data = Input;
        InitChild(T->rchild);
    }

}
// 二叉树的先序遍历_递归算法
void PreOrder(BiTree T)
{
    if (T != NULL)
    {
        cout << T->data << " ";
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
// 二叉树的先序遍历_非递归算法
void PreOrder2(BiTree T)
{
    stack<BiTree>S;
    BiTree p = T;
    while (p || !S.empty())
    {
        if (p){
            S.push(p);
            cout << p->data << " ";
            p = p->lchild;
        } else{
            p = S.top();
            S.pop();
            p = p->rchild;
        }
    }
}
// 二叉树的中序遍历_递归算法
void InOrder(BiTree T)
{
    if (T != NULL)
    {
        InOrder(T->lchild);
        cout << T->data << " ";
        InOrder(T->rchild);
    }
}
// 二叉树的中序遍历_非递归算法
void InOrder2(BiTree T)
{
    stack<BiTree>S;
    BiTree p = T;
    while (p || !S.empty())
    {
        if (p){
            S.push(p);
            p = p->lchild;
        } else{
            p = S.top();
            S.pop();
            cout << p->data << " ";
            p = p->rchild;
        }
    }
}
// 二叉树的后序遍历_递归算法
void PostOrder(BiTree T)
{
    if (T != NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout << T->data << " ";
    }
}
// 二叉树的后序遍历_非递归算法
void PostOrder2(BiTree T)
{
    stack<BiTree>S;
    BiTree p = T;
    BiTree r;
    while (p || !S.empty())
    {
        if (p){
            S.push(p);
            p = p->lchild;
        } else{
            p = S.top();
            if (p->rchild && p->rchild!=r)  // 右子树存在，且未被访问过
                p = p->rchild;
            else{
                S.pop();
                cout << p->data << " ";
                r = p;
                p = nullptr;    // 重制p指针
            }
        }
    }
}
// 二叉树的层序遍历
void LevelOrder(BiTree T)
{
    queue<BiTree>Q;
    BiTree p;
    Q.push(T);
    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
        cout << p->data << " ";
        if (p->lchild != NULL)
            Q.push(p->lchild);
        if (p->rchild != NULL)
            Q.push(p->rchild);
    }
}

运行结果