二叉樹的查找(前序、中序、後序、層序遍歷)--biaobiao88

建立一棵含有n個結點的二叉樹，採用二叉鏈表存儲；

輸出前序、中序、後序、、層序遍歷該二叉樹的遍歷結果。

定義二叉樹的數據類型——二叉樹結點結構體BiNode。建立二叉鏈表可以採用擴展二叉樹的一個遍歷序列，例如前序序列，將擴展二叉樹的前序序列由鍵盤輸入，建立該二叉樹的二叉鏈表存儲。

簡單起見，本實驗假定二叉樹的數據元素為char型

用模板類改寫

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<malloc.h>
int MaxSize = 100;
using namespace std;
typedef char DataType;
typedef struct BiNode
{
    DataType data;
    struct BiNode *lchile,*rchild;
}BiNode;
BiNode *root;

//創建拓展二叉樹，#代虛結點 
BiNode *Creat(BiNode *root)//          cishu   /////
{
    char ch;
    cin >> ch;
    if(ch == '#')
        root = NULL;
    else
    {
        root = (BiNode *)malloc(sizeof(BiNode));
        root->data = ch;
        root->lchile = Creat(root->lchile);
        root->rchild = Creat(root->rchild);
    }
    return root;
}

//前序遍歷 
void PreOrder(BiNode *root)
{
    if(root == NULL)
        return;
    else
    {
        cout << root->data << " ";
        PreOrder(root->lchile);
        PreOrder(root->rchild);
    }
}

//中序遍歷 
void InOrder(BiNode *root)
{
    if(root == NULL)
        return;
    else
    {
        InOrder(root->lchile);
        cout << root->data << " ";
        InOrder(root->rchild);
    }
}

//後序遍歷 
void PostOrder(BiNode *root)
{
    if(root == NULL)
        return;
    else
    {
        InOrder(root->lchile);
        InOrder(root->rchild);
        cout << root->data << " ";
    }
}

//層序遍歷 
void LevelOrder(BiNode *root)
{
    BiNode *q = NULL,*Q[MaxSize];
    int front = -1;
    int rear = -1;
    if(root == NULL)
        return;
    Q[++rear] = root;
    while(front != rear)
    {
        q = Q[++front];
        cout << q->data << " ";
        if(q->lchile != NULL)
            Q[++rear] = q->lchile;
        if(q->rchild != NULL)
            Q[++rear] = q->rchild;
    }
    
}

int main()
{
    BiNode *root = NULL;
    root = Creat(root);
    cout << "該二叉樹的根節點是：" << root->data << endl;
    cout << endl;
    cout << "該二叉樹的前序遍歷是：";
    PreOrder(root);
    cout << endl;
//    cout << "該二叉樹的根節點是：" << root->data << endl;
    cout << endl;
    cout << "該二叉樹的中序遍歷是：";
    InOrder(root);
    cout << endl;
//    cout << "該二叉樹的根節點是：" << root->data << endl;
    cout << endl;
    cout << "該二叉樹的後序遍歷是：";
    PostOrder(root);
    cout << endl;
//    cout << "該二叉樹的根節點是：" << root->data << endl;
    cout << endl;
    cout << "該二叉樹的層序遍歷是：";
    LevelOrder(root);
    cout << endl;
    return 0;
}

/*
abd##e##c#f##
該二叉樹的根節點是：a

該二叉樹的前序遍歷是：a b d e c f

該二叉樹的中序遍歷是：d b e a c f

該二叉樹的後序遍歷是：d b e c f a

該二叉樹的層序遍歷是：a b c d e f
*/