題目要求

設(shè)二叉樹采用二叉鏈表存儲結(jié)構(gòu)，結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽址愋?。編寫程序，用先序遞歸遍歷法建立二叉樹的二叉鏈表存儲結(jié)構(gòu)。然后輸入一個字符，輸出該字符在先、中、后序遍歷中的訪問次序（訪問次序從1開始）以及先、中、后序遍歷結(jié)果。若輸入的字符不在二叉樹中，輸出相應(yīng)提示信息。要求程序可以反復(fù)輸入字符并輸出訪問次序及遍歷結(jié)果，直到輸入某個特殊字符時(shí)結(jié)束程序。注意：輸入單個字符時(shí)需對其后的換行符進(jìn)行處理。

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

用結(jié)構(gòu)體建立二叉樹的二叉鏈表結(jié)構(gòu)。其中，data表示數(shù)據(jù)域，lchild表示左指針，rchild表示右指針，BiT表示二叉鏈表結(jié)構(gòu)體指針類型變量，BiTNode表示二叉鏈表結(jié)構(gòu)體類型變量。

算法設(shè)計(jì)簡要描述

1. 先序遍歷建立二叉樹：遞歸調(diào)用函數(shù)，不斷讀取字符，依次建立左子樹和右子樹，當(dāng)讀取到‘#’字符時(shí)，返回NULL指針，最終返回根結(jié)點(diǎn)指針。
2. 查詢字符是否在二叉樹中：在while循環(huán)中，反復(fù)輸入字符，依次輸出先序、中序、后序遍歷結(jié)果，并判斷該字符是否在二叉樹中。

程序代碼

#include <iostream>
using namespace std;
typedef struct node                             //二叉鏈表
{
    ElemTp data;                                //數(shù)據(jù)域
    struct node *lchild,                        //左指針
        *rchild;                                //右指針
}*BiT, BiTNode;
void visit(BiT e)                               //訪問函數(shù)      
{
    if (e->data != NULL)                        //輸出二叉樹的數(shù)據(jù)域
        cout << e->data << "  ";
}
void preorder(BiT bt)                           //先序遍歷二叉樹
{
    if (bt)
    {
        visit(bt);                              //訪問根節(jié)點(diǎn)
        preorder(bt->lchild);                   //遞歸調(diào)用遍歷左子樹
        preorder(bt->rchild);                   //遞歸調(diào)用遍歷右子樹
    }
}
void midorder(BiT bt)                           //中序遍歷二叉樹
{
    if (bt)
    {
        midorder(bt->lchild);                   //遞歸調(diào)用遍歷左子樹
        visit(bt);                              //訪問根節(jié)點(diǎn)
        midorder(bt->rchild);                   //遞歸調(diào)用遍歷右子樹
    }
}
void lasorder(BiT bt)                           //后序遍歷二叉樹
{
    if (bt)
    {
        lasorder(bt->lchild);                   //遞歸調(diào)用遍歷左子樹
        lasorder(bt->rchild);                   //遞歸調(diào)用遍歷右子樹
        visit(bt);                              //訪問根節(jié)點(diǎn)
    }
}
BiT crtPreBT()                                  //先序遞歸遍歷建立二叉樹算法
{
    BiT bt;
    char ch;
    ch = getchar();
    if (ch == '#')                              //讀到‘#’返回NULL指針
        return NULL;    
    bt = new BiTNode();                         //建立新的二叉樹結(jié)點(diǎn)
    bt->data = ch;
    bt->lchild = crtPreBT();                    //遞歸建立左子樹
    bt->rchild = crtPreBT();                    //遞歸建立右子樹
    return bt;
}
void prefind(BiT bt, ElemTp c, int &k)          //先序查詢(bt為根節(jié)點(diǎn),c為查詢元素,k記錄查詢元素的位置)
{
    if (!bt || k > 0)                           //bt為空,或者k>0,直接返回
        return;
    k--;                        
    if (bt->data == c)                          //查詢到了元素c，將k變?yōu)閗的相反數(shù)
        k = -k;
    if (k > 0)
        return;
    prefind(bt->lchild, c, k);                  //遞歸查詢左子樹
    prefind(bt->rchild, c, k);                  //遞歸查詢右子樹
}
void midfind(BiT bt, ElemTp c, int &k)          //中序查詢(bt為根節(jié)點(diǎn),c為查詢元素,k記錄查詢元素的位置)
{
    if (!bt || k > 0)                           //bt為空,或者k>0,直接返回
        return;
    midfind(bt->lchild, c, k);                  //遞歸查詢左子樹
    if (k > 0)
        return;
    k--;
    if (bt->data == c)                          //查詢到了元素c，將k變?yōu)閗的相反數(shù)
        k = -k;
    midfind(bt->rchild, c, k);                  //遞歸查詢右子樹
}
void lasfind(BiT bt, ElemTp c, int &k)          //后序查詢(bt為根節(jié)點(diǎn),c為查詢元素,k記錄查詢元素的位置)
{
    if (!bt || k > 0)                           //bt為空,或者k>0,直接返回
        return;
    lasfind(bt->lchild, c, k);                  //遞歸查詢左子樹
    lasfind(bt->rchild, c, k);                  //遞歸查詢右子樹
    if (k > 0)
        return;
    k--;
    if (bt->data == c)                          //查詢到了元素c，將k變?yōu)閗的相反數(shù)
        k = -k;
}
int main()
{
    int pre_n, mid_n, las_n;
    pre_n = mid_n = las_n = 0;        //pre_n, mid_n, las_n分別記錄先序、中序、后序中該元素的位置
    ElemTp c;
    BiT bt;
    cout << "請輸入先序遍歷的字符序列: " << endl;
    bt = crtPreBT();
    cout << "先序遍歷結(jié)點(diǎn)訪問次序: " << endl;
    preorder(bt);
    cout << endl;
    cout << "中序遍歷結(jié)點(diǎn)訪問次序: " << endl;
    midorder(bt);
    cout << endl;
    cout << "后序遍歷結(jié)點(diǎn)訪問次序: " << endl;
    lasorder(bt);
    cout << endl;
    cout << "請輸入要查找的字符('#'結(jié)束): " << endl;
    cin >> c;
    while (c != '#')                                //輸入'#'結(jié)束
    {
        prefind(bt, c, pre_n);
        midfind(bt, c, mid_n);
        lasfind(bt, c, las_n);
        cout << "先序遍歷結(jié)點(diǎn)訪問次序: " << endl;
        preorder(bt);
        cout << endl;
        cout << "中序遍歷結(jié)點(diǎn)訪問次序: " << endl;
        midorder(bt);
        cout << endl;
        cout << "后序遍歷結(jié)點(diǎn)訪問次序: " << endl;
        lasorder(bt);
        cout << endl;
        if (pre_n > 0 && mid_n > 0 && las_n > 0)
        {
            cout << "先序遍歷中該字符的訪問次序?yàn)? " << pre_n << endl;
            cout << "中序遍歷中該字符的訪問次序?yàn)? " << mid_n << endl;
            cout << "后序遍歷中該字符的訪問次序?yàn)? " << las_n << endl;
        }
        else
            cout << "二叉樹中不存在該字符" << endl;
        pre_n = mid_n = las_n = 0;
        cout << "請輸入下一個要查找的字符('#'結(jié)束): " << endl;
        cin >> c;
    }
    return 0;
}

示例

（1）程序輸入：
先序序列：ABC##DE#G##F###
請輸入要查找的字符('#'結(jié)束):A G #