与链表、堆栈和队列不一样，二叉查找树不是线性数据结构，是二维数据结构。每个节点都包含一个LeftNode和RightNode，二叉查找树把比节点数据项小的数据放在LeftNode,把比节点数据项大的数据放在RightNode。
关于节点的类。
publicclassTreeNode<T>
{
publicT Element {get;set; }
publicTreeNode<T> LeftNode {get;set; }
publicTreeNode<T> RightNode {get;set; }
publicTreeNode(T element)
{
this.Element = element;
LeftNode = RightNode =null;
}
publicoverridestringToString()
{
stringnodeString = "[" +this.Element + "";
if(this.LeftNode ==null&&this.RightNode ==null)
{
nodeString += "(叶节点)";
}
if(this.LeftNode !=null)
{
nodeString += "左节点：" +this.LeftNode.ToString();
}
if(this.RightNode !=null)
{
nodeString += "右节点：" +this.RightNode.ToString();
}
nodeString += "]";
returnnodeString;
}
}
以上，把比节点数据项Element小的数据所在节点赋值给LeftNode，把比节点数据项Element大的数据所在节点赋值给RightNode。
创建一个泛型二叉树查找类，维护着一个根节点，并提供各种对节点的操作方法。
publicclassBinarySearchTree<T>
{
publicTreeNode<T> Root {get;set; }
publicBinarySearchTree()
{
this.Root =null;
}
//把某个数据项插入到二叉树
publicvoidInsert(T x)
{
this.Root = Insert(x,this.Root);
}
//把某个数据项从二叉树中删除
publicvoidRemove(T x)
{
this.Root = Remove(x,this.Root);
}
//删除二叉树中的最小数据项
publicvoidRemoveMin()
{
this.Root = RemoveMin(this.Root);
}
//获取二叉树中的最小数据项
publicT FindMin()
{
returnElemntAt(FindMin(this.Root));
}
//获取二叉树中的最大数据项
publicT FindMax()
{
returnElemntAt(FindMax(this.Root));
}
//获取二叉树中的某个数据项
publicT Find(T x)
{
returnElemntAt(Find(x,this.Root));
}
//清空
publicvoidMakeEmpty()
{
this.Root =null;
}
//判断二叉树是否为空，是否存在
publicboolIsEmpty()
{
returnthis.Root ==null;
}
//获取某个节点的数据项
PRivateT ElemntAt(TreeNode<T> t)
{
returnt ==null?default(T) : t.Element;
}
/// <summary>
/// 查找节点
/// </summary>
/// <param name="x">要查找数据项</param>
/// <param name="t">已存在的节点</param>
/// <returns>返回节点</returns>
privateTreeNode<T> Find(T x, TreeNode<T> t)
{
while(t !=null)//当没有找到匹配数据项，不断调整查找范围，即t的值
{
if((xasIComparable).CompareTo(t.Element) < 0)
{
t = t.LeftNode;
}
elseif((xasIComparable).CompareTo(t.Element) > 0)
{
t = t.RightNode;
}
else//如果找到数据项，就返回当前t的值
{
returnt;
}
}
returnnull;
}
//获取最小的节点，
privateTreeNode<T> FindMin(TreeNode<T> t)
{
if(t !=null)
{
while(t.LeftNode !=null)//不断循环二叉树的左半边树
{
t = t.LeftNode;//不断设置t的值
}
}
returnt;
}
//获取最大的节点
privateTreeNode<T> FindMax(TreeNode<T> t)
{
if(t !=null)
{
while(t.RightNode !=null)
{
t = t.RightNode;
}
}
returnt;
}
/// <summary>
/// 插入节点
/// </summary>
/// <param name="x">要插入的数据项</param>
/// <param name="t">已经存在的节点</param>
/// <returns>返回已存在的节点</returns>
protectedTreeNode<T> Insert(T x, TreeNode<T> t)
{
if(t ==null)
{
t =newTreeNode<T>(x);
}
elseif((xasIComparable).CompareTo(t.Element) < 0)
{
//等号右边的t.LeftNode是null，因此会创建一个TreeNode实例给t.LeftNode
t.LeftNode = Insert(x, t.LeftNode);
}
elseif((xasIComparable).CompareTo(t.Element) > 0)
{
t.RightNode = Insert(x, t.RightNode);
}
else
{
thrownewException("插入了相同元素~~");
}
returnt;
}
//删除最小的节点
//返回当前根节点
protectedTreeNode<T> RemoveMin(TreeNode<T> t)
{
if(t ==null)
{
thrownewException("节点不存在~~");
}
elseif(t.LeftNode !=null)
{
//通过递归不断设置t.LeftNode，直到t.LeftNode=null
t.LeftNode = RemoveMin(t.LeftNode);
returnt;
}
else//当t.LeftNode=null的时候，就把t.RightNode当作最小节点返回
{
returnt.RightNode;
}
}
//删除某数据项，返回当前根节点
protectedTreeNode<T> Remove(T x, TreeNode<T> t)
{
if(t ==null)
{
thrownewException("节点不存在~~");
}
elseif((xasIComparable).CompareTo(t.Element) < 0)
{
t.LeftNode = Remove(x, t.LeftNode);
}
elseif((xasIComparable).CompareTo(t.Element) > 0)
{
t.RightNode = Remove(x, t.RightNode);
}
elseif(t.LeftNode !=null&& t.RightNode !=null)
{
t.Element = FindMin(t.RightNode).Element;
t.RightNode = RemoveMin(t.RightNode);
}
else
{
t = (t.LeftNode !=null) ? t.LeftNode : t.RightNode;
}
returnt;
}
publicoverridestringToString()
{
returnthis.Root.ToString();
}
}
客户端创建二叉查找树的实例，并调用实例方法插入随机数据。BinarySearchTree<int> intTree =newBinarySearchTree<int>();
Random r =newRandom(DateTime.Now.Millisecond);
stringtrace = "";
//插入5个随机数
for(inti = 0; i < 5; i++)
{
intrandomInt = r.Next(1, 500);
intTree.Insert(randomInt);
trace += randomInt + "";
}
Console.WriteLine("最大的节点：" + intTree.FindMax());
Console.WriteLine("最小的节点：" + intTree.FindMin());
Console.WriteLine("根节点：" + intTree.Root.Element);
Console.WriteLine("插入节点的依次顺序是：" + trace);
Console.WriteLine("打印树为：" + intTree);
Console.ReadKey();
参考资料：
Binary Search Trees (BSTs) in C#
“了解集合本质必须要知晓的概念”系列包括：
了解集合本质必须要知晓的概念01-链表了解集合本质必须要知晓的概念02-堆栈了解集合本质必须要知晓的概念03-队列了解集合本质必须要知晓的概念04-二叉查找树