二叉树排序：
左< 根< 右
#include<iostream>
#include<string>
using namespace std;
//
typedef struct node{
struct node *left,*right;
int data;
}node_t;
template <typename T>
class Btree{
public:
Btree();
void Btree_create(T *_array, int number);
int Btree_search(T item);
void Btree_append(T item);
void Btree_remove(T item);
void Btree_sort_output(node_t *p);
virtual ~Btree();
node_t *head;
private:
// node_t *head;
int count;
};
template <typename T> Btree<T>::Btree(){
head=NULL;
count=0;
}
template <typename T> Btree<T>::~Btree(){
while(count>0){
Btree_remove(head->data);
}
head=NULL;
}
template <typename T> void Btree<T>::Btree_create(T* array,int number){
if(number<=0)
return;
int i=0;
node_t * temp;
node_t *par;
node_t *t;
int flag=0;
for(i=0;i<number;i++){
temp=new node_t;
temp->data=array[i];
temp->left=NULL;
temp->right=NULL;
if(head==NULL)
{// insert as the first item
head=temp;
}
else{// insert to the appropriate position
t=head;
while(t){
par=t;
if(array[i]<t->data){
t=t->left;
flag=1;
}
else{
flag=0;
t=t->right;
}
}
if(flag)
par->left=temp;
else
par->right=temp;
}
count++;
}
}
template<typename T> int Btree<T>::Btree_search(T item){
// search the item,return 1 if finding it, or o if not
node_t *t=head;
while(t){
if(t->data==item)
break;
if(item<t->data){
t=t->left;
}
else{
t=t->right;
}
}
if(t)
return 1;
else
return 0;
}
template<typename T> void Btree<T>::Btree_append(T item){
// insert to the appropriate position
node_t *temp;
temp=new node_t;
temp->data=item;
temp->left=NULL;
temp->right=NULL;
if(head==NULL)
{// insert as the first item
head=temp;
}
else{// insert to the appropriate position
node_t *par;
node_t *t=head;
int flag=0;
while(t){
par=t;
if(item<t->data){
t=t->left;
flag=1;
}
else{
flag=0;
t=t->right;
}
}
if(flag)
par->left=temp;
else
par->right=temp;
}
count++;
}
template<typename T> void Btree<T>::Btree_remove(T item){
// always remove the first found item if multiple itmes are found;
node_t *t=head;
node_t *par;
int flag=0;
if(!t){
cout<<" no items"<<endl;
return;
}
while(t){
if(t->data==item){
break;
}
if(item<t->data){
par=t;
t=t->left;
flag=1;
}
else{
par=t;
t=t->right;
flag=0;
}
}
if(!t){
cout<<"no found"<<endl;
return;
}
/* 9 10 5
/ \ / \ / \
NULL NULL 9 ... ,,, 9
/ \ / \
NULL NULL NULL NULL
we will delete 9
*/
if(t->left==NULL && t->right==NULL){
if(t==head){
head=NULL;
}
else{
if(flag) par->left=NULL;
else par->right=NULL;
}
}
/* 9 12 5
/ \ / \ / \
NULL 10 9 ... ,,, 9
/ \ / \
NULL 11 NULL 11
we will delete 9
*/
else if(t->left==NULL && t->right!=NULL){
if(t==head){
head=t->right;
}
else{
if(flag) par->left=t->right;
else par->right=t->right;
}
}
/* 9 12 5
/ \ / \ / \
4 NULL 9 ... ,,, 9
/ \ / \
4 NULL 7 NULL
we will delete 9
*/
else if(t->left!=NULL && t->right==NULL){
if(t==head){
head=t->left;
}
else{
if(flag) par->left=t->left;
else par->right=t->left;
}
}
/* 9 12 5 5
/ \ / \ / \ / \
4 12 9 ... ,,, 9 -> ... 7
/ \ / \ \
4 11 7 10 10
we will delete 9
*/
else{
if(t!=head){
if(flag) par->left=t->left;
else par->right=t->left;
}
else
head=t->left;
node_t* temp=t->left;
while(temp->right){
temp=temp->right;
}
temp->right=t->right;
}
count--;
delete t;
}
// mid-order sort and output
template<typename T> void Btree<T>::Btree_sort_output(node_t *p){
if(p==NULL)
return;
Btree_sort_output(p->left);
cout<<p->data<<" ";
Btree_sort_output(p->right);
}
void main(){
int A[10]={43,23,3,4,5,2,45,234,45,9};
Btree<int> *btree=new Btree<int>;
btree->Btree_create(A,10);
btree->Btree_sort_output(btree->head);
cout<<endl;
btree->Btree_append(1);
btree->Btree_append(7);
btree->Btree_sort_output(btree->head);
cout<<endl;
btree->Btree_remove(67);
btree->Btree_remove(43);
btree->Btree_sort_output(btree->head);
cout<<endl;
btree->Btree_remove(45);
btree->Btree_sort_output(btree->head);
cout<<endl;
delete btree;
}
删除方法：
删除节点
1. 左右孩子都为空，直接删除，修改父节点
2 . 只有左孩子为空，或者右孩子为空，修改父节点（左指针，或右指针)指向此节点的右孩子，或者左孩子。
3. 都不为空，
1）让此节点左子树上上的最大节点代替此节点
2） 或者让此节点右子树上的最小节点代替此节点
3）或者 修改此节点的左子树添加到右子树上
4）或者修改此节点的右子树添加到左子树上