#include <stdio.h>
#include <stdlib.h>
typedef int elemtype；
typedef struct Node
{
elemtype data；
struct Node *Lchild；
struct Node *Rchild；
}TreeNode；
typedef TreeNode *bt；
int
Search_data(TreeNode *t,TreeNode **p,TreeNode **q， elemtype x) //查找函数
{
int flag=0；
*p=NULL；
*q=t；
while(*q)
{
if (x>(*q)->data)
{
*p=*q；
*q=(*q)->Rchild；
}
else{
if (x<(*q)->data)
{
*p=*q；
*q=(*q)->Lchild；
}
else{
flag=1；
break；
}
}
}
return flag；
}
int
InsertNode(TreeNode **t,elemtype x) //插入函数
{
int flag =0；
TreeNode *q，*s；
TreeNode *p=*t；
if (，Search_data(*t，&p，&q,x))
{
s=(TreeNode *)malloc(sizeof(TreeNode))；
s->data=x；
s->Lchild=NULL；
s->Rchild=NULL；
flag=1；
if(，p) t=s；
else{
if(x>p->data)
p->Rchild=s；
else
p->Lchild=s；
}
}
return flag；
}
int
DeleteNode(TreeNode **t,elemtype x) //删除函数
{
int flag=0；
TreeNode *q，*s，**f；
TreeNode *p=*t；
if (Search_data(*t，&p，&q,x))
{
flag=1；
if(p==q) f=&(*t)；
else
{
f=&(p->Lchild)；
if(x>p->data)
f=&(p->Rchild)；
}
if(，q->Rchild)
*f=q->Lchild；
else{
if(，q->Lchild)
*f=q->Rchild；
else{
p=q->Rchild；
s=p；
while(p->Lchild){
s=p；
p=q->Lchild；
}
*f=p；
p->Lchild=q->Lchild；
if (s，=p)
{
s->Lchild=p->Rchild；
p->Rchild=q->Rchild；
}
}
}
free(q)；
}
return flag；
}
void
visit(bt t)
{
printf("%c"，t->data)；
}
TreeNode *
creat_Tree()
{
char ch；
bt t；
ch=getchar()；
if(ch==' ') return (NULL)；
else{
t=(TreeNode *)malloc(sizeof(TreeNode))；
t->data=ch；
t->Lchild=creat_Tree()；
t->Rchild=creat_Tree()；
printf("%x\n"，&t)；
return (t)；
}
}
void
mid_oderTree(bt t)
{
if (t，=NULL)
{
mid_oderTree(t->Lchild)；
visit(t)；
mid_oderTree(t->Rchild)；
}
}
int
count_leafTree(bt t)
{
int i；
if(t==NULL) return 0；
else
if(t->Lchild==NULL&&t->Rchild==NULL)
i=1；
else i=count_leafTree(t->Lchild)+
count_leafTree(t->Rchild)；
return i；
}
main()
{
TreeNode *t，*p，*q；
elemtype x；
x='M'；
printf("creat Tree:\n")；
//二叉树在遍历最后一个节点之后，遇到结束符结束建立树。
t=creat_Tree()；
printf("中根遍历树:\n")；
mid_oderTree(t)；
printf("\n中根序插入%c成功输出（是1否0）:%d\n"，x,InsertNode(&t,x))；
printf("插入%c后的查找成功输出（是1否0）:%d\n"，x,Search_data(t，&p，&q， x))；
printf("插入后的中根遍历树:\n")；
mid_oderTree(t)；
printf("\n删除%c成功输出（是1否0）:%d \n"，x,DeleteNode(&t,x))；
printf("删除后的中根遍历树:\n")；
mid_oderTree(t)；
printf("\n求树的叶子数:%d \n"，count_leafTree(t))；。
红黑树添加节点，我们一般在叶子节点添加红色，因为添加红色节点能更快的符合上面几条性质，比如，如果添加一个黑色节点，很容易就打破规则7，本来红黑树从任意节点到子节点的路径上都包含相同的 black 节点，但是如果这时候我们添加black 节点，那么这条规则就打破了，所以我们一般添加红色节点
所以如果叶子节点为黑色节点，我们添加红色节点没有问题，但是叶子节点是红色节点，那么久不满足性质6了，就需要做调整
所有就需要染色，就需要将，父节点染成黑色，祖父节点染成红色，然后进行旋转，进行左旋和右旋
如果添加节点出现上溢的情况，那么将这个节点的父节点和叔父节点染成黑色，然后把原来的父节点染成red，然后当做新添加的节点来处理,递归向上，如果到了根节点还是上溢，只需要将根节点染成 black
1.如果删除的为 red 节点，那么直接删除
如果删除 black 节点：
2.如果这个black 有两个red 节点，那么不用理会，因为删除这个black 节点之后，会有相应的red节点来顶替
拥有一个 red 节点的black 节点，和叶子black 节点，如下图
3.删除拥有一个 red 节点的 black 节点：
判定条件：用以替代的子节点为 red
删除这个 black 节点之后，将替代的子节点染成黑色即可
如果兄弟节点至少有一个 red 节点，那么就管兄弟借一个，此时可能会导致 B 树下溢，
如果兄弟节点没有一个 red 节点，那么就将 parent染成黑色，兄弟节点染成红色
如果 parent 为黑色，那么会导致下溢，只需要把parent当做被删除的节点就可以
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）