wyf实现二叉排序树的各种算法一.需求分析(1)系统概述：本系统是针对排序二叉树设计的各种算法，提供的功能包括有：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0)二.总体设计(1)系统模块结构图(2)数据结构设计typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针} BiTNode,*BiTree;typedef BiTree SElemType;typedef BiTree QElemType;typedef struct{QElemType *base; // 初始化的动态分配存储空间int front; // 头指针,若队列不空,指向队列头元素int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置}SqQueue;typedef struct{SElemType *base; // 在栈构造之前和销毁之后，base的值为NULLSElemType *top; // 栈顶指针int stacksize; // 当前已分配的存储空间，以元素为单位}SqStack; // 顺序栈Status InitStack(SqStack &S){// 构造一个空栈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;return OK;}Status Push(SqStack &S,BiTree e){// 在栈S中插入元素e为新的栈顶元素// 请补全代码if(S.top - S.base >= S.stacksize){S.base = (SElemType * )realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType));if(!S.base )return ERROR;S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}* S.top ++ = e;return OK;}Status Pop(SqStack &S,SElemType &e){// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR// 请补全代码if(S.top == S.base)return ERROR;e = * --S.top;return OK;}Status InitQueue(SqQueue &Q){// 构造一个空队列Q，该队列预定义大小为MAXQSIZE// 请补全代码Q.base = (QElemType *)malloc (MAXQSIZE * sizeof(QElemType));if(!Q.base) return ERROR;Q.front = Q.rear = 0;return OK;}Status EnQueue(SqQueue &Q,QElemType e){// 插入元素e为Q的新的队尾元素// 请补全代码if((Q.rear + 1)% MAXQSIZE == Q.front)return ERROR;Q.base[Q.rear] = e ;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q, QElemType &e){// 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR// 请补全代码if(Q.front == Q.rear) return ERROR;e = Q.base[Q.front];Q.front = (Q.front +1) % MAXQSIZE;return OK;}Status CreateBiTree(BiTree &T , int n) { // 算法6.4// 按先序次序输入二叉树中结点的值（一个字符）// 构造二叉链表表示的二叉树T。

int i ,e ,loop = 1;BiTree S1,S2;for(i=1;i<=n;i++){loop = 1;scanf("%d",&e);if(!(S1 = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;S1 -> data = e;S1 -> lchild = NULL;S1 -> rchild = NULL;S2 = T;if(S2 == NULL) T = S1;else while(loop){if(S1->data < S2->data)if(S2->lchild == NULL){S2 ->lchild = S1; loop = 0;}else S2=S2->lchild;else if(S2->rchild == NULL){S2 -> rchild = S1; loop = 0;}else S2=S2->rchild;}}return OK;} // CreateBiTreeStatus Insert( BiTree T) //插入新结点{BiTree S1, S2;ElemType e;scanf("%d",&e);if(!(S2 = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;S2 -> data = e;S2 -> rchild = NULL; S2 -> lchild = NULL;S1 = T;while(T){if(S1 -> data <= S2-> data)if(!S1 -> rchild){S1 -> rchild = S2;return OK;}else S1 = S1->rchild;elseif(!S1 -> lchild){S1 -> lchild = S2;return OK;}else S1 = S1->lchild;}T = S2;return OK;}Status Search( BiTree T ,ElemType e) {BiTree S;S = T;while(S){if(S -> data < e)S = S->rchild;else if(S -> data > e)S = S->lchild;else return OK;}return ERROR;}Status Visit( ElemType e ) { // 输出元素e的值printf("%d ", e );return OK;}// PrintElementStatus PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) { // 前序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。

//补全代码,可用多个语句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) ) { // 中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。

//补全代码,可用多个语句if(T)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)(ElemType) ) { // 后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。

//补全代码,可用多个语句if(T){if(PostOrderTraverse(T->lchild , Visit))if(PostOrderTraverse(T->rchild , Visit))if(Visit(T->data)) return OK;return ERROR;}else return OK;} // PostOrderTraverseStatus Dif_InOrder( BiTree T ) //中序遍历的非递归算法{BiTree S1;SqStack S2;S1 = T;InitStack(S2);while(S1 || S2.base != S2.top){if(S1){Push( S2, S1);S1 = S1-> lchild;}else{Pop(S2,S1);printf("%d ",S1->data);S1=S1->rchild;}}return OK;}Status Level( BiTree T ) /层次/遍历{BiTree S1, S3, S4;S1 = T;SqQueue S2;InitQueue(S2);EnQueue(S2,S1);while(S2.front != S2.rear){DeQueue(S2,S1);printf("%d ",S1->data);S3 = S1->lchild;S4 = S1->rchild;if(S3) EnQueue(S2,S3);if(S4) EnQueue(S2,S4);}return OK;}三.总结终于完成了这个实验报告，经过这次的磨练，我对数据结构这门学科有了更深的理解和感悟。