defsucc(x): if x.right isnotNone: return tree_min(x.right) p = x.parent while p isnotNoneand p.left != x: x = p p = p.parent return p defpred(x): if x.left isnotNone: return tree_max(x.left) p = x.parent while p isnotNoneand p.right != x: x = p p = p.parent return p
node* left; node* right; node* parent; //parent is optional,it's helpful for succ/pred T key; };
// in-order tree walk // easy implemented by using functional approach template<classT,classF> voIDin_order_walk(node<T>* t,Ff){ if(t){ in_order_walk(t->left,f); f(t->key); in_order_walk(t->right,f); } }
template<classT> node<T>* succ(node<T>* x){ if(x){ if(x->right) return min(x->right); //find an ancestor,whose left child contains x node<T>* p = x->parent; 大专栏 [初等算法]--树 while(p && p->right==x){ x = p; p = p->parent; } return p; } return0; }
template<classT> node<T>* pred(node<T>* x){ if(x){ if(x->left) return max(x->left); //find an ancestor,whose right child contains x node<T>* p = x->parent; while(p && p->left==x){ x = p; p = p->parent; } return p; } return0; }
template<classT> node<T>* insert(node<T>* tree,Tkey){ node<T>* root(tree); node<T>* x = new node<T>(key); node<T>* parent(0); while(tree){ parent = tree; if(key < tree->key) tree = tree -> left; else//assert there is no duplicated key inserted. tree = tree -> right; } x->parent = parent; if( parent == 0 ) //tree is empty return x; elseif( key < parent->key) parent->left = x; else parent->right = x; return root; }
// cut the node off the tree,then delete it. // it can prevent dtor removed children of a node template<classT> voIDremove_node(node<T>* x){ if(x) x->left = x->right = 0; delete x; }
// The algorithm described in Clrs isn't used here. // I used the algorithm as below (refer to Annotated STL,P 235 (by Hou JIE) // if x has only one child: just splice x out // if x has two children: use min(right) to replace x // @return root of the tree template<classT> node<T>* del(node<T>* tree,node<T>* x){ if(!x) return tree;
voIDtest_in_order_walk(){ std::cout<<"ntest in order walk with print functor: "; in_order_walk(tree,Print()); //this can be simplifIEd by using boost //using namespace boost::lambda; //in_order_walk(tree,std::cout<<_1<<","); }
voIDtest_del(){ test_del_n(17); test_del_n(7); test_del_n(6); test_del_n(15); test_del_n(1); //try to del a non-exist val } private: node<int>* tree; };
评论列表(0条)