《叉树的各种算法》由会员分享，可在线阅读，更多相关《叉树的各种算法（7页珍藏版）》请在金锄头文库上搜索。
1、二叉树的各种算法.txt男人的承诺就像80岁老太太的牙齿，很少有真的。你嗜烟成性的时候，只有三种人会高兴，医生你的仇人和卖香烟的。/*用函数实现如下二叉排序树算法：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字（函数返回值为成功1,失败0）（6）交换各结点的左右子树（7）求二叉树的深度（8）叶子结点数Input第一行：准备建树的结点个数n第二行：输入n个整数，用空格分隔第三行：输入待查找的关键字第四行：输入待查找的关键字第五行：输入待插入的关键字Output第一行：二叉树的先序遍历序列第二行：二叉树的中序遍历序列第三
2、行：二叉树的后序遍历序列第四行：查找结果第五行：查找结果第六行第八行：插入新结点后的二叉树的先、中、序遍历序列第九行：插入新结点后的二叉树的中序遍历序列（非递归算法）第十行：插入新结点后的二叉树的层次遍历序列第十一行第十三行：第一次交换各结点的左右子树后的先、中、后序遍历序列第十四行第十六行：第二次交换各结点的左右子树后的先、中、后序遍历序列第十七行：二叉树的深度第十八行：叶子结点数*/#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typed
3、efintStatus;typedefintKeyType;#defineSTACK_INIT_SIZE100/存储空间初始分配量#defineSTACKINCREMENT10/存储空间分配增量#defineMAXQSIZE100typedefintElemType;typedefstructBiTNodeElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p)if(!T)p=f;returnFALSE;elseif(
4、key=T-data)p=T;returnTRUE;elseif(keydata)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(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;elseif(edata)p-lchild=s;elsep-rchild=s;re
5、turnTRUE;elsereturnFALSE;StatusPrintElement(ElemTypee)/输出元素e的值printf(%d,e);returnOK;/PrintElementStatusPreOrderTraverse(BiTreeT,Status(*Visit)(ElemType)/前序遍历二叉树T的递归算法，对每个数据元素调用函数/补全代码,可用多个语句if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit)returnOK;returnERRO
6、R;elsereturnOK;/PreOrderTraverseStatusInOrderTraverse(BiTreeT,Status(*Visit)(ElemType)/中序遍历二叉树T的递归算法，对每个数据元素调用函数/补全代码,可用多个语句if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)returnOK;returnERROR;elsereturnOK;/InOrderTraverseStatusPostOrderTraverse(BiTreeT,Statu
7、s(*Visit)(ElemType)/后序遍历二叉树T的递归算法，对每个数据元素调用函数/补全代码,可用多个语句if(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)returnOK;returnERROR;elsereturnOK;Visit。Visit。Visit。/PostOrderTraverseStatusPutout(BiTreeT)PreOrderTraverse(T,PrintElement);printf(n);InOrderTraverse(
8、T,PrintElement);printf(n);PostOrderTraverse(T,PrintElement);printf(n);returnOK;structSqStackBiTree*base;/BiTree*top;/intstacksize;/;/顺序栈/非递归算法在栈构造之前和销毁之后，base的值为NULL栈顶指针当前已分配的存储空间，以元素为单位StatusInitStack(SqStack&S)=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!returnERROR;=STACK_INIT_SIZE;returnO
9、K;StatusPush(SqStack&S,BiTreee)if(=(BiTree*)realloc,+STACKINCREMENT)*sizeof(BiTree);if(!returnERROR;=+;+=STACKINCREMENT;*+=e;returnOK;StatusPop(SqStack&S,BiTree&e)if=returnERROR;returnOK;StatusStackEmpty(SqStackS)/若栈S为空栈，则返回TRUE否则返回FALSEifTRUE;elsereturnFALSE;StatusInOrderTraverse1(BiTreeT,Status(*V
10、isit)(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;returnOK;II层次遍历BiTree*base;IIintfront;IItypedefstruct初始化的动态分配存储空间头指针,若队列不空,指向队列头元素intrear;II尾指针,若队列不空,指向队列尾元素的下一个位置SqQueue;StatusInitQueue(SqQueue&Q
11、)=(BiTree*)malloc(MAXQSIZE*sizeof(BiTree);if(!returnERROR;=0;returnOK;intQueueLength(SqQueueQ)/返回Q的元素个数/请补全代码returnStatusEnQueue(SqQueue&Q,BiTreee)/插入元素e为Q的新的队尾元素/请补全代码if(+1)%MAXQSIZE=returnERROR;=e;=+1)%MAXQSIZE;returnOK;StatusDeQueue(SqQueue&Q,BiTree&e)/若队列不空,则删除Q的队头元素,用e返回其值,并返回0K;否则返回ERROR/请补全代码
12、if=returnERROR;e=;=+1)%MAXQSIZE;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-rchild);/右孩子进队ret
13、urnOK;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-rchild);/返回树的深度if(dep1dep2)returndep1+1;els
14、ereturndep2+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,p-rchild);if(!p-lchild&!p-rchild)i+;returni;intmain()/主函数SqStackS;SqQueu
15、eQ,Q3;BiTreeT=NULL,f,p;inti,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,p);printf(%dn,SearchBST(T,b,f,p);InsertBST(T,c);Putout(T);InOrderTraverse1(T,PrintElement,S);printf(n);LevelTraverse(T,Q);printf(n);Change(T);Putout(
