#define MAXSIZE 100 typedef int KeyType; /*关键字类型*/ typedef struct { KeyType key; /*InfoType otherinfo;*/ }RedType; /*记录类型*/ typedef struct BiTNode { RedType data; struct BiTNode *lchild,*rchild; }BiTNode, *BiTree; /*动态查找表的二叉链表存储表示*/#include <stdio.h> #include <stdlib.h> #include <string.h> #include "search.h" BiTree Search_BST(BiTree T, KeyType key, BiTNode **parent) {/*在二叉排序树T上查找其关键字等于key的记录结点。若找到返回该结点指针，parent指向其双亲；否则返回空指针，parent指向访问路径上最后一个结点。*/ // 请在这里补充代码，完成本关任务 /********** Begin *********/ /********** End **********/ } void Insert_BST(BiTree *T, RedType r)/*若二叉排序树T中没有关键字为r.key的记录，则插入*/ { BiTNode *p,*q,*parent; parent=NULL; p=Search_BST(*T,r.key,&parent); /*查找*/ if(p) printf("BST中有结点r，无需插入\n"); else { p=parent; q=(BiTNode *)malloc(sizeof(BiTNode)); q->data=r; q->lchild=q->rchild=NULL; if(*T==NULL) *T=q; /*若T为空，则q为新的根*/ else if(r.key<p->data.key) p->lchild=q; else p->rchild=q; } } BiTree Create_BST( ) /*二叉排序树的构造*/ {/*输入若干记录的关键字（以-1标志结束），生成一棵BST，采用二叉链表存储，返回其根指针T*/ BiTree T; RedType r; T=NULL; /*建空树*/ scanf("%d",&r.key); while(r.key!=-1) { Insert_BST(&T, r); scanf("%d",&r.key); } return T; } void PreOrder(BiTree bt) /*先序遍历*/ { if(bt) { printf("%d ",bt->data.key); PreOrder(bt->lchild); PreOrder(bt->rchild); } } void InOrder(BiTree bt) /*中序遍历*/ { if(bt) { InOrder(bt->lchild); printf("%d ",bt->data.key); InOrder(bt->rchild); } 补充代码

/*后序遍历*/ void PostOrder(BiTree bt) { if(bt) { PostOrder(bt->lchild); PostOrder(bt->rchild); printf("%d ",bt->data.key); } } /*中序遍历的非递归算法*/ void InOrderTraverse(BiTree T) { BiTree p=T; SqStack S; InitStack(&S); while(p || !StackEmpty(S)) { if(p) { Push(&S, p); p=p->lchild; } else { Pop(&S, &p); printf("%d ",p->data.key); p=p->rchild; } } } /*在二叉排序树T中查找其关键字等于key的记录，若查找成功，删除该结点并返回1；否则返回0。*/ int Delete(BiTree *T,KeyType key) { if(!(*T)) return 0; /*空树*/ else { if(key==(*T)->data.key) /*找到了关键字等于key的结点*/ { DeleteNode(T); return 1; } else if(key<(*T)->data.key) return Delete(&(*T)->lchild,key); else return Delete(&(*T)->rchild,key); } } /*从二叉排序树中删除结点p，并重接它的左或右子树。*/ void DeleteNode(BiTree *p) { BiTree q; if(!(*p)->rchild) /*右子树空则只需重接它的左子树*/ { q=*p; *p=(*p)->lchild; free(q); } else if(!(*p)->lchild)/*左子树空则只需重接它的右子树*/ { q=*p; *p=(*p)->rchild; free(q); } else /*左右子树均不空*/ { q=*p; /*从右子树开始*/ BiTree s=(*p)->rchild; while(s->lchild) /*转左，找到最小值*/ { q=s; s=s->lchild; } (*p)->data=s->data; /*s指向被删结点的直接前驱*/ if(q!=*p) q->lchild=s->rchild; /*重接q的左子树*/ else q->rchild=s->rchild; /*重接q的右子树*/ free(s); } }