二叉树排序:
左< 根< 右
#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)或者修改此节点的右子树添加到左子树上