树之二叉树

       本文来介绍二叉树。二叉树是树形结构的一个重要类型，其重要性不言而喻，我们还会在后面经常应用到二叉树。比如说树、森林二叉树之间可相互转换，对树和森林的操作可对应为对相应二叉树的操作。

       本文介绍的二叉树具有链式存储结构，其存储结构为二叉链表（当然也有三叉链表的存储结构）。本文介绍了二叉树的各种遍历与二叉树的一些其他操作。

       二叉树的遍历操作是二叉树其他操作的基础。不同的遍历并非重复，而是具有实际的意义，即不同的问题会应用不同的遍历操作。比如说判断俩个二叉树是否相等，用先序遍历比较好；删除一个二叉树，用后序遍历比较好等等。

#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
using namespace std;

typedef char Datatype;          //数据域中数据的类型
typedef struct node{            //结点类型
    Datatype data;              //数据域
    struct node *lchild,*rchild;//左右孩子指针
}BinTNode;
typedef BinTNode *BinTree;      //BinTree为指向BinTNode类型结点的指针类型

//***********************二叉树的遍历************************

void PreOrder(BinTree T){
    //先序遍历递归算法
    if(T){
        printf("%c",T->data);//先访问根节点
        PreOrder(T->lchild); //再访问左子树
        PreOrder(T->rchild); //最后访问右子树
    }
}

void InOrder(BinTree T){
    //中序遍历递归算法
    if(T){                   // 如果二叉树非空
        InOrder(T->lchild);  //先访问左子树
        printf("%c",T->data);//再访问根结点
        InOrder(T->rchild);  //最后访问右子树
    }
}

void PostOrder(BinTree T){
    //后序遍历递归算法
    if(T){
        PostOrder(T->lchild);//先访问左子树
        PostOrder(T->rchild);//再访问右子树
        printf("%c",T->data);//最后访问根结点
    }
}

void LevelOrder(BinTree T){
    //层次遍历算法,按照从左到右,从上到下的顺序遍历二叉树
    BinTNode *p=T;            //工作指针初始化为根指针
    queue<BinTNode*>q;        //队列中元素的类型是指向根节点的指针
    while(p){                 //当队列中的元素不是空指针时进入循环
        printf("%c",p->data); //访问当前结点的数据域
        if(p->lchild)         //如果左子树不为空,则将左指针进队列
            q.push(p->lchild);
        if(p->rchild)         //如果右子树不空,则将右指针进队列
            q.push(p->rchild);
        if(q.empty())         //如果队列为空,则退出循环
            break;
        p=q.front();          //取队头元素
        q.pop();              //弹出队头元素
    }
}

void InOrder1(BinTree T){
    //中序遍历二叉树的非递归算法
    stack<BinTNode*>s;       //栈的元素时指向树结点的指针
    BinTNode *p=T;           //活动指针初始化为根指针
    while(p||!s.empty()){    //进入循环的条件:要么子树不空,要么栈不空
        if(p){               //根指针进栈,遍历左子树
            s.push(p);
            p=p->lchild;
        }
        else{                //根指针退栈,访问根节点,遍历右子树
            p=s.top();
            s.pop();
            printf("%c",p->data);
            p=p->rchild;
        }
    }
}

//***************二叉树的一些其他操作******************

void CreateBinTree(BinTree *T){
    //二叉链表的构造
    //基于先序遍历的构造,先序序列中虚结点表示空指针的位置
    //T是指向根指针的指针，故修改*T就修改了实参(根指针)本身
    char ch;
    ch=getchar();
    if(ch==' ')
        *T=NULL;//读入空格，将相应指针置空
    else{
        *T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点
        (*T)->data=ch;//给结点的数据域赋值
        CreateBinTree(&(*T)->lchild);//构造左子树
        CreateBinTree(&(*T)->rchild);//构造右子树
    }
}

//***********************测试函数************************

int main(){
    BinTree T;
    printf("输入字符串（空格字符表示空树），来建立二叉树！\n");
    CreateBinTree(&T);
    printf("二叉树已经建好，先序遍历序列为：\n");
    PreOrder(T);
    printf("\n中序遍历序列为(递归)：\n");
    InOrder(T);
    printf("\n中序遍历序列为(非递归)：\n");
    InOrder1(T);
    printf("\n后序遍历序列为：\n");
    PostOrder(T);
    printf("\n层次遍历序列为：\n");
    LevelOrder(T);
    return 0;
}
           

在下图中的测试样例中，建立上图所示二叉树，其输入的先序序列是：ABD∮∮∮CE∮∮F∮∮，其中∮表示空树，那么如图所示的二叉树的先序遍历序列为：A B D C E F，中序遍历序列为：D B A E C F，后序遍历序列为：D B E F C A。

测试样例：