概念解释

树形结构---有n（n>=0）个结点的有限集，且满足如下条件：

1. 在非空树中有且仅有一个特定的称为根的结点

2. 当n>1时，其余结点可为m（m>0）个互不相交的有限集，每个集合本身是一棵树，称为根的子树

3. 树的结点包含一个数据元素及若干指向其子树的分支

结点拥有的子树数量称为结点的度。度为0的结点称为叶子（终端结点）。度不为0的结点称为分支结点（非终端结点）。

内部结点：除根结点以外的分支结点。

树的度是树内各结点的度的最大值。

结点的子树的根称为该结点的孩子。该结点称为孩子的双亲。同一个双亲的孩子之间称为兄弟。

结点的祖先是从根到该结点所经历的所有的结点。

以某结点为根的子树中的任一结点都称为该结点的子孙。

结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第L层，则其子树的根就在第L+1层，其双亲在同一层的结点

互为堂兄弟。树结点的最大层次为树的深度（高度）。如果将树中结点的各子树看成是从左到右有顺序的（即不能互换），则称该树为有序树，否则为无序树。

#include 
    
     using namespace std;typedef char T;class bst{	struct Node{		T data;		Node* L;		Node* R;		Node(const T& d):data(d),L(),R(){}		Node(const T& d,Node*l,Node*r):data(d),L(l),R(r){}	};	typedef Node* tree;	Node* rp;	int n;public:	bst():rp(),n(){}	void clear(){clear(rp);n=0;}	~bst(){clear();}	void insert(const T& d){insert(rp,new Node(d));++n;}	tree& find(const T& d){return find(rp,d);}	void travel()const{travel(rp);cout<
     
      L!=NULL) insert(t->R, t->L);		t = t->R;		delete p;		--n;		return true;	}	const T& root()const{if(!rp) throw"空";return rp->data;}	int size()const{return n;}	void update(const T& olddata,const T& newdata){		if(remove(olddata)) insert(newdata);	}	void insert(tree& t, Node* p){		if(t==NULL) t = p;		else if(p->data < t->data) insert(t->L,p);		else insert(t->R,p);	}	tree& find(tree& t, const T& d){//返回以d为根的子树的根指针		if(t==NULL) return t;//没找到		else if(d==t->data) return t;//找到了		else if(d
      
       data)	return find(t->L,d);		else return find(t->R,d);	}	void travel(tree t)const{		if(t!=NULL){			travel(t->L);			cout << t->data << ' ';			travel(t->R);		}	}	void clear(tree& t){		if(t!=NULL){			clear(t->L);			clear(t->R);			delete t; t=NULL;		}	}	int high(tree t){		if(t==NULL) return 0;		int lh = high(t->L);		int rh = high(t->R);		return 1+(lh>rh?lh:rh);	}};int main(){	bst b;	b.insert('k');b.insert('s');b.insert('f');b.insert('t');	b.insert('a');b.insert('m');b.insert('x');b.insert('e');	b.insert('w');b.insert('b');b.insert('u');b.insert('j');	b.travel();	b.remove('k');b.remove('m');b.remove('j');b.remove('u');	b.travel();	b.update('b','k');b.update('k','b');b.update('x','*');	b.travel();	while(!b.empty()) b.remove(b.root());	cout<<"size:"<
       
        <