二叉树
节点的查找、
插入、删除.用C语言做的，不懂的地方卖宽可粗兆以给我中凳亮留言。希望对你有所帮助！\x0d\x0a\x0d\x0a#include \x0d\x0a#include \x0d\x0a\x0d\x0atypedef int elemtype\x0d\x0atypedef struct Node\x0d\x0a{\x0d\x0aelemtype data\x0d\x0astruct Node *Lchild\x0d\x0astruct Node *Rchild\x0d\x0a}TreeNode\x0d\x0atypedef TreeNode *bt\x0d\x0a\x0d\x0aint\x0d\x0aSearch_data(TreeNode *t,TreeNode **p,TreeNode **q, elemtype x) //查找函数\x0d\x0a{\x0d\x0aint flag=0\x0d\x0a*p=NULL\x0d\x0a*q=t\x0d\x0a\x0d\x0awhile(*q)\x0d\x0a{\x0d\x0aif (x>(*q)->data)\x0d\x0a{\x0d\x0a*p=*q\x0d\x0a*q=(*q)->Rchild\x0d\x0a}\x0d\x0aelse{\x0d\x0aif (xdata)\x0d\x0a{\x0d\x0a*p=*q\x0d\x0a*q=(*q)->Lchild\x0d\x0a}\x0d\x0aelse{\x0d\x0aflag=1\x0d\x0abreak \x0d\x0a}\x0d\x0a}\x0d\x0a}\x0d\x0areturn flag\x0d\x0a}\x0d\x0a\x0d\x0aint\x0d\x0aInsertNode(TreeNode **t,elemtype x) //插入函数\x0d\x0a{\x0d\x0aint flag =0\x0d\x0aTreeNode *q,*s\x0d\x0aTreeNode *p=*t\x0d\x0a\x0d\x0aif (!Search_data(*t,&p,&q,x))\x0d\x0a{\x0d\x0as=(TreeNode *)malloc(sizeof(TreeNode))\x0d\x0as->data=x\x0d\x0as->Lchild=NULL\x0d\x0as->Rchild=NULL\x0d\x0aflag=1\x0d\x0aif(!p) t=s\x0d\x0aelse{\x0d\x0aif(x>p->data)\x0d\x0ap->Rchild=s\x0d\x0aelse\x0d\x0ap->Lchild=s\x0d\x0a}\x0d\x0a}\x0d\x0areturn flag\x0d\x0a}\x0d\x0a\x0d\x0aint\x0d\x0aDeleteNode(TreeNode **t,elemtype x) //删除函数\x0d\x0a{\x0d\x0aint flag=0\x0d\x0aTreeNode *q,*s,**f\x0d\x0aTreeNode *p=*t\x0d\x0a\x0d\x0aif (Search_data(*t,&p,&q,x))\x0d\x0a{\x0d\x0aflag=1\x0d\x0aif(p==q) f=&(*t)\x0d\x0aelse\x0d\x0a{\x0d\x0af=&(p->Lchild)\x0d\x0aif(x>p->data)\x0d\x0af=&(p->Rchild)\x0d\x0a}\x0d\x0a\x0d\x0aif(!q->Rchild)\x0d\x0a*f=q->Lchild\x0d\x0aelse{\x0d\x0aif(!q->Lchild)\x0d\x0a*f=q->Rchild\x0d\x0aelse{\x0d\x0ap=q->Rchild\x0d\x0as=p\x0d\x0awhile(p->Lchild){\x0d\x0as=p\x0d\x0ap=q->Lchild\x0d\x0a}\x0d\x0a*f=p\x0d\x0ap->Lchild=q->Lchild\x0d\x0a\x0d\x0aif (s!=p)\x0d\x0a{\x0d\x0as->Lchild=p->Rchild\x0d\x0ap->Rchild=q->Rchild\x0d\x0a}\x0d\x0a}\x0d\x0a}\x0d\x0afree(q)\x0d\x0a}\x0d\x0areturn flag\x0d\x0a}\x0d\x0a\x0d\x0avoid\x0d\x0avisit(bt t)\x0d\x0a{\x0d\x0aprintf("%c",t->data)\x0d\x0a}\x0d\x0a\x0d\x0aTreeNode *\x0d\x0acreat_Tree() \x0d\x0a{\x0d\x0achar ch\x0d\x0abt t\x0d\x0ach=getchar()\x0d\x0aif(ch==' ') return (NULL)\x0d\x0aelse{\x0d\x0at=(TreeNode *)malloc(sizeof(TreeNode))\x0d\x0at->data=ch\x0d\x0at->Lchild=creat_Tree()\x0d\x0at->Rchild=creat_Tree()\x0d\x0aprintf("%x\n",&t)\x0d\x0areturn (t)\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0avoid\x0d\x0amid_oderTree(bt t)\x0d\x0a{\x0d\x0aif (t!=NULL)\x0d\x0a{\x0d\x0amid_oderTree(t->Lchild)\x0d\x0avisit(t)\x0d\x0amid_oderTree(t->Rchild)\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0aint\x0d\x0acount_leafTree(bt t)\x0d\x0a{\x0d\x0aint i\x0d\x0aif(t==NULL) return 0\x0d\x0aelse\x0d\x0aif(t->Lchild==NULL&&t->Rchild==NULL)\x0d\x0ai=1\x0d\x0aelse i=count_leafTree(t->Lchild)+\x0d\x0acount_leafTree(t->Rchild)\x0d\x0areturn i\x0d\x0a}\x0d\x0a\x0d\x0amain()\x0d\x0a{\x0d\x0aTreeNode *t,*p,*q\x0d\x0aelemtype x\x0d\x0ax='M'\x0d\x0aprintf("creat Tree:\n")\x0d\x0a//二叉树在遍历最后一个节点之后，遇到结束符结束建立树。\x0d\x0at=creat_Tree()\x0d\x0aprintf("中根遍历树:\n")\x0d\x0amid_oderTree(t)\x0d\x0a\x0d\x0aprintf("\n中根序插入%c成功输出（是1否0）:%d\n",x,InsertNode(&t,x))\x0d\x0a\x0d\x0aprintf("插入%c后的查找成功输出（是1否0）：%d\n",x,Search_data(t,&p,&q, x))\x0d\x0aprintf("插入后的中根遍历树:\n")\x0d\x0amid_oderTree(t)\x0d\x0a\x0d\x0aprintf("\n删除%c成功输出（是1否0）：%d \n",x,DeleteNode(&t,x))\x0d\x0aprintf("删除后的中根遍历树:\n")\x0d\x0amid_oderTree(t)\x0d\x0a\x0d\x0aprintf("\n求树的叶子数:%d \n",count_leafTree(t))\x0d\x0a}
二叉排序树是一种二叉树，其每个节点都有一个值，并且满足以下条件：
左子树的所有节点的值均小于该节点的值
右子树的所有节点的值均大于该节点的值
左子树和右子树都是二叉排序树
基于上述性质，我们可以在二叉排序树上进行插入、查氏轮找和删除等 *** 作。
插入 *** 作
对于插入 *** 作，我们需要首先遍历二叉排序树，找到插入节点的位置。具体步骤如下：
如果二叉排序树为空，则新节点成为根节点
如果插入节点的值等于当前节点的值，则插入失败，结束 *** 作
如果插入节点的值小于当前节点的值，则在左子树中继续查找插入位置
如果插入节点的值大腔核轿于当前节点的值，则在右子树中继续查找插入位置
当找到插入位置时，创建一个新节点，将插入节点的值赋值给新节点，并将新节点插入到树中。
查找 *** 作
对于查找 *** 作，我们需要遍历二叉排序树，根据当前节点的值与目标值的大小关系，决定向左子树或右子树进行查找，直到找到目标值或者遍历到空节点为止。
删除 *** 作
对于删除 *** 作，我们需要遵循以下步骤：
首先，我伍肆们需要在二叉排序树中查找待删除节点。如果待删除节点不存在，则结束 *** 作
如果待删除节点没有子节点，我们直接将其从二叉排序树中删除
如果待删除节点只有一个子节点，我们将该子节点替换待删除节点
如果待删除节点有两个子节点，我们需要找到待删除节点的中序遍历的后继节点，将其替换待删除节点，然后删除后继节点
删除 *** 作涉及到的细节较多，需要对二叉排序树的性质进行仔细分析。
二叉树节点的查找、插入、删除.用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))；。
微信扫一扫
支付宝扫一扫
评论列表（0条）