二叉樹的基本操作及應用（三）

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
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"); }