#include<stdio.h>#include"string.h"#include<stdlib.h>?typedef struct node #define Max 100{ ???int data;struct node *lchild,*rchild;}BinTNode; //自定義二叉樹的結(jié)點類型typedef BinTNode *BinTree; //定義二叉樹的指針int NodeNum,leaf; //NodeNum為結(jié)點數(shù)，leaf為葉子數(shù)//==========基于先序遍歷算法創(chuàng)建二叉樹==============//=====要求輸入先序序列，其中加入虛結(jié)點"#"以示空指針的位置==========BinTree CreatBinTree(void){BinTree T;int ch;if((ch=getchar())=='#')return(NULL); //讀入#，返回空指針else{ T=(BinTNode *)malloc(sizeof(BinTNode)); //生成結(jié)點T->data=ch;T->lchild=CreatBinTree(); //構(gòu)造左子樹T->rchild=CreatBinTree(); //構(gòu)造右子樹return(T);}}//========NLR 先序遍歷=============void Preorder(BinTree T){if(T) {printf("%c",T->data); //訪問結(jié)點Preorder(T->lchild); //先序遍歷左子樹Preorder(T->rchild); //先序遍歷右子樹}}//========LNR 中序遍歷===============?void Inorder(BinTree T)?{if(T){Inorder(T->lchild);printf("%c",T->data);Inorder(T->rchild);}}//==========LRN 后序遍歷============void Postorder(BinTree T){if(T){Postorder(T->lchild);Postorder(T->rchild);printf("%c",T->data);}}?//=====采用后序遍歷求二叉樹的深度、結(jié)點數(shù)及葉子數(shù)的遞歸算法========?int hl,hr,max;TreeDepth(BinTree T)?{if(T){hl=TreeDepth(T->lchild); //求左深度hr=TreeDepth(T->rchild); //求右深度max=hl>hr? hl:hr; //取左右深度的最大值?NodeNum=NodeNum+1; //求結(jié)點數(shù)if(hl==0&&hr==0) leaf=leaf+1; //若左右深度為0，即為葉子。return(max+1);}else return(0);}?//====利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹==========void Levelorder(BinTree T){int front=0,rear=1;BinTNode *cq[Max],*p; //定義結(jié)點的指針數(shù)組cqcq[1]=T; //根入隊while(front!=rear) {front=(front+1)%NodeNum;p=cq[front]; //出隊printf("%c",p->data); //出隊，輸出結(jié)點的值if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild; //左子樹入隊}if(p->rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->rchild; //右子樹入隊}}}?//==========主函數(shù)=================?void main(){BinTree root;int i,depth;printf("\n");printf("Creat Bin_Tree； Input preorder:"); //輸入完全二叉樹的先序序列，// 用#代表虛結(jié)點，如ABD###CE##F##root=CreatBinTree(); //創(chuàng)建二叉樹，返回根結(jié)點do { //從菜單中選擇遍歷方式，輸入序號。printf("\t********** select ************\n");printf("\t1: Preorder Traversal\n"); printf("\t2: Iorder Traversal\n");printf("\t3: Postorder traversal\n");printf("\t4: PostTreeDepth,Node number,Leaf number\n");printf("\t5: Level Depth\n"); //按層次遍歷之前，先選擇4，求出該樹的結(jié)點數(shù)。printf("\t0: Exit\n");printf("\t*******************************\n");scanf("%d",&i); //輸入菜單序號（0-5）switch (i){case 1: printf("Print Bin_tree Preorder: ");Preorder(root); //先序遍歷break;case 2: printf("Print Bin_Tree Inorder: ");Inorder(root); //中序遍歷break;case 3: printf("Print Bin_Tree Postorder: ");Postorder(root); //后序遍歷break;case 4: depth=TreeDepth(root); //求樹的深度及葉子數(shù)printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);printf(" BinTree Leaf number=%d",leaf);break;case 5: printf("LevePrint Bin_Tree: ");Levelorder(root); //按層次遍歷break;default: exit(1);}printf("\n");} while(i!=0);}