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

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树。二叉树查找需要先生成一个二叉排序树,再遍历所有节点逐一比较其值与关键字是否相同,相同则返回;若一直找不到,则返回-1。

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

C#算法设计概述

二叉树查找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

分析

在最坏的情况下二叉树查找的时间复杂度为:O(n) ,在平均情况下的时间复杂度为: O(logn)

AlgorithmMan

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

下载链接:AlgorithmMan-BinaryTreeSort

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/706

发表评论

登录后才能评论