C#编的线索二叉树错在哪里？望高手指点迷津！
删除节点（既有左孩子又有右孩子并且右孩子为叶节点）存在问题。如依次输入6、2、8，删除6，结果却显示2，本应该是2、8。自己找不出代码漏洞，向高手求教。程序代码如下：
using System;
using System.Collections.Generic;
using System.Text;
namespace ThreadedBinaryTree
{
class Program
{
static void Main(string[] args)
{
ThreadedBST t = new ThreadedBST();
while (true)
{
//创建运行界面菜单选项//
Console.WriteLine("\nMenu");
Console.WriteLine("1.insert");
Console.WriteLine("2.inorder");
Console.WriteLine("3.delete");
Console.WriteLine("4.Exit");
Console.Write("\nEnter your choice (1-4)" + " ");
char ch = Convert.ToChar(Console.ReadLine());
Console.WriteLine();
switch (ch)
{
case '1':
{
Console.Write("Enter a number" + " ");
int n = Convert.ToInt32(Console.ReadLine());
t.insert(n);//执行插入节点操作//
}
break;
case '2':
{
t.inorder(t.h);//执行中序遍历操作//
}
break;
case '3':
{
Console.WriteLine("please enter a number inside the tree");
int num = Convert.ToInt32(Console.ReadLine());
t.d(num);//执行删除节点操作//
}
break;
case '4':
return;
default:
{
Console.WriteLine("Invalid option");
break;
}
}
}
}
}
//定义线索二叉树中的节点类型//
class Node
{
public Node lc;
public Node rc;
public int lt;
public int rt;
public int dt;
public Node(int data, int lth, int rth, Node lch, Node rch)
{
dt = data; lt = lth; rt = rth; lc = lch; rc = rch;
}
}
//创建包含各种操作的类//
class ThreadedBST
{
//声明头节点并初始化为空//
public Node h;
public ThreadedBST()
{
h = null;
}
//此函数可定位待插入节点tmp的父节点cur，也能找到待删除节点cur的父节点par//
public void find(int e, ref Node par, ref Node cur)
{
par = h;
cur = h.lc;
while (true)
{
if (e > cur.dt && cur.rt == 1) { par = cur; cur = cur.rc; }
if (e > cur.dt && cur.rt == 0) break;
if (e < cur.dt && cur.lt == 1) { par = cur; cur = cur.lc; }
if (e < cur.dt && cur.lt == 0) break;
if (e == cur.dt) break;
}
}
//插入节点//
public void insert(int e)
{
Node tmp;//声明新节点//
//第一次插入节点//
if (h == null)
{
Node p;
tmp = new Node(e, 0, 0, null, null); p = new Node(0, 0, 0, null, null);//初始化tmp，p仅作头结点之用，其数据域的值无实际意义//
h = p; h.lc = tmp; h.lt = 1; h.rc = h; tmp.lc = h; tmp.rc = h;//使h不为空以引用h的成员//
}
//插入前树不为空//
else
{
Node par = null, cur = null; tmp = new Node(e, 0, 0, null, null);
find(e, ref par, ref cur);
//调用后得到待插入节点tmp的父节点cur//
if (e > cur.dt)
{
tmp.rc = cur.rc; tmp.lc = cur; cur.rt = 1; cur.rc = tmp;
}
if (e < cur.dt)
{
tmp.lc = cur.lc; tmp.rc = cur; cur.lt = 1; cur.lc = tmp;
}
//插入节点的值不可重复//
if (e == cur.dt)
{ Console.WriteLine("Duplicate number not allowed"); }
}
}
//返回当前节点的中序后继节点//
public Node inor_suc(ref Node cur)
{
Node suc;
if (cur.rt == 0) { suc = cur.rc; return suc; }
else
{
suc = cur.rc;
while (suc.lt != 0)
suc = suc.lc;
return suc;
}
}
//中序遍历//
public void inorder(Node ptr)
{
while (ptr.lt != 0)
ptr = ptr.lc;
Console.Write(ptr.dt + " ");
while (ptr.rc != h)
{
ptr = inor_suc(ref ptr); Console.Write(ptr.dt + " ");
}
}
//以下是删除节点的三种情形,分别用三个子函数实现//
//1.待删除节点为叶节点//
public void c1(ref Node par, ref Node cur)
{
if (par == h) { h.lt = 0; h.lc = h; }
else
{
if (par.lc == cur) { par.lt = 0; par.lc = cur.lc; }
if (par.rc == cur) { par.rt = 0; par.rc = cur.rc; }
}
}
//2.待删除节点有且仅有一个孩子节点//
public void c2(ref Node par, ref Node cur)
{
if (par == h)
{
if (cur.lt == 1) { par.lc = cur.lc; cur.lc.rc = cur.rc; cur.lc = null; cur.rc = null; }
else
{
par.lc = cur.rc; cur.rc.lc = cur.lc; cur.rc = null; cur.lc = null;
}
}
else
{
if (par.rc == cur)
{
if (cur.lt == 1) { par.rc = cur.lc; cur.lc.rc = cur.rc; cur.lc = null; cur.rc = null; }
else { par.rc = cur.rc; cur.rc.lc = cur.lc; cur.rc = null; cur.lc = null; }
}
else
{
if (cur.lt == 1) { par.lc = cur.lc; cur.lc.rc = cur.rc; cur.lc = null; cur.rc = null; }
else { par.lc = cur.rc; cur.rc.lc = cur.lc; cur.rc = null; cur.lc = null; }
}
}
}
//3.待删除节点有两个孩子节点//
public void c3(ref Node cur)
{
Node crt = inor_suc(ref cur); //找到待删除节点cur的中序后继节点crt//
Node prt;//声明crt的父节点为prt//
cur.dt = crt.dt;//用crt数据域的值覆盖cur//
if (crt == cur.rc)
prt = cur;
else
prt = crt.rc;
//删除节点crt//
if (crt.rt == 0)
c1(ref prt, ref crt);
else
c2(ref prt, ref crt);
}
//删除节点//
public void d(int e)
{
Node par = null, cur = null;
find(e, ref par, ref cur);
if (e == cur.dt)
{
if (cur.lt == 0 && cur.rt == 0) c1(ref par, ref cur);
if (cur.lt == 1 && cur.rt == 1) c3(ref cur);
if ((cur.lt == 0 && cur.rt != 0) || (cur.rt == 0 && cur.lt != 0))
c2(ref par, ref cur);
}
}
}
}
