目录

1.简介

2.性质

3.泛型声明

4.树的结构

5.查找

6.插入

7.遍历

8.删除

9.示例

1.简介

二叉排序树：顾名思义它是一颗具有一定访问顺序的二叉树，通过中序遍历可以得到一个有序的序列

2.性质

一颗二叉排序树可以是空树，当它是非空树时具有以下特性：

1）当它的左子树不为空时，所有左子节点的值均小于根节点的值

2）当它的右子树不为空时，所有右子节点的值均大于根节点的值

3）它的左右子树均为二叉排序树

3.泛型声明

泛型数据需实现IComparerSearch接口，GetCompareValue()返回值用于比较计算，如下：

// -------------------------------------------------------------------------------------
// 常用搜索算法（泛型）（仅支持int比较:GetCompareValue()）
// 泛型要实现IComparerSearch接口 示例如下：
//public class Data : IComparerSearch
//{
//    public int id; // 示例字段，可自定义
//
//    public int GetCompareValue()
//    {
//        return this.id;
//    }
//}
// -------------------------------------------------------------------------------------/// <summary>
/// 泛型查找需要实现此接口
/// </summary>
public interface IComparerSearch
{/// <summary>/// 获取参与排序比较的值/// </summary>int GetCompareValue();
}

4.树的结构

/// <summary>
/// 二叉树数据结构
/// </summary>
/// <typeparam name="T">实现了IComparerSearch接口的类/struct</typeparam>
public class BSTree<T> where T : IComparerSearch
{public T value;public BSTree<T> lChild;public BSTree<T> rChild;
}

二叉树数据结构包括左右子树节点，和用于存放泛型数据的value

二叉排序树的常用操作有：查找、插入、删除和遍历；如下我们逐一详解

5.查找

二叉排序树的查找返回两个参数：1.查找到的泛型数据；2.未查找到的可以插入的节点insertNode；

/// <summary>
/// 二叉排序树查找
/// </summary>
// <typeparam name="T">实现IComparerSearch的泛型数据</typeparam>
// <param name="root">二叉排序树的根节点</param>
// <param name="key">查找的值（同IComparerSearch的GetCompareValue()返回值相比较）</param>
// <param name="insertNode">未查找到的插入节点</param>
// <returns>查找到的泛型数据</returns>
public static T SearchBSTree<T>(BSTree<T> root, int key, out BSTree<T> insertNode) where T : IComparerSearch
{return SearchBSTree(root, root, key, out insertNode);
}private static T SearchBSTree<T>(BSTree<T> root, BSTree<T> node, int key, out BSTree<T> insertNode) where T : IComparerSearch
{if (root == null){insertNode = null;return default(T);}else if (node == null){// 未找到，如果有父节点则返回父节点insertNode = root;return default(T);}else if (node.value.GetCompareValue() == key){// 找到则返回当前节点insertNode = node;return node.value;}else if (node.value.GetCompareValue() > key)return SearchBSTree(node, node.lChild, key, out insertNode); // 左子树elsereturn SearchBSTree(node, node.rChild, key, out insertNode); // 右子树
}

6.插入

二叉排序树在插入时，首先会与当前节点的值做比较（根节点值为空则直接插入到根节点），等于返回（相同的值不会重复插入），小于则插入到此节点的左子树中，大于则插入到此节点的右子树中。如下图所示：依次将{ 66, 33, 77, 55, 88 } 插入到树中

如图所示，插入后生成一颗二叉排序树，当用中序遍历树时，则得到一个有序序列 ：{ 33，55，66，77，88 }

代码如下：

/// <summary>
/// 二叉排序树插入(相同的value不会重复插入)
/// </summary>
// <typeparam name="T">实现IComparerSearch的泛型数据</typeparam>
// <param name="root">二叉排序树的根节点</param>
// <param name="value">插入的泛型数据</param>
public static void InsertBSTree<T>(BSTree<T> root, T value) where T : IComparerSearch
{if (root.value == null){// 第一个元素插入根节点root.value = value;}else{BSTree<T> insertNode;// 树中不存在时插入（相同的value不会重复插入）if (SearchBSTree(root, value.GetCompareValue(), out insertNode) == null && insertNode != null){if (value.GetCompareValue() < insertNode.value.GetCompareValue()){// 插入左子树insertNode.lChild = new BSTree<T>();insertNode.lChild.value = value;}else{// 插入右子树insertNode.rChild = new BSTree<T>();insertNode.rChild.value = value;}}}
}

7.遍历

二叉排序树采用中序遍历即可获得一个有序序列，代码如下：

/// <summary>
/// 遍历(中序)二叉排序树并返回一个有序list（默认升序）
/// </summary>
/// <param name="root">二叉排序树的根节点</param>
/// <param name="isUp">true:升序；false：降序</param>
public static List<T> QueryBSTree<T>(BSTree<T> root, bool isUp = true) where T : IComparerSearch
{List<T> list = new List<T>();QueryBSTree(root, isUp, ref list);return list;
}private static void QueryBSTree<T>(BSTree<T> node, bool isUp, ref List<T> list) where T : IComparerSearch
{if (node == null)return;if (isUp){// 中序遍历(升序)QueryBSTree(node.lChild, isUp, ref list);list.Add(node.value);QueryBSTree(node.rChild, isUp, ref list);}else{// 降序QueryBSTree(node.rChild, isUp, ref list);list.Add(node.value);QueryBSTree(node.lChild, isUp, ref list);}
}

8.删除

二叉排序树的删除稍微复杂一些，分如下4中情况：

1）要删除的是叶子节点，则直接删除即可，如下图：

2）要删除的节点A（33）仅有左子树时，则将被移除节点A的左子树赋值给A的父节点的左子树，并移除A，如下图：

3）要删除的节点A（77）仅有右子树时，则将被移除节点A的右子树赋值给A的父节点的右子树，并移除A，如下图：

4）要删除的节点A同时存在左右子树时

此时比较简单的思路是：将节点A的左右子树中的一支（比如：右子树）作为替换节点，挂接在A的父节点下，并将A的另一支子树（左子树）下的所有节点重新插入到A的原右子树节点下；这是个比较笨的方法，思路比较简单，但是也很有可能增加数的深度，并且插入还增加了删除的成本

所以我们介绍另一种删除的思路：我们尝试找A的左右子树中某一个节点B来代替A，使得B替换A后，B也是一颗二叉排序树，并且不需要对左右子树节点进行重新插入；参见下图：

当我们要删除节点52时，可以选择左子树的最大值45，或是右子树的最小值58来代替52，并且替换后新节点也是一颗二叉排序树，这里我们以固定取左子树最大值来替换为例讲解，分以下两种情况：

1】要删除节点A（52）的左子树B（36）没有右子树时，则先将A（52）的右子树C（58）赋给B（36）的右子树，然后将B（36）赋给A（52）的父节点，如下图：

 2】要删除节点A（52）的左子树B（36）有右子树时，则循环找到最大的右子树节点C（45）用于替换A，并将节点C（45）的左子树D（39）赋给节点B（36）的右子树，如下图：

代码如下：

/// <summary>
/// 二叉排序树移除一个元素
/// </summary>
// <typeparam name="T">实现IComparerSearch的泛型数据</typeparam>
// <param name="key">查找的值（同IComparerSearch的GetCompareValue()返回值相比较）</param>
// <param name="root">二叉排序树的节点</param>
public static bool RemoveBSTree<T>(int key, ref BSTree<T> root) where T : IComparerSearch
{if (root == null)return false;// 找到需要移除的节点if (root.value.GetCompareValue() == key){if (root.lChild != null && root.rChild != null){// 左右子树都不为空（移除key对应的节点数据，并取左子树最大的节点作为新的节点数据替换）BSTree<T> coverNode = root.lChild;if (coverNode.rChild == null){// 左子树没有右子节点，则直接把左子树替换到移除位置coverNode.rChild = root.rChild;root = coverNode;}else{// 取左子树最大的节点作为新的节点数据替换BSTree<T> coverParent = root;while (coverNode.rChild != null){coverParent = coverNode;coverNode = coverNode.rChild;}if (coverNode.lChild != null)coverParent.rChild = coverNode.lChild;elsecoverParent.rChild = null;coverNode.lChild = root.lChild;coverNode.rChild = root.rChild;root = coverNode;}}else if (root.lChild != null){// 左子树不为空root = root.lChild;}else if (root.rChild != null){// 右子树不为空root = root.rChild;}else{// 左右子树均为空，移除当前节点即可root = null;}return true;}else if (key < root.value.GetCompareValue()){// 左子树查找return RemoveBSTree(key, ref root.lChild);}else{// 右子树查找return RemoveBSTree(key, ref root.rChild);}
}

9.示例

// 泛型数据结构
public class SearchData : IComparerSearch
{public int id;public int GetCompareValue(){return this.id;}public void Output(){Debug.Log($"id = {id}");}
}private List<SearchData> searchDataList = new List<SearchData>();
private Search.BSTree<SearchData> root = new Search.BSTree<SearchData>();private void Start()
{SearchExecute();
}private void SearchExecute()
{// 生成二叉排序树Search.ClearBSTree(root);root = new Search.BSTree<SearchData>();RandomInitSerachDataList(0, 100, 10);for (int i = 0; i < searchDataList.Count; i++){Search.InsertBSTree(root, searchDataList[i]);}OutputSerachDataList(searchDataList);// 查询并返回一个升序序列searchDataList = Search.QueryBSTree(root);OutputSerachDataList(searchDataList);
}// 删除序列中的一个随机数值
private void Remove()
{if (searchDataList == null || searchDataList.Count == 0)return;int index = UnityEngine.Random.Range(0, searchDataList.Count);int key = searchDataList[index].GetCompareValue();Debug.LogWarning($"[Remove] key = {key}");// 二叉排序树移除Search.RemoveBSTree(key, ref root);searchDataList = Search.QueryBSTree(root);OutputSerachDataList(searchDataList);
}// 随机生成maxCount个数据
private void RandomInitSerachDataList(int min, int max, int maxCount)
{SearchData data = null;searchDataList.Clear();for (int i = 0; i < maxCount; ++i){data = new SearchData();data.id = UnityEngine.Random.Range(min, max + 1);searchDataList.Add(data);}
}// 数据打印
private void OutputSerachDataList(List<SearchData> list)
{Debug.Log("----------------------------------------");for (int i = 0; i < list.Count; ++i){list[i].Output();}
}

随机生成5个数后的二叉排序树查询输出如下：