ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 二叉排序树

二叉排序树

原创 Linux操作系统 作者:tyoodz 时间:2012-04-08 14:52:51 0 删除 编辑
#include
#include

typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

bool 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->rchild, key, T, p);
else 
return SearchBST (T->lchild, key, T, p);
}


bool InsertBST (BiTree *T, int key)
{
BiTree s, p;
if (!SearchBST (*T, key, NULL, &p))
{
s = (BiTree) malloc (sizeof (BiTNode));
s->data = key;
s->rchild = s->lchild = NULL;
if (!p)
*T = s;
else if (key < p->data)
p->lchild = s;
else
p->rchild = s;
return 1;
}
else
return 0;
}


bool Delete (BiTree *p)
{
BiTree q, s;
if ((*p)->rchild == NULL)
{
q = *p; 
*p = (*p)->lchild;
free (q);
}
else if ((*p)->lchild == NULL)
{
q = *p;
*p = (*p)->rchild;
free(q);
}
else
{
q = *p;
s = q->lchild;
while (s ->lchild)
{
q = s;
s = s->lchild;
}
(*p)->data = s->data;
if ((*p)!=q)
q->rchild = s->lchild;
else
q->lchild = s->lchild;
free(s);
}
return 1;
}

bool DeleteBST (BiTree *T, int key)
{
if (!*T)
return 0;
else
{
if (key > (*T)->data)
return DeleteBST (&(*T)->rchild, key);
else if (key < (*T)->data)
return DeleteBST (&(*T)->lchild, key);
else
return Delete(T);
}
}

void InOrderTraverse(BiTree T) //ÖDDò±éàú
{
if (T == NULL)
return;
InOrderTraverse(T->lchild);
printf ("%d ", T->data);
InOrderTraverse(T->rchild);
}

int main ()
{
BiTree p;
int i;
int a [10] = {1,75,9,65,3,5,8,0,92,99};
BiTree T = NULL;
for (i = 0; i < 10; i++)
InsertBST (&T, a[i]);
printf ("%d\n", SearchBST (T, 0, NULL, &p) ); //2éÕò0
printf ("%d\n", p->data);
DeleteBST(&T, 1); //é¾3y1
InOrderTraverse(T);
return 0;
}

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/25361369/viewspace-720650/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 快速排序
下一篇: Python模拟抽象类
请登录后发表评论 登录
全部评论

注册时间:2011-05-16

  • 博文量
    55
  • 访问量
    72537