二叉排序树又叫二叉搜索树，如果树不为空，则具有以下性质：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
通俗来讲一句话，插入节点的时候小的放左边，大的放右边。
先定义Node节点
public class Node<T>
{
public T Data;
public int Index;
public Node<T> LeftChild;
public Node<T> RightChild;
public Node<T> Parent;
public int Height;
public bool Larger(int index)
{
if (Index == index)
throw new Exception("index exist:" + index);
return Index > index;
}
}
主要就是一个插入的方法
public void Insert(Node<T> node)
{
if (Root == null)
throw new Exception("sort tree does't exist");
Node<T> temp;
temp = Root;
while(true)
{
if(node.Larger(temp.Index))
{
if(temp.RightChild == null)
{
temp.RightChild = node;
node.Parent = temp;
break;
}
else
{
temp = temp.RightChild;
}
}
else
{
if (temp.LeftChild == null)
{
temp.LeftChild = node;
node.Parent = temp;
break;
}
else
{
temp = temp.LeftChild;
}
}
}
}
完整代码
class SortTree<T>
{
private Node<T> Root;
public void CreatSortTree(Node<T> data)
{
if (Root != null)
throw new Exception("can't creat,root exist");
Root = new Node<T>();
Root = data;
}
public void Insert(Node<T> node)
{
if (Root == null)
throw new Exception("sort tree does't exist");
Node<T> temp;
temp = Root;
while(true)
{
if(node.Larger(temp.Index))
{
if(temp.RightChild == null)
{
temp.RightChild = node;
node.Parent = temp;
break;
}
else
{
temp = temp.RightChild;
}
}
else
{
if (temp.LeftChild == null)
{
temp.LeftChild = node;
node.Parent = temp;
break;
}
else
{
temp = temp.LeftChild;
}
}
}
}
public void InOrder()
{
InOrder(Root);
}
private void InOrder(Node<T> root)
{
if (root != null)
{
Console.WriteLine(string.Format("index:{0},data:{1}", root.Index, root.Data));
InOrder(root.LeftChild);
InOrder(root.RightChild);
}
}
}
删除操作会在下一章平衡二叉树说到
