- /*
- function: It is a test for studying
- platform: unix,linux
- */
- #include <stdio.h>
- #include <stdlib.h>
- #define ARRAYLEN 10
- //int source[]={54,90,6,69,12,37,92,67,28,65,85,80,83,86,84,87};
- //int source[]={15,21,23,25,30,31,37,41,45,49,56,58,60,72};
- int source[]={19,21,30,31,37,41,45,49,56,58,60,72};
- typedef struct bst{
- struct bst *left,*right;
- int data;
- }BSTree,*bst_t;
- //void insertBST(BSTree *t,int key)//在二叉树排序树中插入查找关键字key
- void insertBST(BSTree *t,int key)//在二叉排序树中插入查找关键字key
- {
- //s1 new node insert to BST
- BSTree *p,*parent,*head;
- if( !(p=(BSTree*)malloc(sizeof(BSTree))) )//申请内存空间
- {
- printf("申请内存出错!\\n");
- exit(-1);
- }
- p->data=key;//保存节点数据
- p->left=p->right=NULL;//左右子树置空
- head=t;//非递归式
- while(head!=NULL)//查找需要添加的父节点
- {
- parent=head;
- if(key < head->data)//若关键字小于节点的数据
- head=head->left;//在左子树查找
- else //若关键字大于节点的数据
- head=head->right;//在右子树中查找
- }
- //判断添加到左子树还是右子树
- if(key < parent->data)//小于父节点
- parent->left=p; //添加到左子树
- else
- parent->right=p;//添加到右子树
- }
- BSTree *searchBST(BSTree* t,int key)
- {
- if(!t ||t->data==key)//节点为空,或关键字相等
- return t; //返回节点的地址
- else if(key > t->data)//关键字大于节点数据
- return (searchBST(t->right,key));
- else
- return (searchBST(t->left,key));
- }
- BSTree* searchBST2(BSTree* node,int key)
- {
- while(node&&key!=node->data)
- {
- if(key<node->data)
- node=node->left;
- else
- node=node->right;
- }
- return node;
- }
- BSTree* minimum(BSTree* node)
- {
- while(node->left !=NULL)
- {
- node=node->left;
- }
- return node;
- }
- //后继结点
- BSTree* bst_successor(BSTree *node)
- {
- if(node->right != NULL)
- return minimum(node);
- //BSTree *sucNode=node->parent
- }
- void createBST(BSTree* t,int data[], int n)//
- {
- int i;
- t->data=data[0];
- t->left=t->right=NULL;
- for(i=1; i<n;i++)
- insertBST(t,data[i]);
- }
- //void BST_LDR(BSTree *t) //中序遍历
- void BST_LDR(BSTree *t) //中序遍历
- {
- if(t)//树不为空,则执行如下操作
- {
- BST_LDR(t->left); //中序遍历左子树
- printf("%d ",t->data); //输出结点数据
- BST_LDR(t->right); //中序遍历右子树/
- }
- return;
- }
- bool mdelete(BSTree* p)
- {
- BSTree *q, *s;
- //该节点是叶子节点,直接删除
- if(!p->right&&!p->left)
- free(p);
- else if(!p->right)//右子树空则只能重接它的左子树
- {
- q=p->left;
- p->data = p->left->data;
- p->left=p->left->left;
- p->right=p->left->right;
- free(q);
- }
- else if(!p->left)//左子树空只需要重接它的右子树
- {
- q=p->right;
- p->data=p->right->data;
- p->left=p->right->left;
- p->right=p->right->right;
- free(q);
- }
- else //左右子树均为空
- {
- q=p;
- s=p->left;
- while(s->right)
- {
- q=s;
- s=s->right;
- }//转左,然后向右转到头
- p->data=s->data;//s指向被删除节点的"前驱"
- if(q!=p)
- q->right=s->left;//重接*q的右子树
- else
- q->left=s->left;//重接*q的左子树
- free(s);
- }
- return true;
- }
- bool BST_delete(BSTree *t,int key)
- {
- if(!t) //不存在关键字 等于key的数据元素
- return false;
- else
- {
- if(key==t->data)//找到关键字等于key的数据元素
- return mdelete(t);
- else if(key < t->data)
- return BST_delete(t->left,key);
- else
- return BST_delete(t->right,key);
- }
- }
- int main(int argc,char* argv[])
- {
- int N=sizeof(source)/sizeof(int);
- int key,i;
- BSTree bst,*pos;
- printf("原数据[%d]: ",N);
- for(i=0;i<N;i++)
- printf("%d ",source[i]);
- printf("\\n");
- createBST(&bst,source,N);
- printf("遍历二叉排序树:");
- BST_LDR(&bst);
- printf("\\n请输入删除节点:");
- scanf("%d",&key);
- BST_delete(&bst,key);
- BST_LDR(&bst);
- printf("\\n请输入查找的关键字:");
- scanf("%d",&key);
- pos=searchBST(&bst,key);
- if(pos)
- printf("查找成功!\\n");
- else
- printf("查找失败!\\n");
- getchar();
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/060620149726.html
来源: http://www.codesnippet.cn/detail/060620149726.html