
二叉树查找(Binary Tree Search)
二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
- 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
- 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
- 左、右子树也分别为二叉排序树。
二叉树查找需要先生成一个二叉排序树,再遍历所有节点逐一比较其值与关键字是否相同,相同则返回;若一直找不到,则返回-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); } }
以上是二叉树查找算法的一种实现,以下是这个案例的输出结果:
7
分析
在最坏的情况下二叉树查找的时间复杂度为: ,在平均情况下的时间复杂度为:
。
AlgorithmMan

AlgorithmMan by Iori,AlgorithmMan是使用C#开发的一套用于算法演示的工具。
下载链接:AlgorithmMan-BinaryTreeSort
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/706。
评论列表(1条)
[…] 该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflyin… […]