# C#算法设计查找篇之05-二叉树查找

C#算法设计概述

## 二叉树查找（Binary Tree Search）

• 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉排序树。

## 示例

```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));

}

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);
}

}```

`7`

## AlgorithmMan

AlgorithmMan by Iori，AlgorithmMan是使用C#开发的一套用于算法演示的工具。

(12)