排序二叉树c++

实际删除节点的过程中移花截木，把数据交换，然后递归。

#include <iostream>
using namespace std;
struct BiTree{
int data;
BiTree *left;
BiTree * right;
BiTree(int x){
data=x;
left=right=NULL;
}
~BiTree(){
if(left) delete left;
if(right) delete right;
}
void add(BiTree* t){
if(t->data<data)
if(left)
left->add(t);
else
left=t;
else
if(right)
right->add(t);
else
right=t;
}
void in_order(){
if(left) left->in_order();
cout<<data<<" ";
if(right) right->in_order();
}
BiTree* del(){
// 分类一，叶子节点
if(left==NULL && right==NULL){
delete this;
return NULL;
}
//分类二，只有右子树
if(left==NULL){
BiTree* t=right;
right=NULL;
delete this;
return t;
}
//分类二，只有左子树
if(right==NULL){
BiTree* t=left;
left=NULL;
delete this;
return t;
}
//分类三 左孩子没有右孩子
if(left->right==NULL){
data=left->data;
left=left->del();
return this;
}
//分类三 左孩子有右孩子
BiTree* p=left;
while(p->right->right) p=p->right;
data=p->right->data;
p->right=p->right->del();
return this;
}
};
int main(){
int data[]={12,3,7,16,2,18,9,7,2,5,11};
BiTree* root=new BiTree(data[0]);
for(int i=1;i<sizeof(data)/sizeof(int);i++)
root->add(new BiTree(data[i]));
root->in_order();cout<<endl;
root=root->del();
root->in_order();cout<<endl;
return 0;
}

#分类删节点

分类一

• 删叶子结点

分类二 单侧有孩子

• 左侧有孩子

• 右侧有孩子

分类三 双侧有孩子

1左孩子没有右孩子

2左孩子有右孩子

原文地址：https://blog.csdn.net/qq_37755459/article/details/140204805

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！