二叉树


		排序二叉树是经常遇到的一个数据结构，相关的递归算法也是考察的重点。以下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  
    &n

补充：软件开发 , C++ ,