本文实现了二叉树了存储实现，起先决定和队列与栈一样，设计一个二叉树节点的类型class treeNode，再构建一个二叉树类处理节点的生成，遍历等，结果在做二叉树创建函数CreateBitTree时遇到了很多问题，最后才发现直接构建一个二叉树类型就可以了。
这里主要介绍利用先序序列和中序序列重构一个二叉树的函数
#include<iostream>#include<math.h>using namespace std;class BitTree{ char *data; BitTree *lchild, *rchild; void preorder(BitTree *&T); //先序遍历调用函数 void inorder(BitTree *&T); //中序遍历调用函数 void postorder(BitTree *&T); //后序遍历调用函数public: void CreateBitTree(BitTree *&T);//二叉树创建函数 void PreOrder(BitTree *&T) //先序遍历 { cout<<"先序遍历输出序列如下："<<endl; preorder(T); cout<<endl; } void InOrder(BitTree *&T) //中序遍历 { cout<<"中序遍历输出序列如下："<<endl; inorder(T); cout<<endl; } void PostOrder(BitTree *&T)//后序遍历 { cout<<"后序遍历输出序列如下："<<endl; postorder(T); cout<<endl; } void CrtBt(BitTree *&T,char **&pre,char **&ino,int pe,int is,int n,int length);//利用先序中序序列重构二叉树};void BitTree::CreateBitTree(BitTree *&T)//二叉树创建函数定义{ char *ch=new char(10); cout<<"请输入当前节点字符:"<<endl; cin>>ch; if(*ch=='#') //定义如果输入为‘#’时表示没有该节点 T=NULL; else { if(!(T=new BitTree)) { cout<<"overflow"<<endl; return; } T->data=new char(strlen(ch)+1); strcpy(T->data,ch); cout<<"初始化 "<<T->data<<"的左节点:"; CreateBitTree(T->lchild); //构建T节点的左子树 cout<<"初始化 "<<T->data<<"的右节点:"; CreateBitTree(T->rchild); //构建T节点的右子树 }}void BitTree::preorder(BitTree *&T)//先序遍历{ if(T!=NULL) //当前节点存在的话先输出当前节点的内容，在遍历其左右子树节点 { cout<<T->data<<" "; preorder(T->lchild); preorder(T->rchild); }}void BitTree::inorder(BitTree *&T)//中序遍历{ if(T!=NULL) //当前节点存在，先遍历其左子树节点，然后输出当前节点内容，再遍历右子树节点 { inorder(T->lchild); cout<<T->data<<" "; inorder(T->rchild); }}void BitTree::postorder(BitTree *&T)//后序遍历{ if(T!=NULL) //当前节点存在，先遍历其左子树节点，然后输出当前节点内容，再遍历右子树节点 { postorder(T->lchild); postorder(T->rchild); cout<<T->data<<" "; }}int search(char *ino[],char *ps,int n)//字符查询函数，查找ino字符串中是否有与ps一致{ int point=0; while(strcmp(*(ino+point),ps)!=0&&point<n) { point++; } if(point<n) return point; else return -1;}void BitTree::CrtBt(BitTree *&T,char **&pre,char **&ino,int ps,int is,int n,int length){ /*已知pre[ps+n-1]是该二叉树的先序序列， ino[is+n-1]是二叉树的中序序列 本算法由此两个序列重构二叉树 核心思想：利用先序序列确定树根，然后用中序序列划分左右子树， 并在左右子树不断重复以上步骤，知道所有序列都分配完 */ if(n==0) T=NULL; else { int k=search(ino,*(pre+ps),length); //查询先序的某个节点在中序序列的位置 if(k==-1) T=NULL; else { if(!(T=new BitTree)) { cout<<"overflow"<<endl; return; } T->data=new char(strlen(*(pre+ps))+1); strcpy(T->data,*(pre+ps)); if(k==is) T->lchild=NULL; else CrtBt(T->lchild,pre,ino,ps+1,is,k-is,length);//构建左子树 if(k==is+n-1) T->rchild=NULL; else CrtBt(T->rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1,length);//构建右子树 } }}void main(){ int n=7; char **pre; char **ino; pre=new char*[7]; ino=new char*[7]; cout<<"input pre"<<endl; for(int i=0;i<n;i++) { pre[i]=new char(1); cin>>pre[i]; } cout<<"input ino"<<endl; for(int i=0;i<n;i++) { ino[i]=new char(1); cin>>ino[i]; } BitTree *T; T->CrtBt(T,pre,ino,0,0,n,n); T->PostOrder(T); T->PreOrder(T); T->InOrder(T);}