题目要求

编写程序，用先序递归遍历法（或输入先序及中序递归遍历结点访问序列）建立二叉树的二叉链表存储结构，计算并输出二叉树的结点总数以及树的高度；然后输出其先序、中序、后序以及层次遍历结点访问次序。其中层次遍历的实现需使用循环队列。二叉树结点数据类型建议选用字符类型。

数据结构设计

采用 C ++ 的模板类，创建队列。每个队列对象中，elem 指针用来建立长度为 n 的数组，n 表示队列的容量，front 表示队头指针，rear 表示队尾指针，c 表示队列中当前元素的个数。
采用结构体建立二叉树，其中，data 表示数据域，lchild 表示左指针，rchild 表示右指针，BiT 表示二叉树结构体指针类型变量，BiTNode 表示二叉树结构体类型变量。

算法设计简要描述

1. 先序遍历建立二叉树：递归调用函数，不断读取字符，依次建立左子树和右子树，当读取到‘#’字符时，返回 NULL 指针，最终返回根结点指针。
2. 先序和中序遍历结点访问序列建立二叉树：
   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