|
//bin sort tree
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
void print(int *str, int len)
{
int i=1;
printf("==> str: ");
while(i<=len)
printf("%d ", str[i++]);
printf("\n");
}
typedef struct node{
int key;
struct node *lchild, *rchild;
}BSTNode;
typedef BSTNode *BSTree;
//前序遍历算法
void PreOrder(BSTree T)
{
if(T){
printf("%d ", T->key);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历算法
void InOrder(BSTree T)
{
if(T){
InOrder(T->lchild);
printf("%d ", T->key);
InOrder(T->rchild);
}
}
//后序遍历算法
void PostOrder(BSTree T)
{
if(T){
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%d ", T->key);
}
}
void printTree(BSTree p)
{
printf("\n InOrder : ");
InOrder(p);
printf("\n PreOrder : ");
PreOrder(p);
printf("\n PostOrder: ");
PostOrder(p);
printf("\n");
}
#if 1
//从二叉排序书中删除节点p，并重接它的左或右子树
void Del(BSTree *ptr)
{
BSTNode *p = *ptr;
BSTNode *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->key = s->key; //s指向被删节点的"前驱"
if(q!=p)q->rchild=s->lchild; //重接*q的右子树
else q->lchild = s->lchild; //重接*q的左子树
}
}
//若二叉排序树T中存在关键字等于key的数据元素时, 则删除该数据元素节点,
//并返回1, 否则返回0. 删除中序前驱
int DeleteBSTNode(BSTree *T, int key)
{
if(!T) return 0; //不存在关键字等于key的数据元素
else{
if(key == (*T)->key) Del(T); //找到关键字等于key的数据元素
else if(key < (*T)->key) DeleteBSTNode(&(*T)->lchild, key);
else DeleteBSTNode(&(*T)->rchild, key);
return 1;
}
}
#endif
//二叉排序树删除算法
//在二叉排序树*Tptr中删去关键字为key的结点, 删除中序后继
void DelBSTNode(BSTree *Tptr, int key)
{
BSTNode *parent=NULL, *p=*Tptr, *q, *child;
while(p){ //从根开始查找关键字为key的待删结点
if(p->key==key) break;//已找到,跳出查找循环
parent=p; //parent指向*p的双亲
p = (key < p->key) ? p->lchild : p->rchild; //在p的左或右子树中继续找
}
if(!p) return; //找不到被删结点则返回
q=p; //q记住被删结点*p
if(q->lchild && q->rchild) //*q的两个孩子均非空,故找*q的中序后继*p
for(parent=q,p=q->rchild; p->lchild; parent=p,p=p->lchild);
//现在情况(3)已被转换为情况(2),而情况(1)相当于是情况(2)中child=NULL的状况
child = (p->lchild) ? p->lchild : p->rchild;//若是情况(2),则child非空;否则child为空
if(!parent){ //*p的双亲为空,说明*p为根,删*p后应修改根指针
*Tptr=child; //若是情况(1),则删去*p后,树为空;否则child变为根
}else{ //*p不是根,将*p的孩子和*p的双亲进行连接,*p从树上被摘下
if(p==parent->lchild) //*p是双亲的左孩子
parent->lchild=child; //*child作为*parent的左孩子
else
parent->rchild=child; //*child作为 parent的右孩子
if(p!=q) //是情况(3),需将*p的数据复制到*q
q->key=p->key; //若还有其它数据域亦需复制
}
free(p); //释放*p占用的空间
}
//1: success 0: failed
int SearchBST(BSTree T, int key, BSTree f, BSTree *p)
{
if( !T ) {*p=f; return 0;} //查找不成功
else if(key == T->key) { *p=T; return 1;} //查找成功
else if(key < T->key) SearchBST(T->lchild, key, T, p); //左子树中继续查找
else SearchBST(T->rchild, key, T, p); //右子树中继续查找
return 0;
}
//二叉排序树插入新结点的递归算法
//当二叉排序树T中不存在关键字等于key的数据元素时, 插入key并返回1,否则返回0
int InsertBST2(BSTree *T, int key)
{
BSTree s, p;
if(!SearchBST(*T, key, NULL, &p)){ //查找不成功
s = (BSTree)malloc(sizeof(BSTNode));
s->key = key; s->lchild = s->rchild = NULL;
if(!p) *T=s; //被插节点s为新的根节点
else if(key < p->key) p->lchild = s; //被插节点s为左孩子
else p->rchild = s; //被插节点s为右孩子
return 1;
}else{
return 0;
}
}
//二叉排序树插入新结点的非递归算法
//若二叉排序树 *Tptr中没有关键字为key, 则插入, 否则直接返回
void InsertBST(BSTree *Tptr, int key)
{
BSTNode *f, *p=*Tptr; //p的初值指向根结点
while(p){ //查找插入位置
if(p->key==key) return;//树中已有key，无须插入
f=p; //f保存当前查找的结点
//若keykey, 则在左子树中查找, 否则在右子树中查找
p = (key < p->key) ? p->lchild : p->rchild;
}
p = (BSTNode *)malloc(sizeof(BSTNode));
p->key = key;
p->lchild = p->rchild=NULL; //生成新结点
if(*Tptr==NULL){ //原树为空
*Tptr=p; //新插入的结点为新的根
}else{ //原树非空时将新结点关p作为关f的左孩子或右孩子插入
if(key < f->key) f->lchild = p;
else f->rchild = p;
}
}
//二叉排序树的生成
//输入一个结点序列, 建立一棵二叉排序树, 将根结点指针返回
BSTree CreateBST(void)
{
BSTree T=NULL; //初始时T为空树
int key;
scanf(" %d", &key); //读人一个关键字
while(key){ //假设key=0是输人结束标志
//InsertBST(&T, key); //将key插入二叉排序树T
InsertBST2(&T, key);
scanf(" %d", &key); //读人下一关键字
}
return T; //返回建立的二叉排序树的根指针
}
void DeleteBST(BSTree T)
{
int key;
printf("input the key to delete: ");
scanf(" %d", &key); //读人一个关键字
while(key){ //假设key=0是输人结束标志
DeleteBSTNode(&T, key);
printf("input the key to delete: ");
scanf(" %d", &key); //读人下一关键字
}
return;
}
int main(void)
{
int len;
int a[20];
int i;
BSTree T=NULL; //初始时T为空树
char input[3] = {0};
while(1){
printf("input 'm' for manual OR string length (MAX: 20) for auto: ");
scanf(" %s", input);
fflush(stdin);
if(input[0] == 'm'){ //手动输入元素建立排序树
if(input[1] != 0) {memset(input, 0, 3); continue;}
T = CreateBST();
printTree(T);
DeleteBST(T);
memset(input, 0, 3);
continue;
}
//自动建立排序树
len = atoi(input);
if(len == 0) break;
//设置rand函数所用的启始种子值，以期每次产生的随机数序列均不相同。
srand(time(NULL));
i = 0;
while(i++ < len){//a[0] 为哨岗
a[i] = rand() % 100;
printf("%d ", a[i]);
}
putchar('\n');
//a[1] = 5; a[2] = 3; a[3] = 8; a[4] = 2;
//a[5] = 4; a[6] = 7;// a[7] = ; a[8] = ;
//a[9] = ; a[10] = ;
i = 0;
while(i++<len){ //假设key=0是输人结束标志
//InsertBST(&T, a[i]); //将key插入二叉排序树T
InsertBST2(&T, a[i]);
}
printTree(T);
memset(input, 0, 3);
}//while(1)
return 0;
}
|
