題目要求
設(shè)二叉樹采用二叉鏈表存儲結(jié)構(gòu)谆构,結(jié)點數(shù)據(jù)域為字符類型。編寫程序框都,用先序遞歸遍歷法建立二叉樹的二叉鏈表存儲結(jié)構(gòu)搬素。然后輸入一個字符,輸出該字符在先魏保、中熬尺、后序遍歷中的訪問次序(訪問次序從1開始)以及先、中谓罗、后序遍歷結(jié)果粱哼。若輸入的字符不在二叉樹中,輸出相應(yīng)提示信息檩咱。要求程序可以反復輸入字符并輸出訪問次序及遍歷結(jié)果揭措,直到輸入某個特殊字符時結(jié)束程序胯舷。注意:輸入單個字符時需對其后的換行符進行處理。
數(shù)據(jù)結(jié)構(gòu)設(shè)計
用結(jié)構(gòu)體建立二叉樹的二叉鏈表結(jié)構(gòu)绊含。其中桑嘶,data表示數(shù)據(jù)域,lchild表示左指針躬充,rchild表示右指針逃顶,BiT表示二叉鏈表結(jié)構(gòu)體指針類型變量,BiTNode表示二叉鏈表結(jié)構(gòu)體類型變量充甚。
算法設(shè)計簡要描述
- 先序遍歷建立二叉樹:遞歸調(diào)用函數(shù)以政,不斷讀取字符,依次建立左子樹和右子樹伴找,當讀取到‘#’字符時盈蛮,返回NULL指針,最終返回根結(jié)點指針疆瑰。
- 查詢字符是否在二叉樹中:在while循環(huán)中,反復輸入字符昙啄,依次輸出先序穆役、中序、后序遍歷結(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é)點
preorder(bt->lchild); //遞歸調(diào)用遍歷左子樹
preorder(bt->rchild); //遞歸調(diào)用遍歷右子樹
}
}
void midorder(BiT bt) //中序遍歷二叉樹
{
if (bt)
{
midorder(bt->lchild); //遞歸調(diào)用遍歷左子樹
visit(bt); //訪問根節(jié)點
midorder(bt->rchild); //遞歸調(diào)用遍歷右子樹
}
}
void lasorder(BiT bt) //后序遍歷二叉樹
{
if (bt)
{
lasorder(bt->lchild); //遞歸調(diào)用遍歷左子樹
lasorder(bt->rchild); //遞歸調(diào)用遍歷右子樹
visit(bt); //訪問根節(jié)點
}
}
BiT crtPreBT() //先序遞歸遍歷建立二叉樹算法
{
BiT bt;
char ch;
ch = getchar();
if (ch == '#') //讀到‘#’返回NULL指針
return NULL;
bt = new BiTNode(); //建立新的二叉樹結(jié)點
bt->data = ch;
bt->lchild = crtPreBT(); //遞歸建立左子樹
bt->rchild = crtPreBT(); //遞歸建立右子樹
return bt;
}
void prefind(BiT bt, ElemTp c, int &k) //先序查詢(bt為根節(jié)點,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é)點,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é)點,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é)點訪問次序: " << endl;
preorder(bt);
cout << endl;
cout << "中序遍歷結(jié)點訪問次序: " << endl;
midorder(bt);
cout << endl;
cout << "后序遍歷結(jié)點訪問次序: " << 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é)點訪問次序: " << endl;
preorder(bt);
cout << endl;
cout << "中序遍歷結(jié)點訪問次序: " << endl;
midorder(bt);
cout << endl;
cout << "后序遍歷結(jié)點訪問次序: " << endl;
lasorder(bt);
cout << endl;
if (pre_n > 0 && mid_n > 0 && las_n > 0)
{
cout << "先序遍歷中該字符的訪問次序為: " << pre_n << endl;
cout << "中序遍歷中該字符的訪問次序為: " << mid_n << endl;
cout << "后序遍歷中該字符的訪問次序為: " << 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 #
程序輸出
先序遍歷:A B C D E G F
中序遍歷:C B E G D F A
后序遍歷:C G E F D B A
A: 先序遍歷中該字符的訪問次序:1
中序遍歷中該字符的訪問次序:7
后序遍歷中該字符的訪問次序:7
G: 先序遍歷中該字符的訪問次序:6
中序遍歷中該字符的訪問次序:4
后序遍歷中該字符的訪問次序:2
(2)程序輸入:
先序序列:ABDF####C#E#G#H##
請輸入要查找的字符('#'結(jié)束):H R #
程序輸出
先序遍歷:A B D F C E G H
中序遍歷:F D B A C E G H
后序遍歷:F D B H G E C A
H: 先序遍歷中該字符的訪問次序:8
中序遍歷中該字符的訪問次序:8
后序遍歷中該字符的訪問次序:4
R: 二叉樹中不存在該字符