traversing binarytreefind delete updatedatasource.txt

二叉树的遍历、查找、删除、更新数据的代码

#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;
　　}
　　~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;
　　}
　　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(ddata)
　　insert(tree->L, d);
　　else
　　insert(tree->R, d);
　　}
　　void insert(const T& d){
　　insert(root, d);
　　num++;
　　}
　　Node*& find(Node*& tree, const T& d){
　　if(tree==NULL) return tree;
　　if(tree->data==d) return tree;
　　if(ddata)
　　return find(tree->L, d);
　　else
　　return find(tree->R, d);
　　}
　　bool find(const T& d){
　　return find(root, d)!=NULL;
　　}
　　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;
　　num--;
　　return true;
　　}
　　void combine(Node* lc, Node*& rc){
　　if(lc==NULL) return;
　　if(rc==NULL) rc = lc;
　　else combine(lc, rc->L);
　　}
　　bool update(const T& od, const T& nd){
　　Node* p = find(root, od);
　　if(p==NULL) return false;
　　erase(od);
　　insert(nd);
　　return true;
　　}
　　};
　　int main()
　　{
　　bst b;
　　cout << "input some integers:";
　　for(;;){
　　int n;
　　cin >> n;
　　b.insert(n);
　　if(cin.peek()=='\n') break;
　　}
　　b.travel();
　　for(;;){
　　cout << "input data pair:";
　　int od, nd;
　　cin >> od >> nd;
　　if(od==-1&&nd==-1) break;
　　b.update(od, nd);
　　b.travel();
　　}
　　}