建立一颗二叉排序树，并删除该二叉排序树上的某个节点

设计并验证如下算法：而擦函数采用二叉链表结构表示，按输入的关键字序列建立一颗二叉排序树，并删除该二叉排序树上的某个节点。

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef int TElemType; int m,n; typedef struct BiTNode {//树节点的建立 TElemType data ;struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; int SearchBST(BiTree T,int key,BiTree f,BiTree &p){if(!T){p=f;return 0;}else if(key==T->data){p=T;return 1;}else if(key<T->data)return SearchBST(T->lchild,key,T,p);else return SearchBST(T->rchild,key,T,p); } int InsertBST(BiTree &T,TElemType e){BiTree p,s;if(!SearchBST(T,e,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;else if(e<p->data)p->lchild=s;elsep->rchild=s;return 1;}elsereturn 0; } int CeateBiTree(BiTree &T)//创建树 {TElemType ch;T=NULL;printf("请输入整数序列构建二叉排序树,以 0结束：\n");scanf("%d",&ch);while(ch!=0){// printf("请输入整数序列构建二叉排序树,以 0结束：\n");InsertBST(T,ch);printf("请输入整数序列构建二叉排序树,以 0结束：\n");scanf("%d",&ch);} } int 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;elseq->lchild=s->lchild;Delete(s);}return 1;} int deleBiTreeData(BiTree &T,TElemType key) {int flag=1;if(!T)return 0;else{if(key==T->data){flag=0;return Delete(T);}else if(key<T->data)return deleBiTreeData(T->lchild,key);elsereturn deleBiTreeData(T->rchild,key);}if(flag){printf("你要删除的结点值不存在：\n");} }int PreOrder(BiTree BT) {//递归先序遍历 if(BT){if(!(BT->data))return 0;printf("%3d ",BT->data);PreOrder(BT->lchild) ;PreOrder(BT->rchild);return 1;} } int main(){BiTree BT;TElemType ch; CeateBiTree(BT);printf("创建二叉排序树的先序遍历：\n");PreOrder(BT);printf("请输入你要删除的结点值：\n");scanf("%d",&ch) ;deleBiTreeData(BT, ch);printf("删除节点后二叉排序树的先序遍历：\n");PreOrder(BT);}

测试结果如下：

请输入整数序列构建二叉排序树,以 0结束： 45 请输入整数序列构建二叉排序树,以 0结束： 24 请输入整数序列构建二叉排序树,以 0结束： 53 请输入整数序列构建二叉排序树,以 0结束： 12 请输入整数序列构建二叉排序树,以 0结束： 37 请输入整数序列构建二叉排序树,以 0结束： 93 请输入整数序列构建二叉排序树,以 0结束： 0 创建二叉排序树的先序遍历：45 24 12 37 53 93 请输入你要删除的结点值： 24 删除节点后二叉排序树的先序遍历：45 12 37 53 93

 

总结

以上是生活随笔为你收集整理的建立一颗二叉排序树，并删除该二叉排序树上的某个节点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。