一遍快速搞清二叉排序树的构建

如何构建一颗二叉排序树

这个思路是用到了递归的。我们都知道，创建一颗二叉树可以通过递归完成。二叉排序树也是同样的思路，只是它不会由我们“手动”去设置结点该放左孩子还是右孩子，而是根据性质（左<根<右）插入结点。

这里以空树开始，创建一颗二叉排序树为例：

假设要求按照序列，将｛40，72，38，35，67，51｝建立一颗二叉排序树，则过程应该是这样的：

 如果说对于插入排序、冒泡排序这些叫做“稳定”的算法（稳定意思是说原本键值一样的元素排序后相对位置不变的时候），那么我想二叉排序树算是另一类的“稳定”（即每次插入结点后，位置不会再发生改变，我自创的---方便记忆吧）。

注意：假设有相同的值，则插不进去，会显示失败（要求结点的每个值具备唯一性）

二叉排序树的代码示例：

int BST_Insert(BiTree &T,KeyType k){
       
     if(T==NULL){               //原树为空，新插入的记录为根结点
  
          T=(BiTree)malloc(sizeof(BSTNode));
          T->data=k;
          T->lchild=T->rchild=NULL;
          return 1;       //返回1，表示插入成功
     ｝

      else if(k==T->data)  //树中存在相同关键字的结点，插入失败
            
          return 0;

      else if(k<T->data)   //小于，插入到T的左子树（递归）

          return BST_Insert(T->lchlid,k);  

      else if(k>T->data)   //大于，插入到T的右子树（递归）
         
          return BST_Insert(T->rchild,k);

}

预告

二叉排序树的查找算是非常简便的，其查找的次数跟树的深度有关。那么有没有可能存在一棵很深的二叉排序树呢，当然，像这样：

如果查5，那么可知失败查找次数就有4次，如果插100呢。。或者更多，那么很明显，这棵二叉排序就已经脱离了初衷了。

下一期，便是另一“进化神树”--平衡二叉树的闪亮登场，敬请期待！！！ 

（也祝各位程序员 1024 快乐！）