二叉树的各种算法

1、二叉树的各种算法.txt男人的承诺就像80岁老太太的牙齿，很少有真的。你嗜烟成性的时候，只有三种人会高兴，医生你的仇人和卖香烟的。/*用函数实现如下二叉排序树算法：（1） 插入新结点（2） 前序、中序、后序遍历二叉树（3） 中序遍历的非递归算法（4） 层次遍历二叉树（5） 在二叉树中查找给定关键字（函数返回值为成功1,失败0）（6） 交换各结点的左右子树（7） 求二叉树的深度（8） 叶子结点数Input第一行：准备建树的结点个数n第二行：输入n个整数，用空格分隔第三行：输入待查找的关键字第四行：输入待查找的关键字第五行：输入待插入的关键字Output第一行：二叉树的先序遍历序列第二行：二叉树的

2、中序遍历序列第三行：二叉树的后序遍历序列第四行：查找结果第五行：查找结果第六行第八行：插入新结点后的二叉树的先、中、序遍历序列第九行：插入新结点后的二叉树的中序遍历序列（非递归算法）第十行：插入新结点后的二叉树的层次遍历序列第十一行第十三行：第一次交换各结点的左右子树后的先、中、后序遍历序列第十四行第十六行：第二次交换各结点的左右子树后的先、中、后序遍历序列第十七行：二叉树的深度第十八行：叶子结点数# /#include"stdio.h"#include"malloc.h"# defineTRUE1# defineFALSE0# defineOK1# d

3、efineERROR0# defineINFEASIBLE-1# defineOVERFLOW-2typedefintStatus;typedefintKeyType;# defineSTACK_INIT_SIZE100/存储空间初始分配量# defineSTACKINCREMENT10/存储空间分配增量# defineMAXQSIZE100typedefintElemType;typedefstructBiTNodeElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;StatusSearchBST(BiTreeT,

4、KeyTypekey,BiTreef,BiTree&p)if(!T)p=f;returnFALSE;elseif(key=T->data)p=T;returnTRUE;elseif(key<T->data)returnSearchBST(T->lchild,key,T,p);elsereturn(SearchBST(T->rchild,key,T,p);StatusInsertBST(BiTree&T,ElemTypee)BiTrees,p;if(!SearchBST(T,e,NULL,p)s=(BiTree)malloc(sizeof(BiTNo

5、de);s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;elseif(e<p->data)p->lchild=s;elsep->rchild=s;returnTRUE;elsereturnFALSE;StatusPrintElement(ElemTypee)/输出元素e的值printf("%d",e);returnOK;/PrintElementStatusPreOrderTraverse(BiTreeT,Status(*Visit)(ElemType)/前序遍历二叉树T的递归算法，对每个数

6、据元素调用函数Visit/补全代码,可用多个语句if(T)if(Visit(T->data)if(PreOrderTraverse(T->lchild,Visit)if(PreOrderTraverse(T->rchild,Visit)returnOK;returnERROR;elsereturnOK;/PreOrderTraverseStatusInOrderTraverse(BiTreeT,Status(*Visit)(ElemType)Visit 。Visit 。/中序遍历二叉树T的递归算法，对每个数据元素调用函数/补全代码,可用多个语句if(T)if(InOrderT

7、raverse(T->lchild,Visit)if(Visit(T->data)if(InOrderTraverse(T->rchild,Visit)returnOK;returnERROR;elsereturnOK;/InOrderTraverseStatusPostOrderTraverse(BiTreeT,Status(*Visit)(ElemType)/后序遍历二叉树T的递归算法，对每个数据元素调用函数/补全代码,可用多个语句if(T)if(PostOrderTraverse(T->lchild,Visit)if(PostOrderTraverse(T->

8、;rchild,Visit)if(Visit(T->data)returnOK;returnERROR;elsereturnOK;/PostOrderTraverseStatusPutout(BiTreeT)PreOrderTraverse(T,PrintElement);printf("n");InOrderTraverse(T,PrintElement);printf("n");PostOrderTraverse(T,PrintElement);printf("n");returnOK;/非递归算法structSqStack

9、BiTree*base;/在栈构造之前和销毁之后，base的值为NULLBiTree*top;/栈顶指针intstacksize;/当前已分配的存储空间，以元素为单位;/顺序栈StatusInitStack(SqStack&S)S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!S.base)returnERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;StatusPush(SqStack&S,BiTreee)if(S.top-S.base)>=S

10、.stacksize)S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(!S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;returnOK;StatusPop(SqStack&S,BiTree&e)if(S.top=S.base)returnERROR;e=*-S.top;returnOK;StatusStackEmpty(SqStackS)/若栈S为空栈，则

11、返回TRUE否则返回FALSEif(S.top-S.base=0)returnTRUE;elsereturnFALSE;StatusInOrderTraverse1(BiTreeT,Status(*Visit)(ElemTypee),SqStackS)BiTreep;InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p->lchild;elsePop(S,p);if(!Visit(p->data)returnERROR;p=p->rchild;return OK;/层次遍历typedefstructBiTree*b

12、ase;/初始化的动态分配存储空间intfront;/头指针,若队列不空,指向队列头元素intrear;/尾指针,若队列不空,指向队列尾元素的下一个位置SqQueue;StatusInitQueue(SqQueue&Q)Q.base=(BiTree*)malloc(MAXQSIZE*sizeof(BiTree);if(!Q.base)returnERROR;Q.front=Q.rear=0;returnOK;intQueueLength(SqQueueQ)/返回Q的元素个数/请补全代码return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;StatusEnQu

13、eue(SqQueue&Q,BiTreee)/插入元素e为Q的新的队尾元素/请补全代码if(Q.rear+1)%MAXQSIZE=Q.front)returnERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;StatusDeQueue(SqQueue&Q,BiTree&e)/若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR/请补全代码if(Q.front=Q.rear)returnERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE

14、;returnOK;StatusLevelTraverse(BiTreeT,SqQueueQ)/层次遍历二叉树InitQueue(Q);BiTreep;p=T;if(T)EnQueue(Q,T);/printf("%d",QueueLength(Q);while(QueueLength(Q)!=0)DeQueue(Q,p);/根结点出队printf("%d",p->data);/输出数据if(p->lchild)EnQueue(Q,p->lchild);/左孩子进队if(p->rchild)EnQueue(Q,p->rchi

15、ld);/右孩子进队returnOK;voidChange(BiTreeT)BiTNode*p;if(T)p=T->lchild;T->lchild=T->rchild;T->rchild=p;Change(T->lchild);Change(T->rchild);/returnOK;intBTreeDepth(BiTreeT)/求由BT指针指向的一棵二叉树的深度/intdep1,dep2;if(T!=NULL)/计算左子树的深度intdep1=BTreeDepth(T->lchild);/计算右子树的深度intdep2=BTreeDepth(T-&g

16、t;rchild);/返回树的深度if(dep1>dep2)returndep1+1;elsereturndep2+1;elsereturn0;、叶子结点数Statusyezhi(BiTreeT,SqQueueQ)inti=0;InitQueue(Q);BiTreep;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

17、,p->rchild);if(!p->lchild&&!p->rchild)i+;returni;intmain()/主函数SqStackS;SqQueueQ,Q3;BiTreeT=NULL,f,p;inti,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);Pu