C语言二叉排序树是什么，如何创建和操作？
导读：这篇文章我们来了解C语言二叉排序树的相关内容，下文将介绍二叉排序树（二叉查找树）的概念、二叉排序树的判别、二叉排序树的创建、插入、删除等内容，对大家学习和理解二叉排序树有一定的帮助，有需要的朋友可以参考，接下来就跟随小编来一起学习一下吧！...
这篇文章我们来了解C语言二叉排序树的相关内容，下文将介绍二叉排序树（二叉查找树）的概念、二叉排序树的判别、二叉排序树的创建、插入、删除等内容，对大家学习和理解二叉排序树有一定的帮助，有需要的朋友可以参考，接下来就跟随小编来一起学习一下吧！
一、二叉排序树（二叉查找树）的概念
（1）若左子树非空，则左子树上所有结点的值均小于根节点的值
（2）若右子树非空，则右子树上所有结点的值均大于根节点的值
（3）左右子树分别也是一棵二叉排序树
tip：可以是一棵空树
二、二叉排序树的判别
（1）因为二叉排序树的中序遍历是一个有序递增序列，可以对已经建立的二叉树进行中序遍历，如果满足则判断是
三、二叉排序树的创建（creat、insert）
树结点的结构体：
struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
}
;
//递归创建结点
void Creat(int a,tree* &
T){
if(T==NULL){
T=new tree;
T->
data=a;
T->
lchild=NULL;
T->
rchild=NULL;
}
else if(a>
T->
data){
Creat(a,T->
rchild);
}
else{
Creat(a,T->
lchild);
}
}
//传入数组，一次性插入
void Insert(tree* &
T,int A[],int len){
for(int i=0;
i=len;
i++){
Creat(A[i],T);
}
}
四、二叉排序树的插入
//查找指定结点(输出当前结点是否存在)，如果没有就插入
void find(tree* &
T,int a){
tree* K=T;
//T指针指向二叉排序树的根节点，K为工作指针
tree* pre;
//pre指向当前工作指针的上一个结点，用于插入确定插入位置
while(K!=NULL&
&
a!=K->
data){
if(a>
K->
data){
pre=K;
K=K->
rchild;
}
else{
pre=K;
K=K->
lchild;
}
}
if(K==NULL){
tree* P;
//工作指针
P=new tree;
P->
data=a;
if(P->
data>
pre->
data){
pre->
rchild=P;
P->
lchild=NULL;
P->
rchild=NULL;
}
else{
pre->
lchild=P;
P->
lchild=NULL;
P->
rchild=NULL;
}
cout"不存在，已插入 "a" 这个结点"endl;
}
else{
cout"存在"endl;
}
}
五、二插排序树的删除
//删除某一结点，若不存在则提示
//①当该结点是叶子结点时，直接删除
//②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
//③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置
void delect(tree* &
T,int a){
//首先找到要删除的结点
tree* Pre;
tree* P=T;
//定义工作指针
while(P!=NULL&
&
a!=P->
data){
//这两个判定条件不能颠倒
if(a>
P->
data){
Pre=P;
P=P->
rchild;
}
else{
Pre=P;
P=P->
lchild;
}
}
if(P==NULL){
cout"要删除的结点不存在"endl;
}
else{
// ①当该结点是叶子结点时，直接删除
if(P->
lchild==NULL&
&
P->
rchild==NULL){
if(P->
data>
Pre->
data){
Pre->
rchild=NULL;
}
else{
Pre->
lchild=NULL;
}
cout"已删除 "aendl;
}
//②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
if((P->
lchild!=NULL&
&
P->
rchild==NULL)||(P->
rchild!=NULL&
&
P->
lchild==NULL)){
if(P->
data>
Pre->
data){
if(P->
lchild!=NULL){
Pre->
rchild=P->
lchild;
}
else{
Pre->
rchild=P->
rchild;
}
}
if(P->
dataPre->
data){
if(P->
lchild!=NULL){
Pre->
lchild=P->
lchild;
}
else{
Pre->
lchild=P->
rchild;
}
}
cout"已删除 "aendl;
}
//③当左右孩子都存在时找中序遍历的下一个（或上一个结点）结点代替其位置 (讨巧一点用前驱的最后一个结点)
if(P->
lchild!=NULL&
&
P->
rchild!=NULL){
tree* q;
tree* s;
q=P;
s=P->
lchild;
while(s->
rchild) //在结点p的左子树中继续查找其前驱结点,即最右下结点
{
q=s;
s=s->
rchild;
//向右到尽头
}
P->
data=s->
data;
//结点s中的数据顶替被删结点p中的
if(q!=P) //重新连接结点q的右子树
q->
rchild=s->
lchild;
else //重新连接结点q的左子树
q->
lchild=s->
lchild;
delete(s);
//释放s
}
cout"已删除 "aendl;
}
}
六、完整代码（可以运行）
#includeiostream>
using namespace std;
struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
}
;
//建立创建，传入一个完整的数组
void Creat(int a,tree* &
T){
if(T==NULL){
T=new tree;
T->
data=a;
T->
lchild=NULL;
T->
rchild=NULL;
}
else if(a>
T->
data){
Creat(a,T->
rchild);
}
else{
Creat(a,T->
lchild);
}
}
//传入数组，一次性插入
void Insert(tree* &
T,int A[],int len){
for(int i=0;
i=len;
i++){
Creat(A[i],T);
}
}
//中序遍历
void midorder(tree* T){
if(T!=NULL){
midorder(T->
lchild);
coutT->
data" ";
midorder(T->
rchild);
}
}
//查找指定结点(输出当前结点是否存在)，如果没有就插入
void find(tree* &
T,int a){
tree* K=T;
//T指针指向二叉排序树的根节点，K为工作指针
tree* pre;
//pre指向当前工作指针的上一个结点，用于插入确定插入位置
while(K!=NULL&
&
a!=K->
data){
if(a>
K->
data){
pre=K;
K=K->
rchild;
}
else{
pre=K;
K=K->
lchild;
}
}
if(K==NULL){
tree* P;
//工作指针
P=new tree;
P->
data=a;
if(P->
data>
pre->
data){
pre->
rchild=P;
P->
lchild=NULL;
P->
rchild=NULL;
}
else{
pre->
lchild=P;
P->
lchild=NULL;
P->
rchild=NULL;
}
cout"不存在，已插入 "a" 这个结点"endl;
}
else{
cout"存在"endl;
}
}
//删除某一结点，若不存在则提示
//①当该结点是叶子结点时，直接删除
//②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
//③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置
void delect(tree* &
T,int a){
//首先找到要删除的结点
tree* Pre;
tree* P=T;
//定义工作指针
while(P!=NULL&
&
a!=P->
data){
//这两个判定条件不能颠倒
if(a>
P->
data){
Pre=P;
P=P->
rchild;
}
else{
Pre=P;
P=P->
lchild;
}
}
if(P==NULL){
cout"要删除的结点不存在"endl;
}
else{
// ①当该结点是叶子结点时，直接删除
if(P->
lchild==NULL&
&
P->
rchild==NULL){
if(P->
data>
Pre->
data){
Pre->
rchild=NULL;
}
else{
Pre->
lchild=NULL;
}
cout"已删除 "aendl;
}
//②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
if((P->
lchild!=NULL&
&
P->
rchild==NULL)||(P->
rchild!=NULL&
&
P->
lchild==NULL)){
if(P->
data>
Pre->
data){
if(P->
lchild!=NULL){
Pre->
rchild=P->
lchild;
}
else{
Pre->
rchild=P->
rchild;
}
}
if(P->
dataPre->
data){
if(P->
lchild!=NULL){
Pre->
lchild=P->
lchild;
}
else{
Pre->
lchild=P->
rchild;
}
}
cout"已删除 "aendl;
}
//③当左右孩子都存在时找中序遍历的下一个（或上一个结点）结点代替其位置 (讨巧一点用前驱的最后一个结点)
if(P->
lchild!=NULL&
&
P->
rchild!=NULL){
tree* q;
tree* s;
q=P;
s=P->
lchild;
while(s->
rchild) //在结点p的左子树中继续查找其前驱结点,即最右下结点
{
q=s;
s=s->
rchild;
//向右到尽头
}
P->
data=s->
data;
//结点s中的数据顶替被删结点p中的
if(q!=P) //重新连接结点q的右子树
q->
rchild=s->
lchild;
else //重新连接结点q的左子树
q->
lchild=s->
lchild;
delete(s);
//释放s
}
cout"已删除 "aendl;
}
}
int main(){
tree* T=NULL;
int A[]={
23,89,65,12,17,3,9,90,21,63,71}
;
Insert(T,A,10);
midorder(T);
delect(T,89);
midorder(T);
find(T,89);
midorder(T);
return 0;
}
总结
关于c语言二叉排序树创建及一些操作方法就介绍到这，上述示例具有一定的借鉴价值，感兴趣的朋友可以参考，希望能对大家和理解c语言二叉排序树有帮助，想要了解更多c语言的内容，大家可以关注其它的相关文章。
文本转载自脚本之家
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： C语言二叉排序树是什么，如何创建和操作？
本文地址： https://pptw.com/jishu/655293.html