C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)-创新互联
完整代码
分享名称:C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)-创新互联
当前路径:http://myzitong.com/article/dosojd.html
#include#includetypedef struct binode
{int data;
struct binode *lchild,*rchild;
}BiTNode,*BiTree;
//查找函数
//f指向T的parent,查找成功p指向该结点;不成功,返回访问的最后一个结点
int searchBST(BiTree T,int key, BiTree f, BiTree *p)
{if(T==NULL)
{*p= f;
return 0;
}
else if(key == T->data)
{*p=T;
return 1;
}
else if(key< T ->data)
{return searchBST(T->lchild, key, T,p);
}
else{return searchBST(T->rchild, key, T,p);
}
}
//插入节点(创建树)
int insertBST(BiTree *T,int key)
{BiTree p,s;
if(searchBST(*T,key,NULL,&p)==0) //查找不成功,不存在相等的结点
{s=(BiTree)malloc(sizeof(BiTNode));
s->data=key;
s->lchild=s->rchild=NULL;
if(!p)
*T=s; //树为空,则s为根节点
else if(key< p->data)
p->lchild=s;
else
p->rchild=s;
return 1;
}
else
return 0;
}
//删除
int Delete(BiTree *p)
{BiTree q,s;
if((*p)->rchild ==NULL) //只有左子树
{q=*p;
*p=(*p)->lchild;
free(q);
}
else if((*p)->lchild == NULL) //只有右子树
{q=*p;
*p=(*p)->rchild;
free(q);
}
else //左右子树均不为空
{q=*p; s=(*p)->lchild;
while (s->rchild) //找到被删结点的左子树的最右结点
{q=s; s=s->rchild;
}
(*p)->data = s->data; //此时s为被删结点的左子树的最右结点
if(q != *p) //q为s 的父亲结点,此时q不重合p,也就是s不是p的右孩子
q->rchild=s->lchild;
else //此时q和p重合,s为p的右孩子
q->lchild=s->lchild;
free(s);
}
return 1;
}
//递归找到结点
int deleteBST(BiTree *T, int key)
{if(*T==NULL)
return 0;
else
{if(key == (*T)->data)
{Delete(T);
return 1;
}
else if(key<(*T)->data)
return deleteBST(&(*T)->lchild,key);
else
return deleteBST(&(*T)->rchild,key);
}
}
void pre(BiTree T)
{if(T)
{printf("%d ",T->data);
pre(T->lchild);
pre(T->rchild);
}
}
int main()
{BiTree T=NULL;
int a[15]={3,6,1,8,2,7,4,5,66};
int i=0;
while(a[i]!='\0')
{insertBST(&T,a[i++]);
}
pre(T);
printf("\n1.插入节点 2.删除结点\n");
int f;int key;
scanf("%d",&f);
if(f==1)
{printf("请输入插入的数字\n");
scanf("%d",&key);
insertBST(&T,key);
pre(T);
}
else
{printf("请输入删除的数字\n");
scanf("%d",&key);
deleteBST(&T,key);
pre(T);
}
return 0;
}
二叉查找树的原理1、若左子树不为空,左子树上所有节点值小于 它根节点的值
2、若右子树不为空,右子树上所有节点值大于 它根节点的值
3、每个节点的左右子树也是二叉排序树
目的:提高查找、插入、删除关键字的速度(不是为了排序)
时间复杂度:由于查找性能取决于树的形态,所以在O(log2n)(二叉树的平均高度)~ O(n) (最坏情况:单链表)之间。
改进:AVL树(不断的修改树的形态) 链接: 二叉平衡树(AVL树)
查找不成功(不重复) ->插入
删除分为三种情况:
(1)为叶子结点 :直接删除
(2)无左、右子树:删除结点,接上孩子即可
(3)左、右子树都有:找需要删除结点的左子树的最右结点(或右子树的最左结点)替换此节点。因为左子树的最右结点和右子树的最左结点最接近根节点,所以用它替换。再把此节点的右或左子树接到此节点的父亲结点上。
通过递归的方式比较找到结点
查找需要为插入做准备,因此函数变量里有个指针。
参考资料:《大话数据结构》
如果文章有问题,请给我留言哦,谢谢!
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享名称:C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)-创新互联
当前路径:http://myzitong.com/article/dosojd.html