《实现二叉排序树的各种算法》由会员分享，可在线阅读，更多相关《实现二叉排序树的各种算法（14页珍藏版）》请在金锄头文库上搜索。
1、wyf实现二叉排序树的各种算法一一. .需求分析需求分析(1)系统概述：系统概述：本系统是针对排序二叉树设计的各种算法，提供的功能包括有：（1） 插入新结点（2） 前序、中序、后序遍历二叉树（3） 中序遍历的非递归算法（4） 层次遍历二叉树（5） 在二叉树中查找给定关键字(函数返回值为成功 1,失败 0)二二. .总体设计总体设计 (1)系统模块结构图系统模块结构图(2)数据结构设计数据结构设计typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;type
2、def BiTree SElemType;typedef BiTree QElemType;typedef structQElemType *base; / 初始化的动态分配存储空间初始化的动态分配存储空间int front; / 头指针头指针,若队列不空若队列不空,指向队列头元素指向队列头元素int rear; / 尾指针尾指针,若队列不空若队列不空,指向队列尾元素的下一个位置指向队列尾元素的下一个位置SqQueue;typedef struct SElemType *base; / 在栈构造之前和销毁之后，在栈构造之前和销毁之后，base 的值为的值为NULLSElemType *top;
3、 / 栈顶指针栈顶指针int stacksize; / 当前已分配的存储空间，以元素为单位当前已分配的存储空间，以元素为单位SqStack; / 顺序栈顺序栈Status InitStack(SqStack if(!S.base) return (ERROR);S.top = S.base ;S.stacksize = STACK_INIT_SIZE;return OK;Status Push(SqStack if(!S.base )return ERROR;S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;* S.top +
4、 = e;return OK;Status Pop(SqStack e = * -S.top;return OK;Status InitQueue(SqQueue if(!Q.base) return ERROR;Q.front = Q.rear = 0;return OK;Status EnQueue(SqQueue Q.baseQ.rear = e ;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK;Status DeQueue(SqQueue 否则返回否则返回 ERROR/ 请补全代码请补全代码if(Q.front = Q.rear) return E
5、RROR;e = Q.baseQ.front;Q.front = (Q.front +1) % MAXQSIZE;return OK;Status CreateBiTree(BiTree BiTree S1,S2;for(i=1;i data = e;S1 - lchild = NULL;S1 - rchild = NULL;S2 = T;if(S2 = NULL) T = S1;else while(loop)if(S1-data data)if(S2-lchild = NULL)S2 -lchild = S1; loop = 0;else S2=S2-lchild;else if(S2-r
6、child = NULL)S2 - rchild = S1; loop = 0;else S2=S2-rchild;return OK; / CreateBiTreeStatus Insert( BiTree T) /插入新结点插入新结点BiTree S1, S2;ElemType e;scanf(“%d“,if(!(S2 = (BiTNode *)malloc(sizeof(BiTNode) return ERROR;S2 - data = e;S2 - rchild = NULL; S2 - lchild = NULL;S1 = T;while(T)if(S1 - data data)if
7、(!S1 - rchild)S1 - rchild = S2;return OK;else S1 = S1-rchild;else if(!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 rchild;else if(S - data e)S = S-lchild;else return OK;return ERROR; Status Visit(
8、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-rchi
9、ld , 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-rchil
10、d , 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
11、(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
12、) /层次层次/遍历遍历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;三三. .总结总结终于完成了这个实验报告，经过这次的磨练，我对数据结构终于完成了这个实验报告，经过这次的磨练，我对数据结构这门学科有了更深的理解和感悟。对二叉树的各种操作也更熟悉这门学科有了更深的理解和感悟。对二叉树的各种操作也更熟悉了。经过这个小实验，我在算法方面还有更大的提升空间。我希了。经过这个小实验，我在算法方面还有更大的提升空间。我希望今后能更加注重算法的设计，我相信我的数据结构这门学科会望今后能更加注重算法的设计，我相信我的数据结构这门学科会学得很好的。这个实验过后我懂得了更多的编程技巧，学会了如学得很好的。这个实验过后我懂得了更多的编程技巧，学会了如何调试程序。这是实验过后总结的好处。希望以后能学到更多新何调试程序。这是实验过后总结的好处。希望以后能学到更多新知识。知识。
