{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','http://www.shouhuola.com//data/attach/topic/topicCxE7eC.jpg', '推荐 抹茶落季 的文章《C# 二叉排序树》','http://www.shouhuola.com/article-52411.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
二叉排序树，又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：
若它的左子树不为空。则左子树上所有的结点的值均小于跟的结点值
若它的右子树部位空，则右子树的所有结点值均大于它的根结点的值
它的左右子树也分别是二叉排序树
1，排序方便
2，查找方便
3，便于插入和删除
C#链式存储二叉排序树，实现简单的排序，以及查找，，具体代码如下：
namespace _2_1_3二叉排序树
{
/// <summary>
/// 结点类
/// </summary>
class BSNode
{
//结点
public BSNode LeftChild { get; set; }
public BSNode RightChild { get; set; }
public BSNode Parent { get; set; }
public int Data { get; set; }
// 构造方法
public BSNode(){}
public BSNode(int item)
{
this.Data = item;
}
}
}
using System;
namespace _2_1_3二叉排序树
{
/// <summary>
/// 二叉排序树
/// </summary>
class BSTree
{
BSNode root = null;
/// <summary>
/// 添加数据
/// </summary>
public void Add(int item)
{
//创建新结点
BSNode newNode = new BSNode(item);
if (root == null) //若为空，则创建为根结点
{
root = newNode;
}
else
{
BSNode temp = root;
while (true)
{
if (item >= temp.Data) //放在temp结点的右边
{
if (temp.RightChild == null)
{
temp.RightChild = newNode;
newNode.Parent = temp;
break;
}
else
{
temp = temp.RightChild;
}
}
else //放在temp结点的左边
{
if (temp.LeftChild == null)
{
temp.LeftChild = newNode;
newNode.Parent = temp;
break;
}
else
{
temp = temp.LeftChild;
}
}
}
}
}
/// <summary>
/// 中序遍历二叉树
/// </summary>
public void MiddleBianli()
{
MiddleBianli(root);
}
//递归方式中序遍历树
private void MiddleBianli(BSNode node)
{
if (node == null) return;
MiddleBianli(node.LeftChild);
Console.Write(node.Data + " ");
MiddleBianli(node.RightChild);
}
/// <summary>
///查找方法-1
/// </summary>
public bool Find1(int item)
{
return Find(item, root);
}
private bool Find(int item, BSNode node)
{
if (node == null) { return false; }
if (node.Data == item)
{
return true;
}
else
{
//利用二叉排序树的便利
if (item > node.Data)
{
return Find(item, node.RightChild);
}
else
{
return Find(item, node.LeftChild);
}
}
}
/// <summary>
/// 查找方法-2
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Find2(int item)
{
BSNode temp = root;
while (true)
{
if (temp == null) return false;
if (temp.Data == item) return true;
if (item > temp.Data)
{
temp = temp.RightChild;
}
else
{
temp = temp.LeftChild;
}
}
}
public bool Delete(int item)
{
BSNode temp = root;
while (true)
{
if (temp == null) return false;
if (temp.Data == item)
{
Delete(temp);
return true;
}
if (item > temp.Data)
{
temp = temp.RightChild;
}
else
{
temp = temp.LeftChild;
}
}
}
public void Delete(BSNode node)
{
//叶子结点，即无子树情况
if (node.LeftChild == null && node.RightChild == null)
{
if (node.Parent == null)
{
root = null;
}
else if (node.Parent.LeftChild == node)
{
node.Parent.LeftChild = null;
}
else if (node.Parent.RightChild == node)
{
node.Parent.RightChild = null;
}
return;
}
//只有右子树的情况
if (node.LeftChild == null && node.RightChild != null)
{
node.Data = node.RightChild.Data;
node.RightChild = null;
return;
}
//只有左子树的情况
if (node.LeftChild != null && node.RightChild == null)
{
node.Data = node.LeftChild.Data;
node.LeftChild = null;
return;
}
//删除的结点有左，右子树
BSNode temp = node.RightChild;
while (true)
{
if (temp.LeftChild != null)
{
temp = temp.LeftChild;
}
else
{
break;
}
}
node.Data = temp.Data;
Delete(temp);
}
}
}
using System;
namespace _2_1_3二叉排序树
{
/// <summary>
/// 测试类
/// </summary>
class Program
{
static void Main(string[] args)
{
BSTree tree = new BSTree();
int[] data = {62,58,28,47,73,99,35,51,93,37 };
foreach (int item in data)
{
tree.Add(item);
}
Console.Write("中序遍历的结果：");
tree.MiddleBianli();
Console.WriteLine();
Console.WriteLine("Find-1方法查找62是否存在：" + tree.Find1(62));
Console.WriteLine("Find-2方法查找62是否存在：" + tree.Find2(62));
Console.WriteLine("Find-1方法查找63是否存在：" + tree.Find1(63));
Console.WriteLine("Find-2方法查找63是否存在：" + tree.Find2(63));
Console.WriteLine("删除根结点后的结果：");
tree.Delete(62);
tree.MiddleBianli();
Console.ReadKey();
}
}
}
作者：Czhenya
链接：https://czhenya.blog.csdn.net/article/details/78887679
来源：CSDN
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。