使用二叉链表建立二叉排序树
输入n个关键码（n≤80），使用二叉链表建立二叉排序树，查找关键码x，删除x，中序输出排序树，否则输出“x不存在”。 我知道这是在要答案，可是我们书上根本没有这类题，问老师吧又说让我自己探索，唉，谢谢大家帮帮忙咯。[ 本帖最后由 xingfulovexi 于 2012-5-16 22:54 编辑 ]
等会儿有时间再写写
你可以先参考下以前类似的帖子
2012-05-16 13:52
2012-05-16 15:41
2012-05-16 21:04
程序代码：using System;
//二叉数的结点结构
class BinaryTreeNode<T>
{
private T m_Data;
private BinaryTreeNode<T> m_Lchild;//指向左孩子
private BinaryTreeNode<T> m_Rchild;//指向右孩子
private BinaryTreeNode<T> m_Parent;//指向父结点
//构造函数
public BinaryTreeNode(T nData, BinaryTreeNode<T> nParent,
BinaryTreeNode<T> nLchild, BinaryTreeNode<T> nRchild)
{
m_Data = nData;
m_Parent = nParent;
m_Lchild = nLchild;
m_Rchild = nRchild;
}
//属性域
public T Data
{
get { return m_Data; }
set { m_Data = value; }
}
public BinaryTreeNode<T> Lchild
{
get { return m_Lchild; }
set { m_Lchild = value; }
}
public BinaryTreeNode<T> Rchild
{
get { return m_Rchild; }
set { m_Rchild = value; }
}
public BinaryTreeNode<T> Parent
{
get { return m_Parent; }
set { m_Parent = value; }
}
}
//二叉排序树类
class BinarySortTree
{
private BinaryTreeNode<int> m_Head;
//构造函数
public BinarySortTree()
{
m_Head = null;
}
//查找和nItem值相等的结点
//找到 则返回该结点
//没找到 则返回null
public BinaryTreeNode<int> Search(int nItm)
{
if (null == m_Head)
{
return null;
}
BinaryTreeNode<int> tmp = m_Head;
while (null != tmp)
{
if (tmp.Data > nItm)
{
tmp = tmp.Lchild;
}
else if (tmp.Data < nItm)
{
tmp = tmp.Rchild;
}
else
{
return tmp;
}
}
return null;
}
//插入nItem值
//树中已有该值 则不插入 否则进行插入
//插入成功 则返回true
//没有插入到树中 则返回false
public bool Insert(int nItem)
{
//如果在树中没有该值 则进行插入操作
if (null != this.Search(nItem))
{
return false;//插入失败
}
//插入操作 则要找到插入点
BinaryTreeNode<int> tmp = m_Head;
if (null == m_Head)
{
m_Head = new BinaryTreeNode<int>(nItem, null, null, null);
return true;
}
while (null != tmp)
{
if (tmp.Data > nItem)
{
if (null == tmp.Lchild)
{
tmp.Lchild = new BinaryTreeNode<int>(nItem, tmp, null, null);
return true;
}
tmp = tmp.Lchild;
}
else if (tmp.Data < nItem)
{
if (null == tmp.Rchild)
{
tmp.Rchild = new BinaryTreeNode<int>(nItem, tmp, null, null);
return true;
}
tmp = tmp.Rchild;
}
}
return false;
}
//删除nItem值
//成功删除 则返回true
// 否则返回false
public bool Delete(int nItem)
{
BinaryTreeNode<int> tmp = this.Search(nItem);
BinaryTreeNode<int> ftmp;
if (null == tmp)
{
return false;
}
ftmp = tmp.Parent;
if (null == tmp.Rchild && null == tmp.Lchild)
{//左右孩子都为空 则直接删除该结点
if (null != ftmp)
{
if (ftmp.Lchild == tmp)
{
ftmp.Lchild = null;
}
else
{
ftmp.Rchild = null;
}
}
else
{
m_Head = null;
}
}
else if (null == tmp.Lchild && null != tmp.Rchild)
{//只有左孩子为空 把右孩子代替该结点的位置
if (null != ftmp)
{
if (ftmp.Lchild == tmp)
{
ftmp.Lchild = tmp.Rchild;
}
else
{
ftmp.Rchild = tmp.Rchild;
}
}
tmp.Rchild.Parent = ftmp;
}
else if (null != tmp.Lchild && null == tmp.Rchild)
{//只有右孩子为空 把左孩子代替该结点的位置
if (null != ftmp)
{
if (ftmp.Lchild == tmp)
{
ftmp.Lchild = tmp.Lchild;
}
else
{
ftmp.Rchild = tmp.Lchild;
}
}
tmp.Lchild.Parent = ftmp;
}
else if (null != tmp.Lchild && null != tmp.Rchild)
{//左右孩子都不为空 则找到右孩子
BinaryTreeNode<int> s = tmp.Rchild;
//若右孩子的左孩子为空 则用右孩子直接代替
if (null == s.Lchild)
{
if (null != ftmp)
{
if (ftmp.Lchild == tmp)
{
ftmp.Lchild = s;
}
else
{
ftmp.Rchild = s;
}
}
s.Parent = ftmp;
s.Lchild = tmp.Lchild;
s.Lchild.Parent = s;
}
else
{//若右孩子的左孩子不为空， 则一直找到右孩子的左孩子直到为空
while (s.Lchild != null)
{
s = s.Lchild;
}
//如果 s的右孩子不为空 则用s的右孩子替换s的位置
//然后 s代替删除结点的位置
BinaryTreeNode<int> sftmp = s.Parent;
if (null != s.Rchild)
{
s.Rchild.Parent = sftmp;
sftmp.Lchild = s.Rchild;
}
else
{
sftmp.Lchild = null;
}
s.Parent = ftmp;
if (null != ftmp)
{
if (ftmp.Lchild == tmp)
{
ftmp.Lchild = s;
}
else
{
ftmp.Rchild = s;
}
}
tmp.Rchild.Parent = s;
tmp.Lchild.Parent = s;
s.Rchild = tmp.Rchild;
s.Lchild = tmp.Lchild;
}
}
return true;
}
}
class App
{
static BinarySortTree BSTree = new BinarySortTree();
static void Main(string[] args)
{
while (true)
{
if (4 == Run())
{
break;
}
}
}
static int Run()
{
int Num;
Console.WriteLine("\t根据提示信息进行处理");
Console.WriteLine("插入操作按 \'1\'");
Console.WriteLine("查找操作按 \'2\'");
Console.WriteLine("删除操作按 \'3\'");
Console.WriteLine("推出按 \'4\'");
Num = int.Parse(Console.ReadLine());
switch (Num)
{
case 1:
Console.Write("输入要插入的数据:");
Num = int.Parse(Console.ReadLine());
if (!BSTree.Insert(Num))
{
Console.WriteLine("\t插入失败...");
}
break;
case 2:
Console.Write("输入要查找的数据:");
Num = int.Parse(Console.ReadLine());
if (null == BSTree.Search(Num))
{
Console.WriteLine("\t查找失败...");
}
break;
case 3:
Console.Write("输入要删除的数据:");
Num = int.Parse(Console.ReadLine());
if (!BSTree.Delete(Num))
{
Console.WriteLine("\t删除失败...");
}
break;
case 4:
break;
default:
break;
}
return Num;
}
}
2012-05-16 21:05
2012-05-16 21:32
2012-05-16 22:29
2012-05-18 16:34
2012-05-18 17:35
2012-05-18 20:16
2012-05-18 22:36
