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的值为NULL
SElemType *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\
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;
} // CreateBiTree
Status 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 <= S2-> data)
if(!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 < e)
S = S->rchild;
else if(S -> data > e)
S = S->lchild;
else return OK;
}
return ERROR;
}
Status Visit( ElemType e ) { // 输出元素e的值
printf(\"%d \
return OK;
}// PrintElement
Status 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;
} // PreOrderTraverse
Status 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;
} // InOrderTraverse
Status 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;
} // PostOrderTraverse
Status 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=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 \
S3 = S1->lchild;S4 = S1->rchild;
if(S3) EnQueue(S2,S3);
if(S4) EnQueue(S2,S4);
}
return OK;
}
三. 总结
终于完成了这个实验报告，经过这次的磨练，我对数据结构这门学科有了更深的理解和感悟。对二叉树的各种操作也更熟悉了。经过这个小实验，我在算法方面还有更大的提升空间。我希望今后能更加注重算法的设计，我相信我的数据结构这门学科会学得很好的。这个实验过后我懂得了更多的编程技巧，学会了如何调试程序。这是实验过后总结的好处。希望以后能学到更多新知识。
