題目要求
編寫程序普监，用先序遞歸遍歷法（或輸入先序及中序遞歸遍歷結(jié)點訪問序列）建立二叉樹的二叉鏈表存儲結(jié)構(gòu)贵试，計算并輸出二叉樹的結(jié)點總數(shù)以及樹的高度；然后輸出其先序凯正、中序毙玻、后序以及層次遍歷結(jié)點訪問次序。其中層次遍歷的實現(xiàn)需使用循環(huán)隊列廊散。二叉樹結(jié)點數(shù)據(jù)類型建議選用字符類型桑滩。
數(shù)據(jù)結(jié)構(gòu)設(shè)計
采用C++的模板類运准，創(chuàng)建隊列。每個隊列對象中缭受，elem指針用來建立長度為n的數(shù)組胁澳，n表示隊列的容量，front表示隊頭指針米者，rear表示隊尾指針胰丁，c表示隊列中當(dāng)前元素的個數(shù)。
采用結(jié)構(gòu)體建立二叉樹喂分，其中锦庸，data表示數(shù)據(jù)域，lchild表示左指針妻顶，rchild表示右指針酸员，BiT表示二叉樹結(jié)構(gòu)體指針類型變量蜒车，BiTNode表示二叉樹結(jié)構(gòu)體類型變量。
算法設(shè)計簡要描述
- 先序遍歷建立二叉樹：遞歸調(diào)用函數(shù)幔嗦，不斷讀取字符酿愧，依次建立左子樹和右子樹，當(dāng)讀取到‘#’字符時邀泉，返回NULL指針嬉挡，最終返回根結(jié)點指針。
- 先序和中序遍歷結(jié)點訪問序列建立二叉樹：
a. 先由先序序列求得根節(jié)點汇恤；
b. 再由根節(jié)點在中序序列中的位置庞钢，知：它之前的訪問的結(jié)點為其左子樹結(jié)點，它之后訪問的為其右子樹結(jié)點因谎；
c. 遞歸應(yīng)用a基括，b兩條。
程序代碼
#include <conio.h>
#include <iostream>
using namespace std;
typedef char ElemTp;
#define MAX 20
template <typename T>
class Queue //模板類：隊列
{
public:
Queue(); //默認(rèn)構(gòu)造函數(shù)
Queue(int n); //構(gòu)造函數(shù)财岔，調(diào)用函數(shù)createQueue(int n)风皿，創(chuàng)建長度為n的隊列
~Queue(); //虛構(gòu)函數(shù)
int createQueue(int n); //創(chuàng)建長度為n的隊列
int empty(); //判斷隊列是否為空
int full(); //判斷隊列是否為滿
int enQueue(T e); //元素e入隊
int dlQueue(T &e); //元素出隊，保存在e中
private:
T *elem; //建立長度為n的數(shù)組
int n; //隊列容量
int front; //隊頭指針
int rear; //隊尾指針
int c; //隊列當(dāng)前元素個數(shù)
};
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é)點
}
}
void layertravel(BiT bt) //層次遍歷二叉樹
{
if (bt == NULL)
return;
Queue<BiT> q(MAX); //建立隊列
q.enQueue(bt); //根節(jié)點入隊
while (!q.empty())
{
q.dlQueue(bt); //根節(jié)點出隊
visit(bt); //訪問根節(jié)點
if (bt->lchild)
q.enQueue(bt->lchild); //左子樹不空匠璧，訪問左子樹
if (bt->rchild)
q.enQueue(bt->rchild); //右子樹不空桐款，訪問右子樹
}
}
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;
}
BiT crtPreMidBT(char *pr, int &i, char *mi, int u, int v) //先序及中序遞歸遍歷結(jié)點訪問序列建立二叉樹算法
{
BiT bt;
int k;
if (u > v)
return NULL;
bt = new BiTNode();
bt->data = pr[i++]; //pr[i]為子樹根節(jié)點
for (k = u; k <= v; k++) //mi[u...v]為子樹中序序列
{
if (mi[k] == bt->data) //查找根節(jié)點在中序序列中的位置
break;
}
bt->lchild = crtPreMidBT(pr, i, mi, u, k - 1); //遞歸建立左子樹
bt->rchild = crtPreMidBT(pr, i, mi, k + 1, v); //遞歸建立右子樹
return bt;
}
int height(BiT bt) //計算二叉樹的高度
{
int hl, hr;
if (!bt)
return 0;
hl = height(bt->lchild); //遞歸計算左子樹的高度
hr = height(bt->rchild); //遞歸計算右子樹的高度
return (hl > hr) ? (hl + 1) : (hr + 1); //返回整個二叉樹的高度(左、右子樹高度較大的值加一)
}
int nodeNum(BiT bt) //計算二叉樹的總結(jié)點數(shù)
{
int nl, nr;
if (!bt)
return 0;
nl = nodeNum(bt->lchild); //遞歸計算左子樹的結(jié)點數(shù)
nr = nodeNum(bt->rchild); //遞歸計算右子樹的結(jié)點數(shù)
return nl + nr + 1; //返回整個二叉樹的結(jié)點數(shù)(左夷恍、右子樹結(jié)點數(shù)之和加一)
}
void choose(BiT &bt) //選擇建立二叉樹的方式
{
char num, pre[MAX], mid[MAX];
int i = 0, u = 0, v;
cout << "請選擇建立二叉樹的方式: " << endl;
cout << "1. 先序遍歷建立二叉樹" << endl;
cout << "2. 先序和中序遍歷建立二叉樹" << endl;
num = _getch();
switch (num)
{
case '1': //先序遍歷建立二叉樹
{
cout << "您選擇了第一種方式." << endl;
cout << "請輸入先序遍歷的字符序列: " << endl;
bt = crtPreBT();
} break;
case '2': //先序和中序遍歷建立二叉樹
{
cout << "您選擇了第二種方式." << endl;
cout << "請輸入先序遍歷的字符序列: " << endl;
cin.getline(pre, MAX);
cout << "請輸入中序遍歷的字符序列: " << endl;
cin.getline(mid, MAX);
v = strlen(mid) - 1;
bt = crtPreMidBT(pre, i, mid, u, v);
} break;
}
}
template<typename T>
Queue<T>::Queue()
{
front = rear = -1;
c = 0;
}
template<typename T>
Queue<T>::Queue(int n)
{
createQueue(n);
}
template<typename T>
Queue<T>::~Queue()
{
c = 0;
front = rear = -1;
delete[]elem;
}
template<typename T>
int Queue<T>::createQueue(int n)
{
if (n <= 0)
return 0;
this->n = n;
c = 0;
front = rear = -1;
elem = new T[n];
if (!elem)
return 0;
return 1;
}
template<typename T>
int Queue<T>::empty()
{
return c == 0;
}
template<typename T>
int Queue<T>::full()
{
return c == n;
}
template<typename T>
int Queue<T>::enQueue(T e)
{
if (c == n)
return 0; //隊滿魔眨，入隊失敗
rear = (rear + 1) % n;
elem[rear] = e;
c++;
return 1; //入隊成功返回1
}
template<typename T>
int Queue<T>::dlQueue(T & e)
{
if (c == 0)
return 0; //隊空，出隊失敗
front = (front + 1) % n;
e = elem[front];
c--;
return 1; //出隊成功返回1
}
int main()
{
int h, num;
BiT bt;
choose(bt);
h = height(bt);
cout << "二叉樹的高度是: " << h << endl;
num = nodeNum(bt);
cout << "二叉樹的總結(jié)點數(shù)是: " << num << endl;
cout << "先序遍歷結(jié)點訪問次序: " << endl;
preorder(bt);
cout << endl;
cout << "中序遍歷結(jié)點訪問次序: " << endl;
midorder(bt);
cout << endl;
cout << "后序遍歷結(jié)點訪問次序: " << endl;
lasorder(bt);
cout << endl;
cout << "層次遍歷結(jié)點訪問次序: " << endl;
layertravel(bt);
cout << endl;
return 0;
}
示例
（1）程序輸入：
先序序列：abc##de#g##f###
程序輸出：
二叉樹的高度是：5
二叉樹的總結(jié)點數(shù)是：7
先序遍歷：a b c d e g f
中序遍歷：c b e g d f a
后序遍歷：c g e f d b a
層次遍歷：a b c d e f g
（2）程序輸入：
先序序列：ABCDEFG
中序序列：CBEDAFG
程序輸出：
二叉樹的高度是：4
二叉樹的總結(jié)點數(shù)是：7
先序遍歷：A B C D E F G
中序遍歷：C B E D A F G
后序遍歷：C E D B G F A
層次遍歷：A B F C D G E
（3）程序輸入：
先序序列：ABDF####C#E#G#H##
程序輸出：
二叉樹的高度是：5
二叉樹的總結(jié)點數(shù)是：8
先序遍歷：A B D F C E G H
中序遍歷：F D B A C E G H
后序遍歷：F D B H G E C A
層次遍歷：A B C D E F G H
（4）程序輸入：
先序序列：#
程序輸出：
二叉樹的高度是：0
二叉樹的總結(jié)點數(shù)是：0
