本文共 1583 字，大约阅读时间需要 5 分钟。

二叉搜索树，也叫二叉查询树，它的优势，顾名思义，就在于查询。一般在链表或者向量中查询一个元素，需要$O(n)$ 的时间复杂度，而对于搜索二叉树，最好情况可以仅用$O(lgn)$ 的复杂度。因此它善于大量数据的检索。

二叉搜索树与一般的二叉树不同在于它的元素分布，有如下特点： 对于每个结点，左子树（如果存在）的关键字大小小于该节点的关键字，右子树（如果存在）的关键字大于该结点的关键字大小。 在《算法导论》中，作者给出了二叉搜索树的一些基本操作（查询、插入、删除等）的伪码，但没有明确说明构造方法(只有一种随机构造方法，使用不断插入新结点的操作构造二叉树）。这里我想了一些别的方法来构造：

假设输入的数据是一个整型向量

vector<int>data

树结点类：

class Ctree{    int key;    Ctree*left,*right,*parent;public:    Ctree(vector
   
    data);};
   

我们假设data已经被排序。而对于二叉搜索树来说，对它的中序遍历就是输出（从小到大）的关键字排序。

//中序遍历Ctree::walk(){    if(left)left->walk();    ShowKeyValue();    if(right)right->walk();}

因此似乎可以逆向思考，用遍历的顺序来构造。但这里存在一个问题。如下图：

如下是失败的思考：

根据二叉搜索树的定义，第三个结点放在2的右子树或者双亲都可以，为了构造更平衡的二叉树以获得更好的查询性能，这里可以额外使用一个变量记录二叉树的深度，使得每次构造都是从接近底部的地方生长。这个图中，放在右子树明显比放在双亲要好。 ——这里其实走进了一个误区。后来我突然明白：一种遍历序列是没有办法确定一颗二叉树的，如果按照这种思路，算法会很麻烦。 于是（经过一晚上睡觉之后，才突然想到的），应该用两种序列来确定二叉树。我们可以想到另外一种序列：先序遍历。而对已排序的数组有一种查询方法，叫二分查找法，就相当于先序遍历的序列。 假设向量长L，我们在L/2处（为奇数则向下取整）选取该元素，作为根节点的关键字，然后[0,L/2)的向量对左子树递归上过程，对[L/2,L)右子树递归如上过程，这样构造出的二叉搜索树是平衡的。 构造函数如下：

Ctree::Ctree(vector
   
    ::iterator p,int len){//假设初始的p不是空的 使用迭代器    key = p[len / 2];    if (len / 2 - 1 >= 0){        left = new Ctr(p, len / 2);    }    else{        left = nullptr;    }    if (len / 2 + 1 < len){        right = new Ctr(p+ len / 2 + 1, len/2);    }    else{        right = nullptr;    }   }
   

按如下方式使用：

vector
   
     vec = {
  1,2,3,4,5,6,7};Ctree ctr(vec.begin(),vec.size());
   

总结：

学习二叉树有一周时间了，很多细节操作都不甚明了。但我觉得对于其意义的理解更为重要。构造得越平衡的二叉树性能越好，许多操作的时间复杂度都接近了$log(n)$ ，这是二叉树在处理大量数据上的一大优势。 这里我只提到了最普通的二叉搜索树，而且没有考虑到插入删除对其平衡性的影响，只单论其构造。要维持二叉树的动态平衡，必须要加其他特性来约束。比如红黑树、AVL树，就是为了二叉树的平衡而提出的。