#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxsize 256
typedef char datatype;
typedef int keytype;
typedef long ctype;
typedef struct
{
char name[50];
ctype number;
keytype score;
}stu;
typedef struct node {
char* other;
ctype another;
keytype key;
struct node* lchild, * rchild;
}bstnode;
void Insertbst(bstnode*& T, bstnode* r) // t为二叉排序树的根指针，s为插入的结点指针
{
if (T == NULL) { T = r; } //原树为空, 返回s作为根指针
else
{
if (r->key < T->key) Insertbst(T->lchild, r);
//在左子树中查找插入位置_
else Insertbst(T->rchild, r); //在右子树中查找插入位置
}
}// Insertbst 递归算法
/*
bstnode*creatbst() //生成二叉排序树
{bstnode *t,*s;
keytype key, endflag=0;
datatype data;
t=NULL; // 设置二叉排序树的初态为空树
scanf("%d",&key); //读入一个结点的关键字
while(key!=endflag)
{s=(bstnode*)malloc(sizeof(bstnode)); //申请新结点
s->lchild=s->rchild=NULL; //新结点指针域置空
s->key=key;
scanf ("%c",&data); //读入结点的其他数据
s->other=data;
Insertbst(t,s); //将新结点插入书t中
scanf("%d",&key); //读入下一个结点的关键字
}
return t;
}
*/
bstnode* creatbst(stu a[], int m) //生成二叉排序树
{
bstnode* t, * s;
t = NULL; // 设置二叉排序树的初态为空树
for (int i = 0; i < m; i++)
{
s = (bstnode*)malloc(sizeof(bstnode)); //申请新结点
s->lchild = s->rchild = NULL; //新结点指针域置空
s->key = a[i].score; //读入结点的其他数据
s->other = a[i].name;
s->another = a[i].number;
Insertbst(t, s); //将新结点插入书t中
}
return t;
}
void preorder(bstnode* root) //前序遍历 使用的原函数 递归输出成功
{
bstnode* p;
p = root;
if (p != NULL)
{
printf("%d,%s,%ld\n", p->key, p->other,p->another);
preorder(p->lchild);
preorder(p->rchild);
}
}
void inorder(bstnode* root)
{
bstnode* p;
p = root;
if (p != NULL)
{
inorder(p->lchild);
printf("%d,%s,%ld\n", p->key,p->other, p->another);
inorder(p->rchild);
}
}
int SearchBST(bstnode* bt, keytype k)
//以递归方式输出从根节点到查找到的节点的路径
{
if (bt == NULL)
return 0;
else if (k == bt->key)
{
printf("%d,%s,%ld\n", bt->key, bt->other, bt->another);
return 1;
}
else if (k < bt->key)
SearchBST(bt->lchild, k); //在左子树中递归查找
else
SearchBST(bt->rchild, k); //在右子树中递归查找
}
//************************************队列定义*********************适用后来广度遍历
typedef struct {
bstnode data[50];
int front;
int rear;
}SeQueue;
void InitQueue(SeQueue*& sq) //建立空循环队列sq
{
sq = (SeQueue*)malloc(sizeof(SeQueue));
sq->front = sq->rear = 0;
}
void SetNull(SeQueue* sq)//置队列sq为空队
{
sq->front = sq->rear = 0;
}
int Length(SeQueue* sq)
{
return (sq->rear - sq->front + maxsize) % maxsize;
}
int Enqueue(SeQueue* sq, bstnode* x)
// 将新元素x插入队列 *sq 的队尾，入队成功返回1，不成功返回0
{
if (sq->front == (sq->rear + 1) % maxsize)
{
printf("队列上溢"); return(0);
}
else {
sq->rear = (sq->rear + 1) % maxsize;
sq->data[sq->rear] = *x;
return(1);
}
}
int Dequeue(SeQueue* sq, bstnode* x) // 通过参数x带回元素值，出队成功返回1，否则返回0
{
if (sq->front == sq->rear)
{
printf("队列下溢"); return(0);
}
else
{
sq->front = (sq->front + 1) % maxsize;
*x = sq->data[sq->front];
return(1);
}
}
//*************************************************************
void layer(bstnode* T)
{
bstnode* p=T;
SeQueue* Q; InitQueue(Q);
if (T != NULL)
{
Enqueue(Q, T);
while (Q->front != Q->rear)
{
Dequeue(Q, p);
printf("%d,%s,%ld\n", p->key, p->other, p->another);
if (p->lchild != NULL)
{
Enqueue(Q, p->lchild);
}
if (p->rchild != NULL)
{
Enqueue(Q, p->rchild);
}
}
}
}
void findpreorder(bstnode* root, char* a)//使用的寻找信息函数 问题所在
{
bstnode* p;
p = root;
if (p != NULL)
{
if (strcmp(p->other, a)==0)
{
printf("%d,%s,%ld\n", p->key, p->other, p->another);
}
findpreorder(p->rchild,a);
findpreorder(p->lchild,a);
}
}
void findscore(bstnode* root, int a)
{
bstnode* p;
p = root;
if (p != NULL)
{
if (a<=p->key)
{
printf("%d,%s,%ld\n", p->key, p->other, p->another);
}
findscore(p->rchild, a);
findscore(p->lchild, a);
}
}
void main()
{
int i,m=12,c;
char z[maxsize] ;
stu mission[12] = { {"雷震子",101401,82}, {"姜子牙",100032,90}, {"哪吒",101674,70}, {"申公豹",101982,87}, {"九尾狐",107431,75},
{"天尊",100001,98},
{"太乙",101009,81},
{"杨戬",101321,63},
{"黄飞虎",101567,72},
{"纣王",108160,55},
{"李靖",102456,84},
{"土行孙",10224,65}};
printf("输入的学生信息为：\n");
for(i=0;i<12;i++)
{ printf("%s, %ld, %2d\n", mission[i].name, mission[i].number, mission[i].score);
}
bstnode* T;
T=creatbst(mission,m);
printf("\n深度优先——中序遍历：\n"); inorder(T); printf("\n");
printf("\n广度优先遍历：\n"); layer(T); printf("\n");
printf("\n请输入需要查询的学生信息：\n");
scanf_s("%s", z,50);
findpreorder(T, z);
printf("\n请输入需要查询的学生分数线以上名单：\n");
scanf_s("%d", &c);
findscore(T, c);
}