#2
小苏苏2013-12-17 20:47
#include "stdio.h"
#include "stdlib.h" #include "string.h" #include "math.h" #define OK 1 #define FALSE 0 #define TRUE 1 typedef int KeyType; typedef int info; typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) typedef struct { KeyType key; //info otherinfo; }ElemType; /* 数据元素类型 */ typedef struct BiTNode { ElemType data; BiTNode *lchild,*rchild; // 左右孩子指针 }BiTNode,*BiTree; int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) {/* 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素,若查找 */ /* 成功,则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径上 */ /* 访问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL */ if(!T) /* 查找不成功 */ {p=f;return 0;} else if EQ(key,T->data.key) {p=T;return 1;} else if LT(key,T->data.key)/* 查找成功 */ SearchBST(T->lchild,key,T,p);/* 在左子树中继续查找 */ else SearchBST(T->rchild,key,T,p);/* 在右子树中继续查找 */ }//SearchBST Status InsertBST(BiTree &T,ElemType e) /* 当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE, */ { BiTree s,p; if(!SearchBST(T,e.key,NULL,p))/* 查找不成功 */ { s=(BiTree)malloc(sizeof(BiTNode)); s->data=e; s->lchild=s->rchild=NULL; if(!p) T=s;/* 被插结点*s为新的根结点 */ else if LT(e.key,p->data.key) p->lchild=s;/* 被插结点*s为左孩子 */ else p->rchild=s;/* 被插结点*s为右孩子 */ return TRUE; } else return FALSE; /* 树中已有关键字相同的结点,不再插入 */ }//InsertBST int Delete(BiTree &p) /* 从二叉排序树中删除结点p,并重接它的左或右子树。算法9.8 */ { BiTree q,s; if(!p->rchild) /* 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) */ { q=p; p=p->lchild; free(q); }//if else if(!p->lchild)/* 只需重接它的右子树 */ { q=p; p=p->rchild; free(q); }//else if else/* 左右子树均不空 */ { q=p; s=p->lchild; while(s->rchild)/* 转左,然后向右到尽头(找待删结点的前驱) */ {q=s; s=s->rchild; } p->data=s->data;/* s指向被删结点的"前驱"(将被删结点前驱的值取代被删结点的值) */ if(q!=p) q->rchild=s->lchild; /* 重接*q的右子树 */ else q->lchild=s->lchild;/* 重接*q的左子树 */ delete s; }//else return OK; }//Delete Status DeleteBST(BiTree &T,KeyType key) {/* 若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点, */ /* 并返回TRUE;否则返回FALSE。算法9.7 */ if(!T)/* 不存在关键字等于key的数据元素 */ return FALSE; else { if EQ(key,T->data.key) /* 找到关键字等于key的数据元素 */ return Delete(T); else if LT(key,T->data.key) return DeleteBST(T->lchild,key); else return DeleteBST(T->rchild,key); }//else }//DeleteBST int InsertBSTD(BiTree &T) /* 当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE, */ /* 否则返回FALSE。算法9.6(改) */ { ElemType e; printf("insert the data,until input -1:\n"); scanf("%d",&e.key ); while(e.key!=-1) { InsertBST(T,e); scanf("%d",&e.key); }//while return 1; }//InsertBSTD void PrintD(BiTree T) { if(T->lchild)PrintD(T->lchild); printf("->%d",T->data.key); if(T->rchild)PrintD(T->rchild); }//PrintD int DeleteBSTD(BiTree &T) { ElemType e; printf("\ninput the data you want to delete:\n"); scanf("%d",&e.key); DeleteBST(T,e.key); return 1; }//DeleteBSTD int main() { BiTree T; InsertBSTD(T); PrintD(T); DeleteBSTD(T); PrintD(T); return OK; } |
只有本站会员才能查看附件,请 登录