[数据结构与算法]二叉树的基本操作（C++）

二叉树的二叉链表存储表示

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

构建二叉树（先序构建）

输入字符，‘#’表示空，即 T=NULL

char num;
cout<<"请输入该节点的值："<<endl;
cin>>num;
if(num == '#') T=NULL;
else{
    T = new BiTNode;
    T->data = num;
    cout<<num<<"的左节点，";
    creatBiTree(T->lchild);
    cout<<num<<"的右节点，";
    creatBiTree(T->rchild);
}

先序遍历二叉树（递归）

if(T){
    cout<<T->data;
    preOrderTraversal(T->lchild);
    preOrderTraversal(T->rchild);
}else{
    return;
}

中序遍历二叉树（递归）

if(T){
    inOrderTraversal(T->lchild);
    cout<<T->data;
    inOrderTraversal(T->rchild);
}else{
    return;
}

后序遍历二叉树（递归）

if(T){
    postOrderTraversal(T->lchild);
    postOrderTraversal(T->rchild);
    cout<<T->data;
}else{
    return;
}

全部代码

#include <iostream>

using namespace std;

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

void creatBiTree(BiTree &T)
{
    char num;
    cout<<"请输入该节点的值："<<endl;
    cin>>num;
    if(num == '#') T=NULL;
    else{
        T = new BiTNode;
        T->data = num;
        cout<<num<<"的左节点，";
        creatBiTree(T->lchild);
        cout<<num<<"的右节点，";
        creatBiTree(T->rchild);
    }
}

void preOrderTraversal(BiTree &T)
{
    if(T){
        cout<<T->data;
        preOrderTraversal(T->lchild);
        preOrderTraversal(T->rchild);
    }else{
        return;
    }
}

void inOrderTraversal(BiTree &T)
{
    if(T){
        inOrderTraversal(T->lchild);
        cout<<T->data;
        inOrderTraversal(T->rchild);
    }else{
        return;
    }
}

void postOrderTraversal(BiTree &T)
{
    if(T){
        postOrderTraversal(T->lchild);
        postOrderTraversal(T->rchild);
        cout<<T->data;
    }else{
        return;
    }
}

int main()
{
    int n;
    BiTree T;
    do {
        cout<<endl;
        cout<<"----------------------------------------"<<endl;
        cout<<"             1、构建二叉树                "<<endl;
        cout<<"             2、先序遍历二叉树             "<<endl;
        cout<<"             3、中序遍历二叉树             "<<endl;
        cout<<"             4、后序遍历二叉树             "<<endl;
        cout<<"             0、退出                     "<<endl;
        cout<<"----------------------------------------"<<endl;
        cout<<"请选择："<<endl;
        cin>>n;
        while(n!=0 && n!=1 && n!=2 && n!=3 && n!=4 && n!=5){
            cout<<"输入有误，请重新输入："<<endl;
            cin>>n;
        }
        switch (n) {
            case 1: creatBiTree(T);break;
            case 2: preOrderTraversal(T);break;
            case 3: inOrderTraversal(T);break;
            case 4: postOrderTraversal(T);break;
            case 6: break;
        }
    } while (n!=0);

    return 0;
}

运行结果

?

?

?