


版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、二叉樹(shù)的各種算法.txt男人的承諾就像80歲老太太的牙齒,很少有真的。你嗜煙成性的時(shí)候,只有三種人會(huì)高興,醫(yī)生你的仇人和賣(mài)香煙的。/*用函數(shù)實(shí)現(xiàn)如下二叉排序樹(shù)算法: (1) 插入新結(jié)點(diǎn) (2) 前序、中序、后序遍歷二叉樹(shù) (3) 中序遍歷的非遞歸算法 (4) 層次遍歷二叉樹(shù) (5) 在二叉樹(shù)中查找給定關(guān)鍵字(函數(shù)返回值為成功1,失敗0) (6) 交換各結(jié)點(diǎn)的左右子樹(shù) (7) 求二叉樹(shù)的深度 (8) 葉子結(jié)點(diǎn)數(shù)Input第一行:準(zhǔn)備建樹(shù)的結(jié)點(diǎn)個(gè)數(shù)n 第二行:輸入n個(gè)整數(shù),用空格分隔 第三行:輸入待查找的關(guān)鍵字 第四行:輸入待查找的關(guān)鍵字 第五行:輸入待插入的關(guān)鍵字Output第一行:二叉樹(shù)的先序
2、遍歷序列 第二行:二叉樹(shù)的中序遍歷序列 第三行:二叉樹(shù)的后序遍歷序列 第四行:查找結(jié)果 第五行:查找結(jié)果 第六行第八行:插入新結(jié)點(diǎn)后的二叉樹(shù)的先、中、序遍歷序列 第九行:插入新結(jié)點(diǎn)后的二叉樹(shù)的中序遍歷序列(非遞歸算法) 第十行:插入新結(jié)點(diǎn)后的二叉樹(shù)的層次遍歷序列 第十一行第十三行:第一次交換各結(jié)點(diǎn)的左右子樹(shù)后的先、中、后序遍歷序列 第十四行第十六行:第二次交換各結(jié)點(diǎn)的左右子樹(shù)后的先、中、后序遍歷序列 第十七行:二叉樹(shù)的深度 第十八行:葉子結(jié)點(diǎn)數(shù)*/#include stdio.h#include malloc.h#define TRUE 1#define FALSE 0#define OK 1
3、#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int KeyType;#define STACK_INIT_SIZE 100 / 存儲(chǔ)空間初始分配量#define STACKINCREMENT 10 / 存儲(chǔ)空間分配增量#define MAXQSIZE 100typedef int ElemType;typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild;/左右孩子指針 BiTNode,*BiTr
4、ee;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=(BiTree)malloc
5、(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 TRUE; else return FALSE;Status PrintElement( ElemType e ) / 輸出元素e的值printf(%d , e ); return OK;/ PrintElementStatus PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 前序遍歷二叉樹(shù)T的遞歸算法,對(duì)每個(gè)數(shù)據(jù)元素
6、調(diào)用函數(shù)Visit。 /補(bǔ)全代碼,可用多個(gè)語(yǔ)句 if(T)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(*Visit)(ElemType) ) / 中序遍歷二叉樹(shù)T的遞歸算法,對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。 /補(bǔ)全代碼,可用多個(gè)語(yǔ)句if(T)if(InOrderTraver
7、se(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) ) / 后序遍歷二叉樹(shù)T的遞歸算法,對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。 /補(bǔ)全代碼,可用多個(gè)語(yǔ)句if(T) if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-r
8、child,Visit)if(Visit(T-data)return OK;return ERROR;else return OK; / PostOrderTraverseStatus Putout(BiTree T) PreOrderTraverse(T,PrintElement);printf(n);InOrderTraverse(T, PrintElement); printf(n);PostOrderTraverse(T,PrintElement); printf(n); return OK;/非遞歸算法struct SqStack BiTree *base; / 在棧構(gòu)造之前和銷(xiāo)毀之
9、后,base的值為NULL BiTree *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.top-S.base)=S.stacksize)
10、 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; *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(SqStack S) / 若棧S為空棧,則返
11、回TRUE,否則返回FALSE if(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;else Pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/層次遍歷typedef struct BiTre
12、e *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; return OK;int QueueLength(SqQueue Q) / 返回Q的元素個(gè)數(shù)/ 請(qǐng)補(bǔ)全代碼 return(Q.rear-Q.front+MAXQ
13、SIZE)%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ǔ)全代碼 if(Q.front=Q.rear)return ERROR; e=Q.ba
14、seQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;Status LevelTraverse(BiTree T,SqQueue Q)/層次遍歷二叉樹(shù)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(p-rchild)EnQueue(Q,p
15、-rchild); /右孩子進(jìn)隊(duì) 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 BTreeDepth(BiTree T) /求由BT指針指向的一棵二叉樹(shù)的深度 /int dep1,dep2; if(T!=NULL) /計(jì)算左子樹(shù)的深度 int dep1=BTreeDepth(T-lchild); /計(jì)算右子樹(shù)的深度 int dep2=BTreeDepth(T-rch
16、ild); /返回樹(shù)的深度 if(dep1dep2) return dep1+1; else return 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);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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 血液透析專(zhuān)業(yè)理論與實(shí)踐考核要點(diǎn)解析
- 安全生產(chǎn)三卡是指
- 生產(chǎn)安全事故調(diào)查處理報(bào)告
- 綠色金融估值體系-洞察及研究
- 第二十個(gè)全國(guó)安全生產(chǎn)月
- 基礎(chǔ)樁植樁法試樁施工技術(shù)方案探討
- 建筑類(lèi)安全生產(chǎn)許可證延期
- 2025企業(yè)安全生產(chǎn)檔案
- 安全生產(chǎn)事故隱患是指
- 消防安全制度一
- 2025至2030中國(guó)燕窩行業(yè)市場(chǎng)運(yùn)行分析及競(jìng)爭(zhēng)格局與投資方向報(bào)告
- 2025年河北省中考語(yǔ)文試卷真題及答案詳解(精校打印版)
- 口服靶向藥講課件
- 12024-2025學(xué)年暑假安全教育主題班會(huì)課件
- 肝膽外科醫(yī)學(xué)科普
- 能源轉(zhuǎn)型與碳市場(chǎng)機(jī)制協(xié)同的路徑優(yōu)化研究
- 包席合同協(xié)議
- 資產(chǎn)評(píng)估風(fēng)險(xiǎn)管理制度
- 中醫(yī)醫(yī)療技術(shù)手冊(cè)2013普及版
- 海運(yùn)出口培訓(xùn)課程教學(xué)課件
- 2023年副主任醫(yī)師(副高)-內(nèi)科學(xué)(副高)考試歷年高頻考點(diǎn)參考題庫(kù)附帶專(zhuān)家答案
評(píng)論
0/150
提交評(píng)論