修改后的二叉排 序树.doc

修改后的二叉排 序树#include #include #include #define EQ(a,b) (a)=(b)#define LT(a,b) (a) (b)#define LQ(a,b) (a)lchild);printf(%4d,T-data.key);InOrderTraverse(T-rchild); /*打印二叉树*/*Status PrintTree(BiTree T,int n)if(T=NULL)return FALSE;PrintTree(T-rchild,n+1);for(int i=0;idata.key);PrintTree(T-lchild,n+1); return TRUE; */*二叉排序树的插入*/Status InsertBST(BiTree &T,KeyType key)BiTree s; if(!T)s=(BiTree)malloc(sizeof(BitNode);s-data.key=key;s-lchild=s-rchild=NULL;T=s;else if LT(key,T-data.key)InsertBST(T-lchild,key);else InsertBST(T-rchild,key);return TRUE;/*二叉排序树的查找*/BiTree SearchBST(BiTree T,KeyType key)if(!T)printf(Can not find!n);return T;else if EQ(key,T-data.key)return T;else if LT(key,T-data.key) return SearchBST(T-lchild,key); else return SearchBST(T-rchild,key);/*二叉排序树的删除*/Status Delete(BiTree &p)BiTree q,s;if(!p-rchild)/没有右孩子q=p;p=p-lchild;free(q);else if(!p-lchild)/没有左孩子q=p;p=p-rchild;free(q);else/两个孩子都有q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild;p-data=s-data;if(q!=p) q-rchild=s-lchild;else q-lchild=s-lchild;delete s;return TRUE;Status DeleteBST(BiTree &T,KeyType key)if(!T)return FALSE;elseif (EQ(key,T-data.key)return Delete(T);elseif(LT(key,T-data.key)return DeleteBST(T-lchild,key);else return DeleteBST(T-rchild,key);int main() BiTree T;/BiTree b1,b2;KeyType key;printf(创建二叉排序树n);printf(Input every key(0 to quit):);CreateBST(T);while(true) printf(Press enter to continue.); getchar(); getchar(); system(cls); Print(T);return 0;void Print(BiTree T)int choice;printf(1:中序遍历排序树n);printf(2:查找结点n);printf(3:中序遍历n);printf(4:插入结点n);printf(5:删除结点n);printf(0:退出n);printf(请选择要进行的操作:);scanf(%d,&choice);Choose(choice,T);void Choose( int choice ,BiTree &T)BiTree b2;KeyType key;int t;switch(choice)case 1: InOrderTraverse(T);break;case 2:printf(Input the key to search:);scanf(%d,&key);if(SearchBST(T,key)printf(把 key 为根的子树进行中序遍历：);b2=SearchBST(T,key);/把 key 为根的子树打印出来 InOrderTraverse(b2); else if (!SearchBST(T,key) InsertBST(T, key); printf(将key插入后并中序遍历二叉排序树); InOrderTraverse(T); break;case 3:InOrderTraverse(T);break;case 4:printf(输入要插入的数据：);scanf(%d,&key); if(SearchBST(T,key) printf(has the same number); else if(InsertBST(T, key)printf(n插入完毕！n);else printf(插入失败n);printf(中序遍历二叉排序树n);InOrderTraverse(T);break;case 5:printf(输入要删除的数据：);scanf(%d,&key);if(DeleteBST(T, key)printf(n删除完毕！n);els