Question

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

Answer 1

二叉树节点的查找、插入、删除.用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))；。

Answer 2

二叉树节点的查找、插入、删除.用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));
}