| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 632 人关注过本帖
标题:C#编的线索二叉树错在哪里?望高手指点迷津!
取消只看楼主 加入收藏
边城迷途
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2010-5-11
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:2 
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);
            }
        }



    }

}
搜索更多相关主题的帖子: 二叉树 线索 
2010-05-11 21:03
边城迷途
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2010-5-11
收藏
得分:0 
这已经是完整的程序了,我使用的开发平台是visual studio 2005控制台应用程序,在上面能够运行。插入和中序遍历操作没有问题,就是删除操作存在不足之处(问题已述如上)。我陈述的问题就存在于用C#语言编写的程序代码中,若换用c或c++或许就不存在问题了(如果我能编出来的话)。如果说我的程序是脚,那么你的完美的解答就是我要找的那双鞋。反过来就不行了,你说是不是,哈哈...打个比方而已!
2010-05-11 22:52
边城迷途
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2010-5-11
收藏
得分:0 
还是要谢谢你。。。毕竟C#语言是一门新兴的编程语言,数据结构中的各种算法基本上均由c/c++实现,用C#语言编的关于线索二叉树的理想化的代码网上也很难找。谢谢。
2010-05-12 14:19
快速回复:C#编的线索二叉树错在哪里?望高手指点迷津!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018895 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved