资源描述：
《实现二叉排序树的各种算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、wyf实现二叉排序树的各种算法一.需求分析(1)系统概述：本系统是针对排序二叉树设计的各种算法，提供的功能包括有：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0)二.总体设计(1)系统模块结构图(2)数据结构设计typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;typedefBiTreeSElemType;typedefBiT
2、reeQElemType;typedefstruct{QElemType*base;//初始化的动态分配存储空间intfront;//头指针,若队列不空,指向队列头元素intrear;//尾指针,若队列不空,指向队列尾元素的下一个位置}SqQueue;typedefstruct{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//顺序栈StatusInitStack(SqStack&S){//构造一个空
3、栈S，该栈预定义大小为STACK_INIT_SIZE//请补全代码S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)return(ERROR);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusPush(SqStack&S,BiTreee){//在栈S中插入元素e为新的栈顶元素//请补全代码if(S.top-S.base>=S.stacksize){S.base=(SElemType*)reallo
4、c(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR//请补全代码if(S.top==S.base)returnERROR;e=*--S.top;return
5、OK;}StatusInitQueue(SqQueue&Q){//构造一个空队列Q，该队列预定义大小为MAXQSIZE//请补全代码Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)returnERROR;Q.front=Q.rear=0;returnOK;}StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素//请补全代码if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[
6、Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}StatusDeQueue(SqQueue&Q,QElemType&e){//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR//请补全代码if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}StatusCreateBiTree(BiTree&T,intn){//算法6.4//按先序次序输入二叉树中结点的值（一个
7、字符）//构造二叉链表表示的二叉树T。inti,e,loop=1;BiTreeS1,S2;for(i=1;i<=n;i++){loop=1;scanf("%d",&e);if(!(S1=(BiTNode*)malloc(sizeof(BiTNode))))returnERROR;S1->data=e;S1->lchild=NULL;S1->rchild=NULL;S2=T;if(S2==NULL)T=S1;elsewhile(loop){if(S1->datadata)if(S2->lchild==NULL){S2->lchild=S1;loo
8、p=0;}elseS2=S2->lchild;elseif(S2->rchild
