[数据结构与算法]二叉树的链式存储表示，创建、遍历等算法，数据结构，C++

1. 二叉树的链式存储表示。

2. 二叉树的创建、遍历等算法。

【基本要求】

1. 创建二叉树的链式存储表示。由二叉树的先序序列和中序序列创建二叉树；

2. 按树状打印二叉树。例如：假设每个结点所含数据元素均的单个字母，左下图二叉树印为右下形状。

?

3. 统计二叉树的叶子结点个数。

4. 给出二叉树的后序和层次序。

5. 输出二叉树中从根结点到所有叶子结点的路径。

?

【测试数据】

1. 先序序列：EBADCFHGIKJ，中序序列：ABCDEFGHIJK

2. 先序序列：ABDFCEGH，中序序列：BFDAGEHC

3. 先序序列：ABDEHCFIMGJKL，中序序列DBHEAIMFCGKLJ

• 需求分析：包含题目要求，程序功能，运行方式，测试数据等

题目要求能够创建二叉树的链式存储表示，并由二叉树的先序序列和中序序列创建二叉树，需要创建BitNode结构体，char型的data数据，由主函数中输入相应的序列，由两个序列创建二叉树。

typedef struct BiTNode {

??? char data;

??? struct BiTNode *Lchild, *Rchild; //左右孩子指针

} BiTNode, *BiTree;

按树状打印二叉树：要根据二叉树的深度和元素个数来决定相应的打印方法，设置深度n，从深度0开始答应，用递归去打印树，由例图可知要先打印右子树，并设置相应的换行和制表符来作为空格。相当于R-T-L打印，按中序序列的逆序列打印树图。

????? 二叉树的叶子结点个数：设置static静态计数n，当没有左孩子也没有右孩子时即为叶子结点，计数+1，再递归遍历左右孩子，返回n，n即为叶子结点。

????? 层次序和后序要按树的相应特点去计算给出，同时要用到队列和容器。

typedef struct {

??? BiTree? *base;? // 动态分配存储空间

??? int? front;??? // 头指针，若队列不空，指向队列头元素

? ??int? rear;???? // 尾指针，若队列不空，指向队列尾元素的下一个位置

} SqQueue;

出二叉树中从根结点到所有叶子结点的路径需要用到容器或者栈，将存入容器或栈的元素当到达叶子结点时输出容器中的内容。

• 概要设计：包含抽象数据类型定义，程序模块等

第一个模块定义BitNode结构体，和顺序队列SqQueue相应的内容，数据，左右孩子指针，头尾指针，创建需要用到的函数，InitQueue构造一个空队列Q；EmptyQueue判断队列是否空；GetHead返回队列Q的队头元素，不修改队头指针；EnQueue插入元素e为Q的新的队尾元素；DeQueue若队列不空，则删除Q的队头元素，否则退出程序报错。相应的需要用到的基本算法，再用这些算法去实现题目所要求的遍历算法和统计结点，路径。

程序的主函数模块用于输入树的相关信息，并运行相应的算法函数。输出正确的题目所要求的结果。定义序列为string方便输入序列，同时方便用length函数去获得序列长度（结点个数）。

而函数定义模块用来定义相应的算法：printBiTree打印树，countLeaf计算叶子结点，LevelOrderTraverse用于输出二叉树层次序列，AllPath用于输出跟到叶子结点的路径。CrtBT即是题目要求的由二叉树的先序序列和中序序列创建二叉树。用PostOrderTraverse输出二叉树的后序序列。

• 详细设计：抽象数据类型以及程序模块的具体实现，算法设计思想

二叉树的先序序列和中序序列创建二叉树:设置pre[ps..ps+n-1]为二叉树的先序序列，in[is..is+n-1]为二叉树的中序序列，n为结点个数，需要先由search函数在中序序列中查询根，当中序序列中元素等于先序序列的第一个时，即返回树根，否则返回-1。树根等于is代表该左子树已递归完成，否则继续递归左子树（ps+1，中序首元素下标即为is，结点个数由k减is），树根等于is+n-1代表该右子树已递归完成，否则继续递归右子树（ps+1，右子树先序首元素下标等于ps+1减去k-is，中序直接加一，结点个数同理）。

按树状打印二叉树: 设置n标志深度，从深度0开始打印，用递归去打印树，由图知需要按R-T-L顺序去打印树，即先打印右子树，递归，深度加一，换行按深度打印制表符，打印数据，同理，再打印左子树。

????? 统计二叉树的叶子结点个数：设置静态的int static n做计数数据，当没有左孩子也没有右孩子即为叶子结点，计数+1，否则即是按递归遍历左右子树，最后返回n，即是叶子结点个数。

给出二叉树的后序和层次序：后序遍历较为容易，L-R-T即是先递归遍历左子树，再递归遍历右子树，再输出结点数据。而层次序遍历要用到队列和相关函数，设置一个顺序队列，初始化队列后，根结点入队，队列非空即代表该层次未遍历完成，访问结点，左右子树入队，出队。完成层次遍历，并输出相应结果层次序列。

输出二叉树中从根结点到所有叶子结点的路径：要使用容器或栈去输出结果，这里使用容器较为便利，先将结点数据压入容器，当到达叶子结点时，代表已经无左右孩子，就输出容器中的内容，否则就递归运行该算法，递归遍历左右子树直到遇到叶子结点，输出路径。

• 调试分析：包括算法的时间复杂度和空间复杂度分析等

递归遍历二叉树，因为每个结点被访问一次，无论按什么次序遍历，对含n个结点的二叉树，时间复杂度均为O（n），辅助空间即树的深度，所以空间复杂度也为O（n）。

按树状打印二叉树同理，但因为需要按深度打印制表符，所以时间复杂度为O（n2），空间复杂度为O（n）。

按先序序列，中序序列构造二叉链表表示的二叉树需要递归遍历子树，还要用search函数去求中序序列中查询根，所以时间复杂度为O（n2），有两个序列的辅助空间，所以空间复杂度也为O（n2）。

统计叶子结点个数的算法较为简单，只使用了递归遍历，对含n个结点的二叉树，时间复杂度均为O（n），辅助空间即树的深度，所以空间复杂度也为O（n）。

层次遍历二叉树，因为需要用到队列，出队和入队，同时需要递归遍历左右子树，辅助空间较多，同时用到队列空间和树BitNode空间，空间复杂度为O（n2），时间复杂度为O（n）。

输出根结点到所有叶子结点的路径中，要用到栈或容器，同时要定义迭代器，输出容器中的内容，加上需要递归子树，所以时间复杂度为O（n2），空间复杂度也为空间复杂度为O（n2）。

调试数据的时候，没有正确打印二叉树，经过调试发现是没有按深度去换行，加上换行符之后正确换行，打印的树才正确。

在层次遍历二叉树时，没有正确的递归子树，递归了传入算法的树，让其入队，相当于重复入队其首结点并输出，导致层次序列一直输出首结点直到队列满，后来发现是需要在递归函数的参数中传入队头的子树，才能正确递归左右子树，这样才正确入队和出队，达到目的。

创建二叉树时，没有在else if递归里传入正确参数，导致树的创建错误，应该按照中序序列和先序序列的规律正确计算，is，in的值，并传入正确的参数去递归算法，计算正确首元素下标和得到子序列的树根，才能在二叉链表中正确创建树。

计算叶子结点时定义n是全局变量，封装性不够好，在递归时最好定义静态static的数据，这样保证了数据的封装性也保证了输出能够正确，同时不破坏程序的模块化。

• 头文件及源程序

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

#define MAXQSIZE  100  //最大队列长度

typedef struct BiTNode {
    char data;
    struct BiTNode *Lchild, *Rchild; //左右孩子指针
} BiTNode, *BiTree;

typedef struct {
    BiTree  *base;  // 动态分配存储空间
    int  front;    // 头指针，若队列不空，指向队列头元素
    int  rear;     // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;

void InitQueue (SqQueue &Q) {
    // 构造一个空队列Q
    Q.base = new BiTree[MAXQSIZE];
    if(!Q.base) exit(0);             // 存储分配失败
    Q.front = Q.rear = 0;
}

bool EmptyQueue(SqQueue Q){//判断队列是否空
    return Q.front == Q.rear;
}

BiTree GetHead(SqQueue Q) {
    //返回队列Q的队头元素，不修改队头指针
    if ( Q.front != Q.rear )
        return Q.base[Q.front];
    else
        return 0;
}

void EnQueue(SqQueue&Q,BiTree e) {
    // 插入元素e为Q的新的队尾元素
    if((Q.rear+1) %MAXQSIZE ==Q.front){
        cout<<"队列满";
        exit(0); //队列满
    }
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1) % MAXQSIZE;
}

void DeQueue (SqQueue&Q) {
    //若队列不空，则删除Q的队头元素，
    //否则退出程序报错
    if (Q.front==Q.rear)  exit(0);
    Q.front = (Q.front+1) % MAXQSIZE;
}

void PostOrderTraverse(BiTree BT) {
    // 后序遍历二叉树
    if (BT) {
        PostOrderTraverse(BT->Lchild); // 递归遍历左子树
        PostOrderTraverse(BT->Rchild); // 递归遍历右子树
        cout<<BT->data;                // 访问结点
    }
}

int Search(string in,char root){
    int n = 0;
    while (in[n]!=root) {//当中序序列中元素等于先序序列的第一个时，即返回树根
        if(in[n] == '\0')
            return -1;//否则返回-1
        n++;
    }
    return n;//返回树根
}

void CrtBT(BiTree &BT,string pre, string in, int ps, int is, int n) {
    //已知pre[ps..ps+n-1]为二叉树的先序序列，in[is..is+n-1]为二叉树的中序序列
    //本算法由此两个序列构造二叉链表表示的二叉树，n为结点个数
    int k;
    if (n==0) BT = NULL;
    else {
        k=Search(in, pre[ps]); // 在中序序列中查询根
        if (k==-1) BT=NULL; // 序列错误，返回空树
        else {
            BT=new BiTNode;
            BT->data = pre[ps];
            if (k==is) BT->Lchild = NULL;//树根等于is代表该左子树已递归完成，否则继续递归左子树
            else CrtBT(BT->Lchild, pre, in, ps+1, is, k-is);
            //ps+1，中序首元素下标即为is，结点个数由k减is
            if (k==is+n-1) BT->Rchild = NULL;//树根等于is+n-1代表该右子树已递归完成，否则继续递归右子树
            else  CrtBT(BT->Rchild, pre, in, ps+1+(k-is), k+1, n-(k-is)-1);
            //ps+1，右子树先序首元素下标等于ps+1减去k-is，中序直接加一，结点个数同理
        }

    } //if

} // CrtBT

void printBiTree(BiTree BT,int n){
    //n标志深度，从深度0开始打印，用递归去打印树
    if(BT){
        if(BT->Rchild){//先打印右子树
            printBiTree(BT->Rchild,n+1);//递归，深度加一，换行
            cout<<endl;
        }
        for(int i = 0;i<n;i++){
            cout<<"\t";//按深度打印制表符
        }
        cout<<BT->data;//打印数据
        cout<<endl;
        if(BT->Lchild){//同理，再打印左子树
            printBiTree(BT->Lchild,n+1);
            cout<<endl;
        }
    }
}

int countLeaf(BiTree BT){
    int static n = 0;
    if(BT){
        if((!BT->Lchild)&&(!BT->Rchild))
            n++;//没有左孩子也没有右孩子即为叶子结点，计数+1
        countLeaf(BT->Lchild);//递归遍历左孩子
        countLeaf(BT->Rchild);//递归遍历右孩子
    }
    return n;
}

void LevelOrderTraverse(BiTree T) {
    //层次遍历二叉树，输出二叉树层次序列
    SqQueue Q;
    InitQueue(Q);
    if(T==NULL) return;
    BiTree p = T;
    EnQueue(Q,p); // 根结点入队
    while(!EmptyQueue(Q) ) {
        cout<<GetHead(Q)->data; // 访问结点
        if(GetHead(Q)->Lchild) EnQueue(Q,GetHead(Q)->Lchild); // 左子树入队
        if(GetHead(Q)->Rchild) EnQueue(Q,GetHead(Q)->Rchild); // 右子树入队
        DeQueue(Q);//出队
    }
}

void AllPath(BiTree BT,vector<char> vct) {
    if (BT) {
        vct.push_back(BT->data);//将结点数据压入容器
        if ((!BT->Lchild)&&(!BT->Rchild)){//当到达叶子结点时（无左右孩子）
            for(vector<char>::iterator iter =vct.begin();iter !=vct.end();iter++){
                //定义迭代器iter，输出容器中的内容
                cout<<*iter;
            }
            cout<<endl;
        }     
        else {
            AllPath(BT->Lchild,vct);//递归遍历左子树
            AllPath(BT->Rchild,vct);//递归遍历右子树
        }
    } // if(T)
} // AllPath

int main()
{
    BiTree BT;
    string pre,in;
    int n;
    cout<<"输入先序序列:"; cin>>pre;
    cout<<"输入中序序列:"; cin>>in;
    n = pre.length();
    CrtBT(BT,pre,in,0,0,n);
    printBiTree(BT,0);
    cout<<endl<<"叶子结点个数为:"<<countLeaf(BT);
    cout<<endl<<"后序序列为:";
    PostOrderTraverse(BT);
    cout<<endl<<"层次序列为:";
    LevelOrderTraverse(BT);
    cout<<endl<<"根结点到所有叶子结点的路径:"<<endl;
    vector<char> v;//容器创建
    AllPath(BT,v);
    return 0;
}

?测试结果：提供试验结果和数据，测试所有操作结果的正确性

?测试数据一，可见所有结果输出正确。

测试数据二，可见所有结果输出正确?

?

?