说明：需要分别输入要二叉树的前序序列和中序序列才能构建二叉树。如果构建失败，程序会报错。
比如我们给定一个二叉树，容易知道
前序序列为：GDAFEMHZ
中序序列为：ADEFGHMZ
程序运行结果：
源代码
#include<stdio.h>#include<stdlib.h>#include<string>#include<math.h>#include<queue>#define TURE 1#define ERROR 0#define N 100using namespace std;typedef int Status;typedef char ElemType;/*定义二叉树的存储类型*/typedef struct BitNode{ElemType data;//结点元素struct BitNode* lchild; // 左孩子指针struct BitNode* rchild; //右孩子指针} BitNode,*BiTree;void InitBiTree(BiTree* T){*T = NULL;}void ClearBiTree(BiTree* T){ //清空二叉树if(*T){if((*T)->lchild)ClearBiTree(&((*T)->lchild));if((*T)->rchild)ClearBiTree(&((*T)->rchild));free(*T);*T=NULL;}}Status BiTreeEmpty(BiTree T){return T==NULL?TURE:ERROR;}//由前序序列和中序序列建立二叉树的过程/* 算法1、通过先序遍历找到根结点A，再通过A在中序遍历的位置找出左子树，右子树2、在A的左子树中，找左子树的根结点（在先序中找），重新开始步骤13、在A的右子树中，找右子树的根结点（在先序中找），重新开始步骤1*///根据先序遍历和中序遍历创建二叉树BiTree createBiTree(char *pre, char *in, int n)//pre存放前序序列，in存放中序序列，n为序列的长度{int i=0;int n1=0,n2=0;int m1=0,m2=0;BiTree node = NULL;char lchild_pre[N],rchild_pre[N] ;//lchild_pre[N] 存放前序序列中的左子树；rchild_pre[N]存放前序序列中的右子树char lchild_in[N],rchild_in[N]; //lchild_in[N]存放中序序列中的左子树；rchild_in[N]存放中序序列中的右子树if(n==0){return NULL;}node = (BiTree)malloc(sizeof(BitNode));if(node==NULL){return NULL;}node->data = pre[0]; //前序序列的第一个元素一定是根节点for(i=0; i<n; i++){//求前序序列中的左子树和右子树if((i<=n1)&&(in[i]!=pre[0])){lchild_in[n1++]=in[i];}else if(in[i]!=pre[0]){rchild_in[n2++] = in[i];}}for(i=1; i<n; i++){//求中序序列中的左子树和右子树if(i<(n1+1)){lchild_pre[m1++]=pre[i];}else{rchild_pre[m2++]=pre[i];}}//使用递归，分别插入左子树和右子树node->lchild =createBiTree(lchild_pre,lchild_in,n1);node->rchild =createBiTree(rchild_pre,rchild_in,n2);return node;}int HeightOfBiTree(BiTree root){ //求二叉树的高度int treeHeight = 0;if (root != NULL){int leftHeight = HeightOfBiTree(root->lchild);int rightHeight = HeightOfBiTree(root->rchild);treeHeight = (leftHeight >= rightHeight)? (leftHeight + 1):(rightHeight + 1);}return treeHeight;}int WidthOfBiTree(BiTree root){ //求二叉树的宽度if(root==NULL){return 0;}int width = 0;int maxWidth = 0;queue<BiTree > Q;BiTree p = NULL;Q.push(root);while(!Q.empty()){width = Q.size();if(maxWidth < width){maxWidth = width;}for(int i=0; i<width; i++){p = Q.front();Q.pop();if(p->lchild){Q.push(p->lchild);}if(p->rchild){Q.push(p->rchild);}}}return maxWidth;}int NodeCount(BiTree root){ //求二叉树的结点数量if(root==NULL)return 0;elsereturn NodeCount(root->lchild)+NodeCount(root->rchild)+1;}int LeafNodeCount(BiTree root){//求二叉树的叶子结点个数if(root==NULL)return 0;if(root->lchild==NULL&&root->rchild==NULL)return 1;return LeafNodeCount(root->lchild)+LeafNodeCount(root->rchild);}void preOrder(BiTree root){ //二叉树的前序遍历if (root==NULL){return;}printf("%c ",root->data);preOrder(root->lchild);preOrder(root->rchild);}void inOrder(BiTree root){ //二叉树的中序遍历if (root==NULL){return;}inOrder(root->lchild);printf("%c ",root->data);inOrder(root->rchild);}void PostOrder(BiTree root){ //后序遍历if (root==NULL){return;}PostOrder(root->lchild);PostOrder(root->rchild);printf("%c ",root->data);}int main(){char preNode[N];char inNode[N];int n = 0;char ch;BitNode* root=NULL;printf("请输入二叉树的先序序列\n");while((ch = getchar())&&ch!='\n')preNode[n++] = ch;printf("请输入二叉树的中序序列\n");n = 0;while((ch = getchar())&&ch!='\n')inNode[n++] = ch;root = createBiTree(preNode,inNode,n);printf("二叉树创建成功\n");printf("先序序列\n");preOrder(root);printf("\n中序序列\n");inOrder(root);printf("\n后序序列\n");PostOrder(root);printf("\n");int height =HeightOfBiTree(root);printf("\n二叉树的高度为：%d\n",height);int width =WidthOfBiTree(root);printf("\n二叉树的宽度为：%d\n",width);int Node =NodeCount(root);printf("\n二叉树的结点数量为：%d\n",Node);int leaf =LeafNodeCount(root);printf("\n二叉树的叶子结点为：%d\n",leaf);system("pause");return 0;}
