数据结构 创建二叉排序树与查找(2)

教师评语： 实验成绩：

指导教师签名：

批阅日期：

代码：

# include # include

//—————————————————————————————————————————— typedef struct node {

//data用于存储二叉树中的字母

//二叉树结点的类型描述

char data;

struct node *lchild; //lchild为指向该结点左孩子的指针 struct node *rchild; //rchild为指向该结点下一层的指针

}BiTNode;

//—————————————————————————————————————————— typedef struct {

BiTNode *pin[40]; int top;

//指针数组，用于存储广义表结点指针

//栈顶指针

//顺序栈的类型描述

}SeqStack;

//—————————————————————————————————————————— void Create(BiTNode *B) {

int m; char r; BiTNode *p,*q; p=NULL;

//定义指向当前结点的指针p,新结点的指针q

//初始时p为空

//建立二叉排序树的函数

printf(\请输入顶点数据:\while(r!='\\n') {

scanf(\ if(p==NULL) { } else {

q=(BiTNode *)malloc(sizeof(BiTNode)); q->data=m;

//申请新结点q

//令该数据存入当前结点的data域

//对于其它数据执行以下操作

B->data=m; p=B;

//输入结点数据

//第一个数据置到根节点，p指针指向根结点

//输入回车表示循环结束

q->lchild=NULL;q->rchild=NULL; p=B;

//令新结点q的lchild域和rchild域为空

}

}

}

while(p->data!=q->data) { }

if(p->datadata) { } else { }

//当p指针所指结点和q指针所指结点中的数据不同时执行以下操作

//如果p结点数据小于新结点q中的数据,执行以下操作

if(p->rchild==NULL)

p->rchild=q;

//如果p的右孩子为空，令p的右孩子为q

p=p->rchild; //将p的右孩子赋p

//如果p结点数据大于新结点q中的数据,执行以下操作

if(p->lchild==NULL)

p->lchild=q;

//如果p的左孩子为空，令p的左孩子为q

p=p->lchild; //将p的左孩子赋p

//—————————————————————————————————————————— void Search(BiTNode *B,int key) { }

//—————————————————————————————————————————— void Inorder(BiTNode *B,SeqStack &K) {

printf(\中序遍历结果为:\ BiTNode *p; p=B;

//提示以下结果为中序遍历结果

//p指针指向当前结点 //当前结点为根结点

//二叉树的中序遍历函数

BiTNode *p; p=B;

//定义指向当前结点的指针p //初始时p指向根结点

//查找函数

while(p!=NULL&&p->data!=key) { }

if(p->data

p=p->rchild;

//当p不为空且p所指结点的数据不为待查找数据时，执行以下操作

//如果当前结点中的数据小于待查找数据，则令p指向它的右孩子

else

//如果当前结点中的数据大于待查找数据，则令p指向它的左孩子

p=p->lchild;

if(p==NULL) printf(\待查找数据不存在\\n\循环结束后，若p为空则待查找数据不存在;否则待查找数据存在 else printf(\待查找数据存在\\n\printf(\

while(K.top!=-1||p!=NULL) {

if(p==NULL)

//当栈不为空或当前结点指针p不为空时，执行以下操作

//如果当前结点指针p为空，执行以下操作

}

}

{ } else { }

K.top++;

//当前结点指针p入栈

//如果当前结点指针p不为空，执行以下操作

p=K.pin[K.top]; K.top--;

printf(\p=p->rchild;

//输出当前结点p中的数据

//令当前结点p的rchild域所指的结点作为当前结点p

//出栈，栈顶元素所指的结点作为当前结点p

K.pin[K.top]=p; p=p->lchild;

//令当前结点p的rchild域所指的结点作为当前结点p

printf(\

//—————————————————————————————————————————— int main() {

int key;

char a='A',b='B',c; BiTNode *B; SeqStack K; K.top=-1; while(a=='A') { }

printf(\谢谢使用!\\n\

B=(BiTNode *)malloc(sizeof(BiTNode)); B->rchild=NULL;B->lchild=NULL; Create(B); Inorder(B,K); while(b=='B') { } a=c; b='B';

printf(\输入待查找数据:\

scanf(\//输入待查找数据 getchar(); Search(B,key);

//进行查找

//申请根结点

//令根结点B的lchild域和rchild域为空

//创建二叉排序树 //中序遍历二叉树中的数据 //B表示查找数据操作

//A表示创建新的二叉排序树

//定义根结点指针 //定义栈并初始化栈

printf(\选择操作(A.新二叉排序树;B.继续查找;C.结束操作):\scanf(\printf(\b=c;

//根据提示，选择下一步操作

} /**

return 0;

请输入顶点数据:53 25 76 20 48 14 60 84 33 78 中序遍历结果为:14 20 25 33 48 53 60 76 78 84 输入待查找数据:33 待查找数据存在

选择操作(A.新二叉排序树;B.继续查找;C.结束操作):B

输入待查找数据:54 待查找数据不存在

选择操作(A.新二叉排序树;B.继续查找;C.结束操作):C

谢谢使用!

Press any key to continue */