排序二叉树c++
排序二叉树c++
- 分类一
- 分类二 单侧有孩子
- 分类三 双侧有孩子
- 1左孩子没有右孩子
- 2左孩子有右孩子
实际删除节点的过程中移花截木，把数据交换，然后递归。
#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);elseleft=t;elseif(right)right->add(t);elseright=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;
}#分类删节点
分类一
- 删叶子结点
分类二 单侧有孩子
- 左侧有孩子
- 右侧有孩子