二叉查找树（BST)、平衡二叉树(AVL树)

二叉查找树(BST)

　　特殊的二叉树，又称为排序二叉树、二叉搜索树、二叉排序树。

　　二叉查找树实际上是数据域有序的二叉树，即对树上的每个结点，都满足其左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。如下图所示：

二叉查找树通常包含查找、插入、建树和删除操作。

二叉查找树的创建

对于一棵二叉查找树，其创建与二叉树的创建很类似，略有不同的是，二叉查找树，为了保证整棵树都关于根结点的大小呈左小右大的特征，在创建时，需要根据当前结点的大小来判断插入位置，给出如下代码：

template<typename T> void BSTree<T>::createBSTreeByFile(ifstream &f){ T e; queue<BSNode<T>*> q; while(!f.eof()){ InputFromFile(f, e); Insert(root, e); } } template<typename T> void BSTree<T>::Insert(BSNode<T>* &t, T x){//得用指针的引用，不然传参时由于形参实例化，并不能成功创建二叉树 if(t==NULL){ t = new BSNode<T>; t->data = x; t->lchild = t->rchild = NULL; return; } if(x<=t->data){ Insert(t->lchild, x); } else{ Insert(t->rchild, x); } }