C语言数据结构二叉树数据插入

指定一个数据为二叉树的根，向二叉树中插入数据，（树的第一层）如果要插入的数据比树根的数据大，则放在该结点的右侧，如果要插入的数据比树根小，则放在该结点的左侧，（树的第二层）数据的存放规则与上面的一致。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

//创建结构体

typedef struct tree

{

int a;//存放数据

struct tree *l;//二叉树节点的左指针

struct tree *r;//二叉树节点的右指针

}r;

//声明一个插入函数s是二叉树的头节点，t是要插入到树中的节点

void cmp(r *s,r* t);

//创建节点的函数

r *creat()

{

r * s = (r *)malloc(sizeof(r));

if(NULL != s)

memset(s,0,sizeof(r));

return s;

}

//采用递归遍历的形式访问树中的每个节点，然后free

void destroy(r *r)

{

if(NULL == r)

return ;

destroy(r->l);

destroy(r->r);

free(r);//递归函数调用进行释放内存

}

//显示树中每个节点的数据

void show(r *r)

{

if(NULL == r)

return ;

look(r->l);

look(r->r);

printf("%d\t",r->a);//后续遍历

}

//向树中插入元素，s是树的根节点，t是要插入树中的节点

void insert(r *s,r* t)

{

if(t->a < (s->a) && s->l == NULL)//如果新节点中的树大于根节点中的树，并且根节点的左指针是NULL

{

s->l = t;//直接将该指针连接到根的左指针上

return ;//节点被连接到树上后就退出

}else if( t->a < (s->a) && NULL != s->l)//如果新节点中的树大于根节点中的树，并且根节点的左指针不是NULL

{

insert(s->l,t);//继续调用函数

}

if( t->a >= (s->a) && s->r == NULL)//如果新节点中的树小于根节点中的树，并且根节点的右指针是NULL

{

s->r = t;//直接将该指针连接到根的右指针上

return ;//节点被连接到树上后就退出

}else if(t->a >= (s->a ) && NULL != s->r)//如果新节点中的树小于根节点中的树，并且根节点的右指针不是NULL

{

insert(s->r,t);//继续调用函数直到将结点挂到该树上

}

}

void main()

{

r * root = creat();//创建根节点

root->a = 8;//给根节点一个初始值8

int s = 0;

while(1)

{

scanf("%d",&s);//键盘录入数据，然后将这些数据插入到树中

if(s == -1)//当输入-1时，结束输入

break;

r * pnew =creat();//对输入的每个数创建节点

pnew->a = s;//将输入的数赋值给创建的节点

insert(root,pnew);//将该节点插入进树中

}

show(root);//后续遍历书中所有的元素

destroy(root);//释放该树中所有的节点

}