//元素类
class Element
{
public int key;
public Element (int k)
{
key = k;
}
}
//节点类
class BstNode
{
public Element date ;
public BstNode leftNode;
public BstNode rightNode;
public void DisPlay( int i)
{
Console.WriteLine("Position:" +i + "Date:" +date.key);
if (leftNode != null)
leftNode.DisPlay(2 * i);
if (rightNode != null)
rightNode.DisPlay(2 * i+1);
}
}
//二叉查找树
namespace 二叉查找树
{
class BST
{
private BstNode root;
public BstNode Root
{
get { return root; }
set { root = value; }
}
public BST()
{
root = null;
}
public BST(BstNode init )
{
root = init;
}
public BstNode IterSearch(Element x)
{
for(BstNode t = root;t!=null;)
{
if (x.key == t.date.key)
return t;
if (x.key < t.date.key)
t = t.leftNode;
if (x.key > t.date.key)
t = t.rightNode;
}
return null;
}
public BstNode Search(BstNode sr, Element x)
{
if (sr == null)
{
Console.WriteLine("输入节点为空或未找到数据");
return null;
}
if (sr.date.key == x.key) return sr;
if (x.key <sr .date.key)
{
return Search(sr.leftNode, x);
}
return Search(sr.rightNode, x);
}
public void DisPlay()
{
if(root !=null )
{
root.DisPlay(1);
}
else
{
Console.WriteLine("Is null");
}
}
public bool Insert(Element x)
{
BstNode p = root;
BstNode q = null;
while(p!=null)
{
q = p;
if (x.key.Equals( p.date.key))
return false;
if (x.key < p.date.key)
p = p.leftNode;
else
p = p.rightNode;
}
p = new BstNode();
p.leftNode = null;
p.rightNode = null;
p.date = x;
if (root == null) root = p;
else if (x.key < q.date.key) q.leftNode = p;
else q.rightNode = p;
return true;
}
public void ShowNode(BstNode root)
{
Console.WriteLine(root .date.key+" ");
}
/// <summary>
/// 中序遍历结果为排序后的数据
/// </summary>
public void InOrder()
{
InOrder(Root);
}
public void InOrder(BstNode node)
{
if (node!=null )
{
InOrder(node.leftNode);
ShowNode(node);
InOrder(node.rightNode);
}
}
}
}
//实例程序
class Program
{
static void Main(string[] args)
{
BST m = new BST();
//Element a, b, c, d, e, f, g, h, i, j;
Element a = new Element(5);
Element b = new Element(3);
Element c = new Element(11);
Element d = new Element(3);
Element e = new Element(15);
Element f = new Element(2);
Element g= new Element(8);
Element h = new Element(22);
Element i = new Element(20);
Element j = new Element(9);
Console.WriteLine(m.Insert(a));
Console.WriteLine(m.Insert(b));
Console.WriteLine(m.Insert (c));
Console.WriteLine(m.Insert (d));
Console.WriteLine(m.Insert (e));
Console.WriteLine(m.Insert(f));
Console.WriteLine(m.Insert (g));
Console.WriteLine(m.Insert (i));
m.DisPlay();
BstNode p = m.Search(m.Root,f);
Console.WriteLine("找到的是"+p.date.key);
m.InOrder();
}
}
