数据结构实验-二叉排序树应用实验报告

七、附录

源代码：

#include #include #include #define ElemType char

typedef struct BiTNode { ElemType data[30]; //定义数据域类型为字符数组

struct BiTNode *lchild, *rchild; //定义左右孩子节点指针 }BiTNode, *BiTree;

int SearchBST(BiTree T, char *key, BiTree f, BiTree *p) {

if (!T) // 树为空，查找不成功 {

*p = f; return 0; }

else if(strcmp(key,T->data)==0) // 查找成功 {

*p = T; //p指向查找到的节点 return 1; }

else if (strcmp(key,T->data)<0)

return SearchBST(T->lchild, key, T, p); // 在左子树中继续查找 else

return SearchBST(T->rchild, key, T, p); // 在右子树中继续查找

}

int InsertBST(BiTree *T, char *key) {

BiTree p,s;

if (!SearchBST(*T, key, NULL, &p)) // 查找不成功 {

s = (BiTNode*)malloc(sizeof(BiTNode));//s作为插入节点 strcpy(s->data, key);

s->lchild = s->rchild = NULL; if (!p)

*T = s; // 插入s为新的根结点 else if (strcmp(key,p->data)<0)

p->lchild = s; // 插入s为左孩子 else

p->rchild = s; // 插入s为右孩子 return 1; } else

return 0; // 树中已有关键字相同的结点，不再插入 }

int Search(BiTNode *N,char *key)

{ // 查找树中是否存在要插入的节点 BiTNode *M; M=N;

while(M!=NULL&&strcmp(M->data,key)!=0)

{ // 查找终止条件为树为空或者查找的节点数据与待查找的数据相同 if(strcmp(M->data,key)<0)

M=M->rchild; // 继续查找左子树 else

M=M->lchild; // 继续查找右子树 } if(!M)

printf(\查找失败！\\n\ else

printf(\查找成功！\\n\}

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */ int Delete(BiTree *p) {

BiTree q,s;

if((*p)->rchild==NULL) // 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) {

q=*p; *p=(*p)->lchild; free(q); // 释放该节点 }

else if((*p)->lchild==NULL) // 只需重接它的右子树 {

q=*p;

*p=(*p)->rchild; free(q); // 释放该节点 }

else // 左右子树均不空 {

q=*p;

s=(*p)->lchild;

while(s->rchild) // 转左，然后向右到尽头（找待删结点的前驱) {

q=s;

s=s->rchild; }

strcpy((*p)->data,s->data); // s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） if(q!=*p)

q->rchild=s->lchild; // 重接q的右子树 else

q->lchild=s->lchild; //重接q的左子树 free(s); }

return 1; }

int DeleteBST(BiTree *T,char *key) {

if(!*T) //不存在关键字等于key的数据元素 return 0; else {

if (strcmp(key,(*T)->data)==0) //找到关键字等于key的数据元素 return Delete(T); //调用Delete函数删除该节点 else if (strcmp(key,(*T)->data)<0)

return DeleteBST(&(*T)->lchild,key);// 继续访问左子树 else

return DeleteBST(&(*T)->rchild,key);//继续访问右子树