二叉排序树，又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：
若它的左子树不为空。则左子树上所有的结点的值均小于跟的结点值 若它的右子树部位空，则右子树的所有结点值均大于它的根结点的值 它的左右子树也分别是二叉排序树
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();
}
}
}
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对服务器之家的支持。如果你想了解更多相关内容请查看下面相关链接
原文链接：https://blog.csdn.net/Czhenya/article/details/78887679
dy("nrwz");