二叉樹的各種算法

1、精選文檔二叉樹的各種算法.txt男人的承諾就像80歲老太太的牙齒，很少有真的。你嗜煙成性的時(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第一行：預(yù)備建樹的結(jié)點(diǎn)個(gè)數(shù)n 其次行：輸入n個(gè)整數(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 "stdio.h"#include "malloc.h"#define TRUE

3、1#define FALSE 0#define OK 1#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,*

4、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;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,ElemTy

5、pe 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(e<p->data)p->lchild=s;else p->rchild=s;return TRUE; else return FALSE;Status PrintElement( ElemType e ) / 輸出元素e的值printf("%d ", e ); return OK

6、;/ PrintElementStatus PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 前序遍歷二叉樹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;else return OK; / PreOrderTraverseStatus InOrderTr

7、averse( BiTree T, Status(*Visit)(ElemType) ) / 中序遍歷二叉樹T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。 /補(bǔ)全代碼,可用多個(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)(

8、ElemType) ) / 后序遍歷二叉樹T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。 /補(bǔ)全代碼,可用多個(gè)語句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) PreOrderTraverse(T,PrintElement);printf("n")

9、;InOrderTraverse(T, PrintElement); printf("n");PostOrderTraverse(T,PrintElement); printf("n"); return OK;/·······················非遞歸算法struct SqStack BiTree *base; /

10、在棧構(gòu)造之前和銷毀之后，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.

11、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; *S.top+=e; return OK;Status Pop(SqStack &S,BiTree &e) if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status Sta

12、ckEmpty(SqStack S) / 若棧S為空棧，則返回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->

13、rchild;return OK;/···························層次遍歷typedef struct BiTree *base; / 初始化的動(dòng)態(tài)安排存儲(chǔ)空間 int front; / 頭指針,若隊(duì)列不空,指向隊(duì)列頭元素 int rear; / 尾指針,若隊(duì)列不空,指向隊(duì)列尾元素的下一個(gè)位置 SqQue

14、ue;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+MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue &Q,BiTree e) / 插入元素e為Q的新的隊(duì)尾元素/ 請(qǐng)補(bǔ)全代碼 if(Q.rear+1)%

15、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.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;Status LevelTraverse(BiTree T

16、,SqQueue Q)/層次遍歷二叉樹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->rchild); /右孩子進(jìn)隊(duì) return OK; void Cha

17、nge(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ì)算右子樹的深度 int dep2=BTreeDepth(T->rchild)

18、; /返回樹的深度 if(dep1>dep2) 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;SqQue