叉樹的各種算法

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

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

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

4、us 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(key<T->data)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

5、,NULL,p)s=(BiTree)malloc(sizeof(BiTNode); s->data=e;s->lchild=s->rchild=NULL; if(!p)T=s;else if(e<p->data)p->lchild=s;else p->rchild=s;return TRUE;else return FALSE;Status PrintElement( ElemType e ) / printf("%d ", e );return OK;/ PrintElement輸出元素 e 的值Status PreOrderTr

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

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

8、 的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)/ 補(bǔ)全代碼 , 可用多個語句if(T)if(PostOrderTraverse(T->lchild,Visit) if(PostOrderTraverse(T->rchild,Visit) if(Visit(T->data)return OK; return ERROR;Visit 。else return OK; / PostOrderTraverseStatus Putout(BiTree T) PreOrderTraverse(T,PrintElement);printf("n");InOrderTraverse

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

10、eof(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) e=*;if=return ERROR;return OK;Status StackEmpty(SqStack S) /

11、若棧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 *bas

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

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

14、tf("%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); / if(p->rchild)EnQueue(Q,p->rchild); /左孩子進(jìn)隊(duì)右孩子進(jìn)隊(duì)return OK;void Change(BiTree T)BiTNode *p;if(T) p=T->lchild;T->lchild=T->rc

15、hild; T->rchild=p;Change(T->lchild);Change(T->rchild); / return OK;int BTreeDepth(BiTree T)/ 求由 BT 指針指向的一棵二叉樹的深度 / int dep1,dep2;if(T!=NULL)計算左子樹的深度int dep1=BTreeDepth(T->lchild); 計算右子樹的深度int dep2=BTreeDepth(T->rchild); 返回樹的深度 if(dep1>dep2)return dep1+1;else/return dep2+1;else retu

16、rn 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); if(p->lchild)EnQueue(Q,p->lchild); if(p->rchild)EnQueue(Q,p->rchild); if(!p->lchild&&!p->rchild)i+;

17、return i;主函數(shù)int main() /SqStack S; SqQueue Q,Q3; BiTree T=NULL,f,p; int i,n,e,a,b,c; scanf("%d",&n); for(i=0;i<n;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",SearchBST(T,b,f,p);InsertBST(T,c);Putout