C++二叉查找树：Binary Search tree
二叉查找树默认左子树的值都比根节点小，右子树都比根节点大，这个定义排除了树中存在值相同节点的可能性。这便是二叉查找树称为一个用关键值KEY快速查找的工具。
二叉树类：
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;//记录节点个数};
1.插入一个节点; void(tree& t,Node* p)//在一棵树树中插入一个节点
if(空树),作为根结点插入
if(大于根节点值)，插入右子树
else 插入左子树
void myinsert(tree& t,Node* p)//在一棵树中插入一个节点{if(t == NULL)t = p;else if(p->data < t->data)myinsert(t->L,p);elsemyinsert(t->R,p);}
2.查找一个节点: tree& (tree& t,const T& d)//在一棵树中寻找节点d，，返回一个指向这个节点的指针。
if(t==NULL) return t;
if(t->data==d) return t;
if(d < t->data) return 左子树中查找
else return右子树查找
tree& myfind(tree& t,const T& d)//返回以d为根节点的子树的根指针{if(t==NULL)return t;else if(d==t->data) return t;//没找到else if(d<t->data) return myfind(t->L,d);//return 一定要带上else return myfind(t->R,d);}void tr
3.删除一个节点:void dele(tree& t,const T& d)
特殊：
叶子节点
单子节点
双子节点—->左右子树合并
1.找到这个节点，即返回指向这个节点的指针pn
2.备份一份指针p=pn
3.左右子树合并
4.Delete节点
5.节点数-1
bool dele(const T& d){//返回那个节点的根指针，另存一份//左右子树合并，根指针指向右子树，释放节点tree& t = myfind(d);if(t == NULL) return false;Node* p = t;if(t->L!=NULL) myinsert(t->R,t->L);t = t->R;delete p;–n;return true;}
4修改一个节点; void(const T& olddata,const T& newdata)
1,删掉这个节点
2.插入一个节点
void update(const T& olddata,const T& newdata){dele(olddata);myinsert(newdata);}5.遍历二叉树 //中根遍历
遍历左子树
遍历根节点
遍历右子树
void travel(const tree& t)const{if(t != NULL){travel(t->L);cout << t->data <<' ';travel(t->R);}}6.清空一棵树
先清左子树
在清右子树
delete根节点 void clean(tree& t)//清空一棵树{if(t!=NULL){clean(t->L);clean(t->R);delete t;t=NULL;}}7.求树的深度
int high(tree& t)const//求一棵树的高度{if(t == NULL) return 0;int lh=high(t->L);int rh=high(t->R);return 1+std::max(lh,rh);}
8.二叉树的层次遍历
1.如果是空树，over
2.创建队列，根节点进队
3 只要队列不为空，
3.1 出队一个元素
3.2访问其中数据
3.3左右非空子树入队
void prin(tree& t){if(!t) return;deque<tree> di;di.push_back(t);while(!di.empty()){tree& t=di.front();cout << t->data << ' ';if(t->L)di.push_back(t->L);if(t->R)di.push_back(t->R);}}加换行符，每层遍历加一个换行
1.如果是空树，over
2.创建队列，根节点进队，NULL进队
3 只要队列size>1，
3.1 出队一个元素
3.2如果是NULL，换行，NULL进队尾。continue
3.2访问其中数据
3.3左右非空子树入队
void print(tree& t ){if(t==NULL)return;deque<tree> di;//创建队列di.push_back(t);//根节点入队di.push_back(NULL);while(di.size()!=1)//只要非空{tree& t=di.front();//取出一个元素if(t==NULL){cout << endl;di.pop_front();di.push_back(NULL);continue;}cout << t->data << ' ';//访问数据di.pop_front();if(t->L)di.push_back(t->L);//左右子树非空节点入队if(t->R)di.push_back(t->R);}}
不义而富且贵，于我如浮云。
