怎么在二叉树中插入一个新的节点？

二叉树节点的查找、插入、删除.用C语言做的，不懂的地方可以给我留言。希望对你有所帮助！

#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))

}

1、首先，需要定义红黑树的节点这样的结构。

2、定义结构的顺序。

3、然后，就能在这里定义的根节点的结构体。

4、此时，可以暂时这棵红黑树的根命名为rb_root。

5、这时，利用刚刚定义的红黑树节点定义新节点。

6、最后，我们便可以为其重新命名为RBRoot即可。

---