#include#include #include #include typedef char DataType;int depth=0;int h1=1;int nlayer=1;char ch2;typedef struct node{ DataType data;//节点数据元素 struct node *lchild;//指向左孩子 struct node *rchild;//指向右孩子}BinTNode,*BinTree;void GetPreOrder(char *last,char *mid,BinTree &T,int len){//利用后序和中序建立二叉树 if(len==0) { T = NULL; return; } //取出后序序列中的最后一个节点 char ch=last[len-1]; int index=0; //在中序序列中进行查找根节点，并用index记录其在序列中的索引 while(mid[index]!=ch) { index++; } T=(BinTree)malloc(sizeof(BinTNode)); //给根节点分配空间 T->data=mid[index]; GetPreOrder(last,mid,T->lchild,index);//建立左子树 GetPreOrder(last+index,mid+index+1,T->rchild,len-index-1);//建立右子树}void GetPostOrder(char *prim,char *mid,BinTree &T,int len){//利用先序和中序建立二叉树 if(len==0) { T=NULL; return; } char ch=prim[0];//提出先序序列中的第一个节点 int index=0; while(mid[index]!=ch) {//在中序序列中查找当前根节点。并用index记录其在序列中的位置 index++; } //给根节点分配空间 T=(BinTree)malloc(sizeof(BinTNode)); T->data=mid[index]; GetPostOrder(prim+1,mid,T->lchild,index); //建立左子树 GetPostOrder(prim+index+1,mid+index+1,T->rchild,len-index-1);//建立右子树}void createB(BinTree &T){//扩展先序遍历创建二叉链表 DataType ch; scanf("%c",&ch); if(ch=='.') T=NULL; else { T=(BinTNode *)malloc(sizeof(BinTNode)); T->data=ch; createB(T->lchild); createB(T->rchild); }}void gradeBT(BinTree &T,DataType ch,int d,int *n){/*求ch结点所在层数*/ if (T) { d++; if(T->data==ch) *n=d; gradeBT(T->lchild,ch,d,n); gradeBT(T->rchild,ch,d,n); }}void countdef(BinTree T,int &n){ /*统计叶子结点数*/ if(T!=NULL) { if(T->lchild==NULL&&T->rchild==NULL) n++; countdef(T->lchild,n); countdef(T->rchild,n); }}int depthhou(BinTree bt){//后序遍历求二叉树的高度 int hl,hr,max; if(bt!=NULL) { hl=depthhou(bt->lchild); hr=depthhou(bt->rchild); max=hl>hr?
hl:hr; return (max+1); } else return 0; } void depthxian(BinTree bt,int h1) {//先序遍历求二叉树高度 if(bt!=NULL) { if(h1>depth) depth=h1; depthxian(bt->lchild,h1+1); depthxian(bt->rchild,h1+1); } } void PrintTree(BinTree bt,int nlayer) {//树状打印二叉树 if(bt==NULL) return; PrintTree(bt->rchild,nlayer+1); for(int i=0;i<nlayer;i++) printf(" "); printf("%c\n",bt->data); PrintTree(bt->lchild,nlayer+1); } void Inorderxian(BinTree &T) {//先序输出二叉树 if(T!=NULL) { printf("%3c",T->data); Inorderxian(T->lchild); Inorderxian(T->rchild); } } void Inorderzhong(BinTree &T) {//中序输出二叉树 if(T!=NULL) { Inorderzhong(T->lchild); printf("%3c",T->data); Inorderzhong(T->rchild); } } void Inorderhou(BinTree &T) {//后序输出二叉树 if(T!=NULL) { Inorderhou(T->lchild); Inorderhou(T->rchild); printf("%3c",T->data); } } void main() { DataType ch; BinTree root; BinTree T=NULL; BinTree BT=NULL; int d=0,h=0,l=1,n=0; int x,count2=0,count3=0; DataType first[26],mid[26],last[26]; root=(BinTNode *)malloc(sizeof(BinTNode)); printf("*****************************************************************\n"); printf("* 1、扩展先序遍历创建二叉树 2、统计二叉树叶子结点数 *\n"); printf("* 3、先序遍历求二叉树高度 4、后序遍历求二叉树高度 *\n"); printf("* 5、按树状打印二叉树 7、利用先序和中序创建二叉树 *\n"); printf("* 8、利用后序和中序创建二叉树 9、先序输出二叉树 *\n"); printf("* 10、中序输出二叉树 11、后序输出二叉树 *\n"); printf("*****************************************************************\n"); printf("请输入你的选择：\n"); //第一种方法创建二叉树 printf("请依照先序遍历的顺序输入须要中序遍历的字符:\n"); createB(root); printf("先序遍历输入二叉树例如以下:"); Inorderxian(root); printf("\n"); printf("中序遍历输入二叉树例如以下:"); Inorderzhong(root); printf("\n"); printf("后序遍历输入二叉树例如以下:"); Inorderhou(root); printf("\n\n"); printf("统计二叉树叶子数:"); countdef(root,n); printf("count=%d\n",n); printf("先序遍历输出二叉树的高度:"); depthxian(root,h1); printf("depthxain=%d\n",depth); printf("后序遍历输出二叉树的高度:"); printf("depthhou=%d\n",depthhou(root)); printf("打印输出二叉树的树状结构:\n"); PrintTree(root,1); //另外一种方法创建二叉树 printf("请输入先序和中序序列：\n"); scanf("%s%s",first,mid); GetPostOrder(first,mid,T, strlen(first)); printf("打印输出二叉树的树状结构:\n"); PrintTree(root,1); printf("先序遍历输入二叉树例如以下："); Inorderxian(T); printf("\n"); printf("中序遍历输入二叉树例如以下："); Inorderzhong(T); printf("\n"); printf("后序遍历输入二叉树例如以下："); Inorderhou(T); printf("\n"); printf("统计二叉树叶子数:"); countdef(T,count2); printf("count2=%d\n",count2); printf("先序遍历输出二叉树的高度:"); depthxian(T,h1); printf("depthxain=%d\n",depth); printf("后序遍历输出二叉树的高度:"); printf("depthhou=%d\n",depthhou(T)); //第三种方法创建二叉树 printf("请输入后序和中序序列：\n"); scanf("%s%s",last,mid); GetPreOrder(last,mid,BT,strlen(last)); printf("打印输出二叉树的树状结构:\n"); PrintTree(BT,1); printf("先序遍历输入二叉树例如以下："); Inorderxian(BT); printf("\n"); printf("中序遍历输入二叉树例如以下："); Inorderzhong(BT); printf("\n"); printf("后序遍历输入二叉树例如以下："); Inorderhou(BT); printf("\n"); printf("统计二叉树叶子数:"); countdef(BT,count3); printf("count3=%d\n",count3); printf("先序遍历输出二叉树的高度:"); depthxian(BT,h1); printf("depthxain=%d\n",depth); printf("后序遍历输出二叉树的高度:"); printf("depthhou=%d\n",depthhou(BT)); printf("\n"); printf("\n"); }