二叉樹的各種算法

1、考試學(xué)資學(xué)習(xí)網(wǎng)押題二叉樹的各種算法 .txt 男人的承諾就像80 歲 xx 的牙齒，很少有真的。你嗜煙成性的時(shí)候，只有三種人會(huì)高興， 醫(yī)生 你的仇人和賣香煙的。 /*用函數(shù)實(shí)現(xiàn)如下二叉排序樹算法：（ 1） 插入新結(jié)點(diǎn)（ 2） 前序、中序、后序遍歷二叉樹（ 3） 中序遍歷的非遞歸算法（ 4） 層次遍歷二叉樹（ 5） 在二叉樹中查找給定關(guān)鍵字（函數(shù)返回值為成功 1,失敗 0）（ 6） 交換各結(jié)點(diǎn)的左右子樹（ 7） 求二叉樹的深度（ 8） 葉子結(jié)點(diǎn)數(shù)Input第一行：準(zhǔn)備建樹的結(jié)點(diǎn)個(gè)數(shù)n第二行：輸入n 個(gè)整數(shù)，用空格分隔第三行：輸入待查找的關(guān)鍵字第四行：輸入待查找的關(guān)鍵字第五行：輸入待插入的關(guān)鍵字O

2、utput第一行：二叉樹的先序遍歷序列第二行：二叉樹的中序遍歷序列第三行：二叉樹的后序遍歷序列1 / 15第四行：查找結(jié)果第五行：查找結(jié)果第六行第八行：插入新結(jié)點(diǎn)后的二叉樹的先、中、序遍歷序列第九行：插入新結(jié)點(diǎn)后的二叉樹的中序遍歷序列（非遞歸算法）第十行：插入新結(jié)點(diǎn)后的二叉樹的層次遍歷序列第十一行第十三行：第一次交換各結(jié)點(diǎn)的左右子樹后的先、中、后序遍歷序列第十四行第十六行：第二次交換各結(jié)點(diǎn)的左右子樹后的先、中、后序遍歷序列第十七行：二叉樹的深度第十八行：葉子結(jié)點(diǎn)數(shù)# /#include stdio.h#include malloc.h# define TRUE 1# define FALSE

3、0#define OK 1#define ERROR 0#define INFEASIBLE -1 #define OVERFLOW -2typedef int Status;typedef int KeyType;2 / 15#define STACK_INIT_SIZE 100存儲(chǔ)空間初始分配量/#define STACKINCREMENT 10存儲(chǔ)空間分配增量/#define MAXQSIZE 100typedef int ElemType;typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;/ 左右孩子指

4、針 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;return 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=

5、(BiTree)malloc(sizeof(BiTNode);3 / 15s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;else if(edata)p-lchild=s;else p-rchild=s;return TRUE;else return FALSE;Status PrintElement( ElemType e ) / 輸出元素 e 的值printf(%d , e );return OK;/ PrintElementStatus PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 前

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

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

8、isit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)return OK;return ERROR;else return OK; / PostOrderTraverseStatus Putout(BiTree T)PreOrderTraverse(T,PrintElement);printf( );InOrderTraverse(T, PrintElement);printf();PostOrderTraverse(T,PrintElement);printf();return OK;/非遞歸算法struct SqStack6 /

9、15BiTree *base; / 在棧構(gòu)造之前和銷毀之后， base 的值為 NULLBiTree *top; / 棧頂指針int stacksize; / 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位; / 順序棧Status InitStack(SqStack &S)S.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,BiTree e)if(S.t

10、op-S.base)=S.stacksize)S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(!S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;7 / 15*S.top+=e;return OK;Status Pop(SqStack &S,BiTree &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status StackEmpty(

11、SqStack S)/若棧S為空棧，則返回TRUE否則返回FALSEif(S.top-S.base=0)return 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;8 / 15elsePop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/層次遍

12、歷typedef structBiTree *base; / 初始化的動(dòng)態(tài)分配存儲(chǔ)空間int front; / 頭指針,若隊(duì)列不空,指向隊(duì)列頭元素int rear; / 尾指針 ,若隊(duì)列不空 ,指向隊(duì)列尾元素的下一個(gè)位置SqQueue;Status InitQueue(SqQueue &Q)Q.base=(BiTree*)malloc(MAXQSIZE*sizeof(BiTree);if(!Q.base)return ERROR;Q.front=Q.rear=0;9 / 15return OK;int QueueLength(SqQueue Q)/ 返回 Q 的元素個(gè)數(shù)/ 請(qǐng)補(bǔ)全代碼retur

13、n(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue &Q,BiTree e)/ 插入元素 e 為 Q 的新的隊(duì)尾元素/ 請(qǐng)補(bǔ)全代碼if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue &Q,BiTree &e)/若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK;否則返回 ERROR/ 請(qǐng)補(bǔ)全代碼10 / 15if(Q.front=Q.rear

14、)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;Status LevelTraverse(BiTree T,SqQueue 理歡遍歷二叉樹InitQueue(Q);BiTree p;p=T;if(T)EnQueue(Q,T);/ printf(%d,QueueLength(Q);while(QueueLength(Q)!=0)DeQueue(Q,p); / 根結(jié)點(diǎn)出隊(duì)printf(%d ,p-data); / 輸出數(shù)據(jù)if(p-lchild)EnQueue(Q,p-lchild); / 左孩子進(jìn)隊(duì) if(

15、p-rchild)EnQueue(Q,p-rchild); / 右孩子進(jìn)隊(duì) return OK; 11 / 15void 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 BTreeDepth(BiTree T)求由BT指針指向的一棵二叉樹的深度/ int dep1,dep2;if(T!=NULL)/ 計(jì)算左子樹的深度int dep1=BTreeDepth(T-lchild);/ 計(jì)算右子樹的深度12

16、/ 15int dep2=BTreeDepth(T-rchild);/ 返回樹的深度if(dep1dep2)return dep1+1;elsereturn dep2+1;else return 0;葉子結(jié)點(diǎn)數(shù) Status yezhi(BiTree T,SqQueue Q)int i=0;InitQueue(Q);BiTree p;p=T;if(T)EnQueue(Q,T);/ printf(%d,QueueLength(Q);while(QueueLength(Q)!=0)DeQueue(Q,p);13 / 15if(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