二叉树前序中序后序遍历(递归和非递归)以及层序遍历代码

树的定义以及采用先序遍历输入节点数据

//树的结构体定义
typedef struct BiTree
{
    char data;
    struct BiTree *lchild,*rchild;
}BiNode, *BTree;

//递归创建二叉链表
void CreatBiTree(BTree &T)
{
    char ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BiTree;
        T->data = ch;//先序创建
        CreatBiTree(T->lchild);
        //T->data=ch;//中序创建
        CreatBiTree(T->rchild);
        //T->data=ch;//后序创建
    }

}

递归方法实现三种遍历

//递归方法
void PreOderRecursive(BTree root){
    if(root){
        printf("%c ", root->data);
        PreOderRecursive(root->lchild);
        PreOderRecursive(root->rchild);
    }
}

void InOderRecursive(BTree root){
    if(root){
        InOderRecursive(root->lchild);
        printf("%c ", root->data);
        InOderRecursive(root->rchild);
    }
}

void PostOderRecursive(BTree root){
    if(root){
        PostOderRecursive(root->lchild);
        PostOderRecursive(root->rchild);
        printf("%c ", root->data);
    }
}

非递归方法实现三种遍历

//非递归方法
void PreOder(BTree root){
    stack<BTree> Btstack;
    BTree T = root;
    while(T || !Btstack.empty()){
        while (T) {
            Btstack.push(T);
            printf("%c ", T->data);
            T = T->lchild;
        }
        T = Btstack.top();
        Btstack.pop();
        T = T->rchild;
    }
}

void InOder(BTree root){
    stack<BTree> Btstack;
    BTree T = root;
    while (T || !Btstack.empty()) {
        while (T) {
            Btstack.push(T);
            T = T->lchild;
        }
        T = Btstack.top();
        Btstack.pop();
        printf("%c ", T->data);;
        T = T->rchild;
    }
}

void PostOrder(BTree root) {
    stack<BTree> Btstack;
    BTree top, last = NULL;
    BTree T = root;
    while (T || !Btstack.empty()) {
        while (T) {
            Btstack.push(T);
            T = T->lchild;
        }
        top = Btstack.top();
        if (top->rchild == NULL || top->rchild == last){
            printf("%c ", top->data);
            Btstack.pop();
            last = top;
        }
        else{
            T = top->rchild;
        }
    }
}

层序遍历

//层序遍历

void LevelOrder(BTree root){
    queue<BTree> Btqueue;
    BTree T = root;
    while (T || Btqueue.empty()) {
        printf("%c ", T->data);;
        if(T->lchild)
            Btqueue.push(T->lchild);
        if(T->rchild)
            Btqueue.push(T->rchild);
        T = Btqueue.front();
        Btqueue.pop();
    }
}

代码测试部分

//主函数，测试部分
int main(){
    BTree A;
    cout << "请按先序遍历输入数据：" << endl;
    CreatBiTree(A);
    cout << endl;
    cout << "递归先序遍历输出结果：" << endl;
    PreOderRecursive(A);
    cout << endl;
    cout << "递归中序遍历输出结果：" << endl;
    InOderRecursive(A);
    cout << endl;
    cout << "递归后序遍历输出结果：" << endl;
    PostOderRecursive(A);
    cout << endl;
    cout << "非递归先序遍历输出结果：" << endl;
    PreOder(A);
    cout << endl;
    cout << "非递归中序遍历输出结果：" << endl;
    InOder(A);
    cout << endl;
    cout << "非递归后序遍历输出结果：" << endl;
    PostOrder(A);
    cout << endl;
    cout << "层序遍历输出结果：" << endl;
    LevelOrder(A);
    cout << endl;
    return 0;
}

测试结果

请按先序遍历输入数据：
AB#C##D#E#F##

递归先序遍历输出结果：
A B C D E F 
递归中序遍历输出结果：
B C A D E F 
递归后序遍历输出结果：
C B F E D A 
非递归先序遍历输出结果：
A B C D E F 
非递归中序遍历输出结果：
B C A D E F 
非递归后序遍历输出结果：
C B F E D A 
层序遍历输出结果：
A B D C E F 
Press <RETURN> to close this window...