树的四种遍历C/C++实现

树的四种遍历C/C++实现

备考期末，懂得都懂，手敲遍代码；
比较懒，都是递归形式

结构定义

typedef char ElemType;
typedef struct BiNode{
    ElemType data;
    struct BiNode *lchild, *rchild;
} BiTNode, *BiTree;

先序创建树

void CreateBiTree(BiTree &T){
    ElemType ch;
    cin >> ch;
    if(ch == '#')  T = NULL;
    else {
        T = new BiNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

先序遍历

void PreOrderTraverse(BiTree &T){
    if(!T) return ;
    cout << T->data << " ";
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

中序遍历

void InOrderTraverse(BiTree &T){
    if(!T) return ;
    InOrderTraverse(T->lchild);
    cout << T->data << " ";
    InOrderTraverse(T->rchild);
}

后序遍历

void PostOrderTraverse(BiTree &T){
    if(!T) return ;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    cout << T->data << " ";
}

层次遍历

void LeverOrderTraverse(BiTree &T){
    queue<BiTree> Tree;
    BiTree sNode = T;
    Tree.push(sNode);
    while(!Tree.empty()){
        sNode = Tree.front();
        Tree.pop();
        cout<< sNode->data << " ";
        if(sNode->lchild) Tree.push(sNode->lchild);
        if(sNode->rchild) Tree.push(sNode->rchild);
    }
}

总代码 （给懒人下载运行用）

#include <iostream>
#include <queue>
using namespace std;

typedef char ElemType;
typedef struct BiNode{
    ElemType data;
    struct BiNode *lchild, *rchild;
} BiTNode, *BiTree;
// 先序创建树
void CreateBiTree(BiTree &T){
    ElemType ch;
    cin >> ch;
    if(ch == '#')  T = NULL;
    else {
        T = new BiNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
// 先序遍历
void PreOrderTraverse(BiTree &T){
    if(!T) return ;
    cout << T->data << " ";
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
// 中序遍历
void InOrderTraverse(BiTree &T){
    if(!T) return ;
    InOrderTraverse(T->lchild);
    cout << T->data << " ";
    InOrderTraverse(T->rchild);
}
// 后序遍历
void PostOrderTraverse(BiTree &T){
    if(!T) return ;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    cout << T->data << " ";
}
// 层次遍历
void LeverOrderTraverse(BiTree &T){
    queue<BiTree> Tree;
    BiTree sNode = T;
    Tree.push(sNode);
    while(!Tree.empty()){
        sNode = Tree.front();
        Tree.pop();
        cout<< sNode->data << " ";
        if(sNode->lchild) Tree.push(sNode->lchild);
        if(sNode->rchild) Tree.push(sNode->rchild);
    }
}

int main(){
    BiTree tree;
    CreateBiTree(tree);
    PreOrderTraverse(tree);
    cout << endl;
    InOrderTraverse(tree);
    cout << endl;
    PostOrderTraverse(tree);
    cout << endl;
    LeverOrderTraverse(tree);
    cout << endl;

    cin.get();
    cin.get();
    return 0;
}

运行示例

1 2 4 # # 5 # # 3 # 6 7 # # #
1 2 4 5 3 6 7
4 2 5 1 3 7 6
4 5 2 7 6 3 1
1 2 3 4 5 6 7

输入测试数据:

1 2 4 # # 5 # # 3 # 6 7 # # #

运行结果：

1 2 4 5 3 6 7
4 2 5 1 3 7 6
4 5 2 7 6 3 1
1 2 3 4 5 6 7