最近复习下数据结构，用C#实现了下二叉搜索树，后面再继续实现平衡树和红黑树，以下是二叉搜索树（又称二叉查找树）的定义和性质：
二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).
二叉排序树的查找算法：
在二叉排序树b中查找x的过程为：
若b是空树，则搜索失败，否则：
若x等于b的根结点的数据域之值，则查找成功；否则：
若x小于b的根结点的数据域之值，则搜索左子树；否则：查找右子树。
向一个二叉排序树b中插入一个结点s的算法：
若b是空树，则将s所指结点作为根结点插入，否则：
若s->data等于b的根结点的数据域之值，则返回，否则：
若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：
把s所指结点插入到右子树中。
在二叉排序树删除结点的算法：
若*x结点为叶子结点，即xL(左子树)和xR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
若*x结点只有左子树xL或右子树xR，此时只要令xL或xR直接成为其双亲结点*parent的左子树或者右子树即可，作此修改也不破坏二叉排序树的特性。
若*x结点的左子树和右子树均不空。在删去*x之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*x的左子树为*parent的左子树，*xsucc为*f左子树的最右下的结点，而*x的右子树为*xsucc的右子树；其二是令*x的直接前驱（或直接后继）替代*x，然后再从二叉排序树中删去它的直接前驱（或直接后继）。
中序后继结点替换要删除的节点：从x的右儿子开始，一直靠左往下走，{zh1}到达的节点就是所需的后继结点，程序中用xsucc指向这个后继结点，现在只需删除xsucc指向的节点，可以根据情况1或者是情况2中的方法来删除它。
代码
{
private T data;
private BinaryNode<T> leftChild;
private BinaryNode<T> rightChild;
public T Data
{
get
{
return data;
}
set
{
data = value;
}
}
public BinaryNode<T> LeftChild
{
get
{
return leftChild;
}
set
{
leftChild = value;
}
}
public BinaryNode<T> RightChild
{
get
{
return rightChild;
}
set
{
rightChild = value;
}
}
}
public class BinaryTree<T>
{
private BinaryNode<T> root;
public BinaryNode<T> Root
{
get
{
return root;
}
set
{
root = value;
}
}
/// <summary>
/// 先序遍历
/// </summary>
/// <param name="root"></param>
public void FirstVisit(BinaryNode<T> root)
{
if (root==null)
{
return;
}
//访问当前节点数据
Console.WriteLine("此节点数据为：{0}", root.Data);
//遍历左子树
FirstVisit(root.LeftChild);
//遍历右子树
FirstVisit(root.RightChild);
}
/// <summary>
/// 中序遍历
/// </summary>
/// <param name="root"></param>
public void MidVisit(BinaryNode<T> root)
{
if (root == null)
{
return;
}
//遍历左子树
MidVisit(root.LeftChild);
//访问当前节点数据
Console.WriteLine("此节点数据为：{0}", root.Data);
//遍历右子树
MidVisit(root.RightChild);
}
/// <summary>
/// 后序遍历
/// </summary>
/// <param name="root"></param>
public void AfterVisit(BinaryNode<T> root)
{
if (root == null)
{
return;
}
//遍历右子树
AfterVisit(root.RightChild);
//遍历左子树
AfterVisit(root.LeftChild);
//访问当前节点数据
Console.WriteLine("此节点数据为：{0}", root.Data);
}
/// <summary>
/// 逐层遍历
/// </summary>
/// <param name="root"></param>
public void LevelVisit(BinaryNode<T> root)
{
if (root == null)
{
return;
}
//用一个队列来保存节点
Queue<BinaryNode<T>> queue = new Queue<BinaryNode<T>>();
//根节点入队
queue.Enqueue(root);
while (queue.Count>0)
{
BinaryNode<T> node = queue.Dequeue();
//访问当前节点数据
Console.WriteLine("此节点数据为：{0}", root.Data);
if (node.LeftChild!=null)
{
queue.Enqueue(node);
}
if (node.RightChild != null)
{
queue.Enqueue(node);
}
}
}
}
public class BinarySearchTree
{
public bool SearCh(BinaryTree<int> bt, int key)
{
BinaryNode<int> p;
if (bt.Root == null)
{
//Console.WriteLine("the binaryTree is empty!");
return false;
}
p = bt.Root;
while (p != null)
{
if (p.Data == key)
{
//Console.WriteLine("search succeed!");
return true;
}
else if (key < p.Data)
{
p = p.LeftChild;
}
else
{
p = p.RightChild;
}
}
return false;
}
/************************************************************************/
/* 向一个二叉排序树b中插入一个结点s的算法，过程为：
1.若b是空树，则将s所指结点作为根结点插入，否则：
2.若s->data等于b的根结点的数据域之值，则返回，否则：
3.若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：
4.把s所指结点插入到右子树中。
* 注意：对二叉查找树插入一个节点时总是插入到叶节点,即此时新增的节点一定是叶节点
/************************************************************************/
public bool Insert(BinaryTree<int> bt, int key)
{
BinaryNode<int> p;
if (bt.Root == null)
{
bt.Root = new BinaryNode<int>();
bt.Root.Data = key;
return true;
}
p = bt.Root;
BinaryNode<int> parent = new BinaryNode<int>(); //用于保留插入时找到的父节点
while (p != null)
{
if (p.Data == key)
{
return false;
}
else if (key < p.Data)
{
parent = p;
p = p.LeftChild;
}
else
{
parent = p;
p = p.RightChild;
}
}
p = new BinaryNode<int>();
p.Data = key;
if (key < parent.Data)
{
parent.LeftChild = p;
}
else
{
parent.RightChild = p;
}
return true;
}
/************************************************************************/
/* 在二叉排序树删去一个结点，分三种情况讨论：
1.若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。
* 由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
2.若*p结点只有左子树PL或右子树PR，
* 此时只要令PL或PR直接成为其双亲结点*f的左子树即可，
* 作此修改也不破坏二叉排序树的特性。
3.若*p结点的左子树和右子树均不空。在删去*p之后，
* 为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，
* 可以有两种做法：其一是令*p的左子树为*f的左子树，
* *s为*f左子树的最右下的结点，而*p的右子树为*s的右子树；
* 其二是令*p的直接前驱（或直接后继）替代*p，
* 然后再从二叉排序树中删去它的直接前驱（或直接后继）。 */
/************************************************************************/
//采取右子树填充法
public bool Delete(BinaryTree<int> bt, int key)
{
BinaryNode<int> p = bt.Root;
BinaryNode<int> parent = new BinaryNode<int>(); //用于保留删除时找到的父节点
while (p != null)
{
if (p.Data == key)
{
break;
}
else if (key < p.Data)
{
parent = p;
p = p.LeftChild;
}
else
{
parent = p;
p = p.RightChild;
}
}
//未找到关键码
if (p == null)
{
return false;
}
//既没有左子节点又没有右子节点
if ((p.LeftChild == null) && (p.RightChild == null))
{
if (p.Data < parent.Data)
{
parent.LeftChild = null;
}
else
{
parent.RightChild = null;
}
}
//没有右子节点
else if ((p.LeftChild != null) && (p.RightChild == null))
{
if (p.Data < parent.Data)//判断删除节点为父节点的左孩子还是右孩子
{
parent.LeftChild = p.LeftChild;
}
else
{
parent.RightChild = p.LeftChild;
}
}
//没有左子节点
else if ((p.LeftChild == null) && (p.RightChild != null))
{
if (p.Data < parent.Data)
{
parent.LeftChild = p.RightChild;
}
else
{
parent.RightChild = p.RightChild;
}
}
//左右均有
else
{
BinaryNode<int> fillNode = p.RightChild;
BinaryNode<int> fillParentNode = p;
//循环找到p的右子树中最小的节点，即最靠左的节点
while (fillNode.LeftChild != null)
{
fillParentNode = fillNode;
fillNode = fillNode.LeftChild;
}
//判断填充节点为它的父节点的左孩子还是右孩子
if (fillNode.Data < fillParentNode.Data)//左孩子
{
if (fillNode.RightChild != null)//判断填充节点是否有右孩子
{
fillParentNode.LeftChild = fillNode.RightChild;
}
else
{
fillParentNode.LeftChild = null;
}
}
else//右孩子
{
if (fillNode.RightChild != null)
{
fillParentNode.RightChild = fillNode.RightChild;
}
else
{
fillParentNode.RightChild = null;
}
}
fillNode.LeftChild = p.LeftChild;
fillNode.RightChild = p.RightChild;
if (p.Data != bt.Root.Data)
{
if (p.Data < parent.Data)//判断删除节点为父节点的左孩子还是右孩子
{
parent.LeftChild = fillNode;
}
else
{
parent.RightChild = fillNode;
}
}
else
{
bt.Root = fillNode;
}
}
return true;
}
}
class Program
{
static void Main(string[] args)
{
BinarySearchTree bst = new BinarySearchTree();
BinaryTree<int> bt=new BinaryTree<int>();
bst.Insert(bt, 10);
bst.Insert(bt, 6);
bst.Insert(bt, 16);
bst.Insert(bt, 25);
bst.Insert(bt, 8);
bst.Insert(bt, 22);
bst.Insert(bt, 12);
bst.Insert(bt, 5);
bst.Insert(bt, 7);
bst.Delete(bt, 10);
bool isExist = bst.SearCh(bt, 10);
string msg=isExist?"存在数据":"不存在数据";
Console.WriteLine(msg);
Console.ReadLine();
}
static void WriteOut(int[] seq)
{
foreach (int i in seq)
{
Console.Write("{0} ,", i);
}
Console.WriteLine();
}
}
posted on 2010-04-27 15:19 阅读(5) 所属分类:
