二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树。
二叉树查找需要先生成一个二叉排序树，再遍历所有节点逐一比较其值与关键字是否相同，相同则返回；若一直找不到，则返回-1。
示例：
public class BSTNode {
public int Key { get; set; }
public int Index { get; set; }
public BSTNode Left { get; set; }
public BSTNode Right { get; set; }
public BSTNode(int key, int index) {
Key = key;
Index = index;
}
public void Insert(int key, int index) {
var tree = new BSTNode(key, index);
if (tree.Key <= Key) {
if (Left == null) {
Left = tree;
}
else {
Left.Insert(key, index);
}
}
else {
if (Right == null) {
Right = tree;
}
else {
Right.Insert(key, index);
}
}
}
public int Search(int key) {
//找左子节点
var left = Left?.Search(key);
if (left.HasValue && left.Value != -1) return left.Value;
//找当前节点
if (Key == key) return Index;
//找右子节点
var right = Right?.Search(key);
if (right.HasValue && right.Value != -1) return right.Value;
//找不到时返回-1
return -1;
}
}
public class Program {
public static void Main(string[] args) {
int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
Console.WriteLine(BinaryTreeSearch(array));
Console.ReadKey();
}
public static int BinaryTreeSearch(int[] array) {
var bstNode = new BSTNode(array[0], 0);
for (int i = 1; i < array.Length; i++) {
bstNode.Insert(array[i], i);
}
return bstNode.Search(80);
}
}
在最坏的情况下二叉树查找的时间复杂度为：O(n) ，在平均情况下的时间复杂度为： O(logn) 。
