二叉查找樹（BST）

二叉查找樹、BST

二叉搜尋樹

時間複雜度與樹的高度成正比，理想情況下O(lgn)。

接口

除了樹的基本功能，二叉樹還可以擴充其他功能；接口如下：

/// <summary>
/// 二叉查找樹相關接口
/// </summary>
/// <typeparam name="T"></typeparam>
interface IBinarySearchTree<out T>
{
    /// <summary>
    /// 從樹中删除最小值
    /// </summary>
    void RemoveMin();
    /// <summary>
    /// 從樹中删除最大值
    /// </summary>
    void RemoveMax();
    /// <summary>
    /// 查找最小元素
    /// </summary>
    T FindMin();
    /// <summary>
    /// 查找最大元素
    /// </summary>
    T FindMax();
}
      

實作

public class BinarySearchTree<T> : BinaryTreeBase<T>, IBinarySearchTree<T> where T : IComparable<T>
{
    public BinarySearchTree() : base() { }

    // TODO
}
      

其他​​具體實作​​，同學們可根據BST的特點，自行補充完善。

應用

public void Test()
{
    var bst = new BinarySearchTree<int>();
    int[] values = new int[21] { 15, 25, 5, 12, 1, 16, 20, 9, 9, 7, 7, 7, -1, 11, 19, 30, 8, 10, 13, 28, 39 };

    values = values.Distinct().ToArray();

    bst.Insert(values);

    WsCommFunc.ConsoleWriteLine(bst.ToString(TraversalMode.LevelOrder));
    Console.WriteLine(TreeDrawer.DrawTree(bst));


    Console.Write("Contains(10): ");
    WsCommFunc.ConsoleWriteLine(bst.Contains(10));

    Console.Write("element>15: ");
    foreach (var item in bst.FindAll(s => s > 15))
    {
        WsCommFunc.ConsoleWrite(item + " ");
    }

    Console.Write("\r\nMin=-1: ");
    WsCommFunc.ConsoleWriteLine(bst.FindMin() == -1);

    Console.Write("Max=39: ");
    WsCommFunc.ConsoleWriteLine(bst.FindMax() == 39);

    Console.Write($"RemoveMin: ");
    bst.RemoveMin();
    WsCommFunc.ConsoleWriteLine(bst.ToString(TraversalMode.LevelOrder));

    Console.Write("RemoveMax: ");
    bst.RemoveMax();
    WsCommFunc.ConsoleWriteLine(bst.ToString(TraversalMode.LevelOrder));

    Console.Write("Min=1: ");
    WsCommFunc.ConsoleWriteLine(bst.FindMin() == 1);

    Console.Write("Max=30: ");
    WsCommFunc.ConsoleWriteLine(bst.FindMax() == 30);
    try
    {
        Console.Write($"Remove(1000): ");
        bst.Remove(1000);
        WsCommFunc.ConsoleWriteLine("OK");
    }
    catch (Exception)
    {
        WsCommFunc.ConsoleWriteLine("ERROR", ConsoleColor.Red);
    }

    Console.WriteLine(TreeDrawer.DrawTree(bst));
    var iter = bst.GetInOrderEnumerator();
    iter.MoveNext();
    iter.MoveNext();
    Console.Write("MoveNext,MoveNext=5: ");
    WsCommFunc.ConsoleWriteLine(iter.Current == 5);
}