1、（ 1） 插入新結(jié)點（ 2） 前序、中序、后序遍歷二叉樹（ 3） 中序遍歷的非遞歸算法（ 4） 層次遍歷二叉樹（ 5） 在二叉樹中查找給定關(guān)鍵字( 函數(shù)返回值為成功1, 失敗 0)（ 6） 交換各結(jié)點的左右子樹（ 7） 求二叉樹的深度（ 8） 葉子結(jié)點數(shù)Input第一行：準備建樹的結(jié)點個數(shù)n第二行：輸入n 個整數(shù)，用空格分隔第三行：輸入待查找的關(guān)鍵字第四行：輸入待查找的關(guān)鍵字第五行：輸入待插入的關(guān)鍵字Output第一行：二叉樹的先序遍歷序列第二行：二叉樹的中序遍歷序列第三行：二叉樹的后序遍歷序列第四行：查找結(jié)果第五行：查找結(jié)果第六行 第八行：插入新結(jié)點后的二叉樹的先、中、序遍歷序列第九行：插入

2、新結(jié)點后的二叉樹的中序遍歷序列( 非遞歸算法 )第十行：插入新結(jié)點后的二叉樹的層次遍歷序列第十一行 第十三行：第一次交換各結(jié)點的左右子樹后的先、中、后序遍歷序列第十四行 第十六行：第二次交換各結(jié)點的左右子樹后的先、中、后序遍歷序列第十七行：二叉樹的深度第十八行：葉子結(jié)點數(shù)*/#include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int KeyType;#define S

3、TACK_INIT_SIZE 100 /#define STACKINCREMENT 10 /#define MAXQSIZE 100存儲空間初始分配量存儲空間分配增量typedef int ElemType;typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;/ BiTNode,*BiTree;左右孩子指針Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)if(!T)p=f;return FALSE;else if(key=T-data)p=T;r

4、eturn TRUE;else if(keydata)return SearchBST(T-lchild,key,T,p);else return(SearchBST(T-rchild,key,T,p);Status InsertBST(BiTree &T,ElemType e)BiTree s,p;if(!SearchBST(T,e,NULL,p)s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;else if(edata)p-lchild=s;else p-rchild=s;return T

5、RUE;else return FALSE;Status PrintElement( ElemType e ) /輸出元素e 的值printf(%d , e );return OK;/ PrintElementStatus PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) /前序遍歷二叉樹T 的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit。/ 補全代碼 , 可用多個語句if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,

6、Visit)return OK;return ERROR;else return OK; / PreOrderTraverseStatus InOrderTraverse( BiTree T, Status(*Visit)(ElemType) )/中序遍歷二叉樹T 的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit。/ 補全代碼 , 可用多個語句if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK; /

7、 InOrderTraverseStatus PostOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) /后序遍歷二叉樹T 的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit。/ 補全代碼 , 可用多個語句if(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)return OK;return ERROR;else return OK; / PostOrderTraverseStatus Putout(BiTree T

8、)PreOrderTraverse(T,PrintElement);printf(n);InOrderTraverse(T, PrintElement);printf(n);PostOrderTraverse(T,PrintElement);printf(n);return OK;/ 非遞歸算法struct SqStackBiTree *base; /BiTree *top; /int stacksize; /; /順序棧在棧構(gòu)造之前和銷毀之后，base 的值為棧頂指針當前已分配的存儲空間，以元素為單位NULLStatus InitStack(SqStack &S)=(BiTree *)mal

9、loc(STACK_INIT_SIZE*sizeof(BiTree);if(!return ERROR;=;=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,BiTree e)if(=(BiTree*)realloc,+STACKINCREMENT)*sizeof(BiTree);if(!return ERROR;=+;+=STACKINCREMENT;*+=e;return OK;Status Pop(SqStack &S,BiTree &e)if=return ERROR;e=*;return OK;Status StackEmpty(Sq

10、Stack S) /若棧 S 為空棧，則返回 TRUE，否則返回 FALSE if TRUE;else return FALSE;Status InOrderTraverse1(BiTree T,Status(*Visit)(ElemType e),SqStack S)BiTree p;InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;elsePop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/ 層次遍歷typedef structBiTree

11、*base; / int front; / int rear; /初始化的動態(tài)分配存儲空間頭指針 , 若隊列不空 , 指向隊列頭元素尾指針 , 若隊列不空 , 指向隊列尾元素的下一個位置SqQueue;Status InitQueue(SqQueue &Q)=(BiTree*)malloc(MAXQSIZE*sizeof(BiTree);if(!return ERROR;=0;return OK;int QueueLength(SqQueue Q)/ 返回 Q的元素個數(shù)/ 請補全代碼returnStatus EnQueue(SqQueue &Q,BiTree e)/ 插入元素 e 為 Q的新的

12、隊尾元素/ 請補全代碼if(+1)%MAXQSIZE=return ERROR;=e;=+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue &Q,BiTree &e)/若隊列不空 ,則刪除/請補全代碼if=return ERROR;e=;=+1)%MAXQSIZE;return OK;Q的隊頭元素,用 e 返回其值,并返回OK;否則返回ERRORStatus LevelTraverse(BiTree T,SqQueue Q)/ 層次遍歷二叉樹InitQueue(Q);BiTree p;p=T;if(T)EnQueue(Q,T);/printf(%d,Qu

13、eueLength(Q);while(QueueLength(Q)!=0)DeQueue(Q,p);/根結(jié)點出隊printf(%d ,p-data);/輸出數(shù)據(jù)if(p-lchild)EnQueue(Q,p-lchild); /if(p-rchild)EnQueue(Q,p-rchild); /左孩子進隊右孩子進隊return OK;void Change(BiTree T)BiTNode *p;if(T)p=T-lchild;T-lchild=T-rchild;T-rchild=p;Change(T-lchild);Change(T-rchild);/ return OK;int BTree

14、Depth(BiTree T)/ 求由 BT 指針指向的一棵二叉樹的深度/ int dep1,dep2; if(T!=NULL)/ 計算左子樹的深度int dep1=BTreeDepth(T-lchild);/ 計算右子樹的深度int dep2=BTreeDepth(T-rchild);/ 返回樹的深度 if(dep1dep2) return dep1+1; elsereturn dep2+1;else return 0;/葉子結(jié)點數(shù)Status yezhi(BiTree T,SqQueue Q)int i=0;InitQueue(Q);BiTree p;p=T;if(T)EnQueue(Q,

15、T);/ printf(%d,QueueLength(Q);while(QueueLength(Q)!=0)DeQueue(Q,p);if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);if(!p-lchild&!p-rchild)i+;return i;int main()/主函數(shù)SqStack S;SqQueue Q,Q3;BiTree T=NULL,f,p;int i,n,e,a,b,c;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&e);InsertBST(T,e);scanf(%d,&a);scanf(%d,&b);scanf(%d,&c);Putout(T);printf(%dn,SearchBST(T,a,f,p);printf(%dn