简介
二叉查找树有一个很有用的特性：小节点在父节点的左下层，大节点在父节点的右下层。利用这个特性，我们能够很容易的实现查找算法。
实现
要构建二叉树，首先要定义树节点结构。一般来说，树节点有三个字段。1.节点数据 2.左子节点 3. 右子节点。这样不难实现定义:
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
left = null;
right = null;
}
public void DisplayNode()
{
Console.Write(data + " ");
}
}
接下来，我们要实现树结构。首先，树结构必须有一个字段表示根节点，这作为整棵树的起始点。然后有一个插入节点的函数。
先来熟悉一下插入步骤的描述：
1.把父节点设置为当前节点，即根节点。
2.如果新节点内的数据值小于当前节点内的数据值，那么把当前节点设置为当前节点的左子节点。如果新节
点内的数据值大于当前节点内的数据值，那么就跳到步骤 4。
3.如果当前节点的左子节点的数值为空（null），就把新节点插入在这里并且退出循环。否则，跳到 while 循
环的下一次循环操作中。
4.把当前节点设置为当前节点的右子节点。
5.如果当前节点的右子节点的数值为空（null），就把新节点插入在这里并且退出循环。否则，跳到 while 循
环的下一次循环操作中。
代码描述：
public void Insert(int num)
{
//新建待插入节点
TreeNode node = new TreeNode(num);
//空树
if (root == null)
root = node;
else
{
//index用作循环指针
TreeNode index = root;
//用来储存当前节点
TreeNode current;
//遍历二叉树
while (true)
{
//获取前一轮的节点，然后判断index指针的左右是否符合条件
current = index;
if (num < index.data)
{
//因为要多赋值一轮，所以要设置index来储存遍历节点
index = index.left;
if (index == null)
{
current.left = node;
break;
}
}
else
{
index = index.right;
if (index == null)
{
current.right = node;
break;
}
}
}
}
}
我们讨论树，不可避免的会讨论到树的前、中、后序遍历。所谓的前中后，我们可以这么记：父节点出现的时机。
递归描述：
//中序递归遍历BST
public void MiddleOrder(TreeNode node)
{
if (node != null)
{
MiddleOrder(node.left);
node.DisplayNode();
MiddleOrder(node.right);
}
}
//先序遍历
public void FrontOrder(TreeNode node)
{
if (node != null)
{
node.DisplayNode();
FrontOrder(node.left);
FrontOrder(node.right);
}
}
//后序遍历
public void BackOrder(TreeNode node)
{
if (node != null)
{
BackOrder(node.left);
BackOrder(node.right);
node.DisplayNode();
}
}
之所以说二叉查找树找最大最小值很方便是因为，最小值只要在左子树找，最大值只要在右子树找。这个时间复杂度等于折半查找的时间复杂度O(lgN)。
//找最小值，只在左子树中找
public int FindMin()
{
TreeNode current = root;
while (current.left != null)
current = current.left;
return current.data;
}
