怎么百度都百不到用非递归算法创建树~? 是不是非递归不比递归好~?
怎么百度都百不到用非递归算法创建树~? 是不是非递归不比递归好~? 程序代码:
/* * Author: Devil Wang * Data: 01-21-2010 * Notes: Template For Binary Tree */ #ifndef __BINTREE_H_ #define __BINTREE_H_ #include<iostream> #include<cstdlib> using std::cin; using std::cout; struct Exception{}; template<class KeyType,class InfoType> struct TNode { KeyType key; InfoType info; TNode<KeyType,InfoType> *left; TNode<KeyType,InfoType> *right; TNode<KeyType,InfoType> *parent; TNode<KeyType,InfoType>():left(NULL),right(NULL),parent(NULL){} TNode<KeyType,InfoType>(KeyType val, InfoType infoval=0):key(val),left(NULL),right(NULL),parent(NULL) { info=infoval; } friend ostream & operator<<(ostream &out,TNode<KeyType,InfoType> &Node) { out<<Node.key; return out; } } ; template<class KeyType, class InfoType> class BinTree { private: TNode<KeyType,InfoType> *root; size_t Size; protected: TNode<KeyType,InfoType> *minimum( TNode<KeyType,InfoType> *point)const { TNode<KeyType,InfoType> *p=point; while( NULL != p->left ) { p=p->left; } try{ if( NULL == p ) throw Exception(); return p; }catch( Exception e ) { exit; } } TNode<KeyType,InfoType> * maximum(TNode<KeyType,InfoType> *point)const { TNode<KeyType,InfoType> *p=point; while( NULL != p->right ) { p=p->right; } try{ if( NULL == p ) throw Exception(); return p; }catch( Exception e ) { exit; } } int leafcont(TNode<KeyType,InfoType> *pointer ) { static int cont=0; if (NULL!=pointer) { leafcont(pointer->left); if(NULL== pointer->left && NULL==pointer->right) { cont++; } leafcont(pointer->right); return cont; } } void travel(TNode<KeyType,InfoType> *T)const { if( NULL!=T ) { travel(T->left); cout<<*T<<" "; travel(T->right); } return ; } public: BinTree<KeyType,InfoType>():root(NULL),Size(0){} BinTree<KeyType,InfoType>(int n):root(NULL),Size(0) { KeyType m; for(int i=0; i<n;i++) { cin>>m; BTinsert(m); } } ~BinTree() { TNode<KeyType,InfoType> *p; while( NULL != root->left || NULL != root->right) { p=minimum(root); BTDelete(p); } if( NULL !=root ) { delete root; } } void BTInsert(KeyType val) { if( NULL == root) { root=new TNode<KeyType,InfoType>(val); root->parent=root; Size++; return ; } else { TNode<KeyType,InfoType> *pr=root,*cur; cur=(root->key>val)?root->left:root->right; while( NULL != cur ) { pr=cur; cur=cur->key>val?cur->left:cur->right; } try{ if( NULL != cur ) throw Exception(); cur=new TNode<KeyType,InfoType> (val); cur->parent=pr; if( pr->key > val) pr->left=cur; else pr->right=cur; }catch( Exception()) { cout<<"Catch An Exception"<<endl; cout<<"BTInsert"<<endl; exit; } Size++; } } TNode<KeyType,InfoType> * BTSearch(KeyType val)const { TNode<KeyType,InfoType> * p=root; while( NULL != p && p->key!=val ) { p=(p->key>val)?p->left:p->right; } try { if( NULL == p ) throw Exception(); return p; }catch ( Exception e) { cout<<"Catch An Exception"<<endl; cout<<"BTSearch"<<endl; return NULL; } } TNode<KeyType,InfoType> *BTMaximum()const{return maximum(root);} TNode<KeyType,InfoType> *BTMinimum()const{return minimum(root);} size_t size() { return Size; } bool empty() { return Size==0; } TNode<KeyType,InfoType> *BTSuccessor( TNode<KeyType,InfoType> *pointer )const { try { TNode<KeyType,InfoType> *point=pointer; if( NULL == point || point== maximum(root)) { throw Exception(); } if ( NULL != point->right ) return point->right; TNode<KeyType,InfoType> *pr=point->parent; if( NULL == pr ) throw Exception(); while( NULL != pr && point==pr->right ) { point=pr; pr=pr->parent; } return pr; }catch( Exception e) { cout<<"Catch An Exception" <<endl; cout<<"BTSuccessor"<<endl; return NULL; } } TNode<KeyType,InfoType> * BTPredecessor(TNode<KeyType,InfoType> *pointer )const { try { TNode<KeyType,InfoType> *point=pointer,*pr; if( NULL == point || point == BinTree::minimum(root)) throw Exception(); if( NULL != point->left ) return point->left; pr=point->parent; while( pr->left == point && NULL != pr ) { point=pr; pr=pr->parent; } return pr; }catch ( Exception e ) { cout<<"Catch An Exception" <<endl; cout<<"BTPredecessor"<<endl; return NULL; } } void BTDelete( TNode<KeyType,InfoType> * z) { TNode<KeyType,InfoType> *x,*y; if ( NULL == z->left && NULL == z->right && z==z->parent ) { delete z; z=NULL; root=NULL; Size--; return ; } if( NULL==z->left || NULL == z->right ) y=z; else y=BinTree::BTSuccessor(z); if( NULL != y->left) x=y->left; else x=y->right; if ( NULL !=x ) x->parent=y->parent; if( y->parent==y) { root=x; x->parent=x; } else if (y== y->parent->left) y->parent->left=x; else y->parent->right=x; if( z!=y ) { z->key=y->key; z->info=y->info; } delete y; Size--; } void BTTravel() { travel(root); cout<<endl; } int BTLeafCont(){return leafcont(root);} }; #endif