排序二叉樹是經常遇到的一個數據結構，相關的遞歸算法也是考察的重點。以下c++示例代碼作為相關總結和備份: [cpp] #include <iostream> using namespace std; typedef int T; //下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼（遞歸算法）： class bst { struct Node{ T data; Node* L; Node* R; Node(const T& d,Node* lp=NULL,Node* rp=NULL):data(d),L(lp),R(rp){} }; Node* root; int num; public: bst():root(NULL),num(0) {} void clear(Node* t){ if(t==NULL) return; clear(t->L); clear(t->R); delete t; t = NULL; } ~bst() { clear(root); } void clear(){ clear(root); num = 0; root = NULL; } bool empty(){ return root==NULL; } int size(){ return num; } T getRoot(){ if(empty()) throw "empty tree"; return root->data; } //LNR-Travel N(Node）、L(Left subtree）和R(Right subtree） void travel(Node* tree){ if(tree==NULL) return; travel(tree->L); cout << tree->data << ' '; travel(tree->R); } void travel(){ travel(root); cout << endl; } int height(Node* tree){ if(tree==NULL) return 0; int lh = height(tree->L); int rh = height(tree->R); return 1+(lh>rh?lh:rh); } int height(){ return height(root); } void insert(Node*& tree,const T& d){ if(tree==NULL) tree = new Node(d); else if(d < tree->data) insert(tree->L,d); else insert(tree->R,d); } void insert(const T& d){ insert(root,d); num++; } //Pass in the reference and return a reference for later write operation(such as modifiing data value) Node*& find(Node*& tree,const T& d){ if(tree==NULL) return tree; if(tree->data == d) return tree; if(d < tree->data) return find(tree->L,d); else return find(tree->R,d); } bool find(const T& d){ return find(root,d)!=NULL; } bool update(const T& od,const T& nd){ Node* p = find(root,od); if(p==NULL) return false; erase(od); insert(nd); return true; } bool erase(const T& d){ Node*& pt = find(root,d); if(pt==NULL) return false; combine(pt->L,pt->R); Node* p = pt; pt = pt->R; delete p; //don't forget to value the ptr as NULL p=NULL; num--; return true; } // A(9) // / \ // B(7) C(15) // / / \ // D(5) E(13)F(21) //spend some time to understand this func /*this function only works for combination after deleting one note. Not the case that any one item is added into the binary tree.*/ private: void combine(Node* lc,Node*& rc){ if(lc==NULL) return; if(rc==NULL) //if the right sibling is empty, then, the note item replace its parent. rc = lc; else combine(lc,rc->L);//always "Gua" the note item(lc) to the left(est) leaf of his right sibling(rc) } }; int _tmain(int argc, _TCHAR* argv[]) { //input and construct the BST bst b; cout << "input some integers:"; for(;;){ int n; cin >> n; b.insert(n); if(cin.peek()=='\n') break; } www.2cto.com //find the old value node, then delete it and replace with the node with new value for(;;){ cout << "input data pair:"; int od,nd; cin >> od >> nd; if(od == -1 && nd == -1) break; b.update(od,nd); } b.travel(); return 0; }
