题目要求
编写程序，用先序递归遍历法（或输入先序及中序递归遍历结点访问序列）建立二叉树的二叉链表存储结构，计算并输出二叉树的结点总数以及树的高度；然后输出其先序、中序、后序以及层次遍历结点访问次序。其中层次遍历的实现需使用循环队列。二叉树结点数据类型建议选用字符类型。
数据结构设计
采用C++的模板类，创建队列。每个队列对象中，elem指针用来建立长度为n的数组，n表示队列的容量，front表示队头指针，rear表示队尾指针，c表示队列中当前元素的个数。
采用结构体建立二叉树，其中，data表示数据域，lchild表示左指针，rchild表示右指针，BiT表示二叉树结构体指针类型变量，BiTNode表示二叉树结构体类型变量。
算法设计简要描述
- 先序遍历建立二叉树：递归调用函数，不断读取字符，依次建立左子树和右子树，当读取到‘#’字符时，返回NULL指针，最终返回根结点指针。
- 先序和中序遍历结点访问序列建立二叉树：
a. 先由先序序列求得根节点；
b. 再由根节点在中序序列中的位置，知：它之前的访问的结点为其左子树结点，它之后访问的为其右子树结点；
c. 递归应用a，b两条。
程序代码
#include <conio.h>
#include <iostream>
using namespace std;
typedef char ElemTp;
#define MAX 20
template <typename T>
class Queue //模板类：队列
{
public:
Queue(); //默认构造函数
Queue(int n); //构造函数，调用函数createQueue(int n)，创建长度为n的队列
~Queue(); //虚构函数
int createQueue(int n); //创建长度为n的队列
int empty(); //判断队列是否为空
int full(); //判断队列是否为满
int enQueue(T e); //元素e入队
int dlQueue(T &e); //元素出队，保存在e中
private:
T *elem; //建立长度为n的数组
int n; //队列容量
int front; //队头指针
int rear; //队尾指针
int c; //队列当前元素个数
};
typedef struct node
{
ElemTp data; //数据域
struct node *lchild, //左指针
*rchild; //右指针
}*BiT,BiTNode;
void visit(BiT e) //访问函数
{
if (e->data != NULL) //输出二叉树的数据域
cout << e->data << " ";
}
void preorder(BiT bt) //先序遍历二叉树
{
if (bt)
{
visit(bt); //访问根节点
preorder(bt->lchild); //递归调用遍历左子树
preorder(bt->rchild); //递归调用遍历右子树
}
}
void midorder(BiT bt) //中序遍历二叉树
{
if (bt)
{
midorder(bt->lchild); //递归调用遍历左子树
visit(bt); //访问根节点
midorder(bt->rchild); //递归调用遍历右子树
}
}
void lasorder(BiT bt) //后序遍历二叉树
{
if (bt)
{
lasorder(bt->lchild); //递归调用遍历左子树
lasorder(bt->rchild); //递归调用遍历右子树
visit(bt); //访问根节点
}
}
void layertravel(BiT bt) //层次遍历二叉树
{
if (bt == NULL)
return;
Queue<BiT> q(MAX); //建立队列
q.enQueue(bt); //根节点入队
while (!q.empty())
{
q.dlQueue(bt); //根节点出队
visit(bt); //访问根节点
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(); //建立新的二叉树结点
bt->data = ch;
bt->lchild = crtPreBT(); //递归建立左子树
bt->rchild = crtPreBT(); //递归建立右子树
return bt;
}
BiT crtPreMidBT(char *pr, int &i, char *mi, int u, int v) //先序及中序递归遍历结点访问序列建立二叉树算法
{
BiT bt;
int k;
if (u > v)
return NULL;
bt = new BiTNode();
bt->data = pr[i++]; //pr[i]为子树根节点
for (k = u; k <= v; k++) //mi[u...v]为子树中序序列
{
if (mi[k] == bt->data) //查找根节点在中序序列中的位置
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) //计算二叉树的总结点数
{
int nl, nr;
if (!bt)
return 0;
nl = nodeNum(bt->lchild); //递归计算左子树的结点数
nr = nodeNum(bt->rchild); //递归计算右子树的结点数
return nl + nr + 1; //返回整个二叉树的结点数(左、右子树结点数之和加一)
}
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 << "二叉树的总结点数是: " << num << endl;
cout << "先序遍历结点访问次序: " << endl;
preorder(bt);
cout << endl;
cout << "中序遍历结点访问次序: " << endl;
midorder(bt);
cout << endl;
cout << "后序遍历结点访问次序: " << endl;
lasorder(bt);
cout << endl;
cout << "层次遍历结点访问次序: " << endl;
layertravel(bt);
cout << endl;
return 0;
}
示例
（1）程序输入：
先序序列：abc##de#g##f###
程序输出：
二叉树的高度是：5
二叉树的总结点数是：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
二叉树的总结点数是：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
二叉树的总结点数是：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
二叉树的总结点数是：0
