C#在控制台中显示二进制搜索树

发布时间：2020-12-15 06:18:45 所属栏目：百科来源：网络整理

导读：我有简单的二叉搜索树 public class BNode{ public int item; public BNode right; public BNode left; public BNode(int item) { this.item = item; }}public class BTree{ private BNode _root; private int _count; private IComparerint _comparer = Com

我有简单的二叉搜索树

public class BNode
{
    public int item;
    public BNode right;
    public BNode left;

    public BNode(int item)
    {
        this.item = item;
    }
}

public class BTree
{
    private BNode _root;
    private int _count;
    private IComparer<int> _comparer = Comparer<int>.Default;


    public BTree()
    {
        _root = null;
        _count = 0;
    }


    public bool Add(int Item)
    {
        if (_root == null)
        {
            _root = new BNode(Item);
            _count++;
            return true;
        }
        else
        {
            return Add_Sub(_root,Item);
        }
    }

    private bool Add_Sub(BNode Node,int Item)
    {
        if (_comparer.Compare(Node.item,Item) < 0)
        {
            if (Node.right == null)
            {
                Node.right = new BNode(Item);
                _count++;
                return true;
            }
            else
            {
                return Add_Sub(Node.right,Item);
            }
        }
        else if (_comparer.Compare(Node.item,Item) > 0)
        {
            if (Node.left == null)
            {
                Node.left = new BNode(Item);
                _count++;
                return true;
            }
            else
            {
                return Add_Sub(Node.left,Item);
            }
        }
        else
        {
            return false;
        }
    }

    public void Print()
    {
        Print(_root,4);
    }

    public void Print(BNode p,int padding)
    {
        if (p != null)
        {
            if (p.right != null)
            {
                Print(p.right,padding + 4);
            }
            if (padding > 0)
            {
                Console.Write(" ".PadLeft(padding));
            }
            if (p.right != null)
            {
                Console.Write("/n");
                Console.Write(" ".PadLeft(padding));
            }
            Console.Write(p.item.ToString() + "n ");
            if (p.left != null)
            {
                Console.Write(" ".PadLeft(padding) + "n");
                Print(p.left,padding + 4);
            }
        }
    }
}

我可以在其中插入值

BTree btr = new BTree();
btr.Add(6);
btr.Add(2);
btr.Add(3);
btr.Add(11);
btr.Add(30);
btr.Add(9);
btr.Add(13);
btr.Add(18);

我想在我的控制台应用程序中显示我的树.我有一个btr.Print();它从左到右显示我的树(6是根) – 但我不满意.

问题：在控制台应用程序中是否有更好的方式显示此树？即使改进此Print()也可以帮助我.

解决方法

我结束了以下方法,允许您打印任意子树：

public static class BTreePrinter
{
    class NodeInfo
    {
        public BNode Node;
        public string Text;
        public int StartPos;
        public int Size { get { return Text.Length; } }
        public int EndPos { get { return StartPos + Size; } set { StartPos = value - Size; } }
        public NodeInfo Parent,Left,Right;
    }

    public static void Print(this BNode root,string textFormat = "0",int spacing = 1,int topMargin = 2,int leftMargin = 2)
    {
        if (root == null) return;
        int rootTop = Console.CursorTop + topMargin;
        var last = new List<NodeInfo>();
        var next = root;
        for (int level = 0; next != null; level++)
        {
            var item = new NodeInfo { Node = next,Text = next.item.ToString(textFormat) };
            if (level < last.Count)
            {
                item.StartPos = last[level].EndPos + spacing;
                last[level] = item;
            }
            else
            {
                item.StartPos = leftMargin;
                last.Add(item);
            }
            if (level > 0)
            {
                item.Parent = last[level - 1];
                if (next == item.Parent.Node.left)
                {
                    item.Parent.Left = item;
                    item.EndPos = Math.Max(item.EndPos,item.Parent.StartPos - 1);
                }
                else
                {
                    item.Parent.Right = item;
                    item.StartPos = Math.Max(item.StartPos,item.Parent.EndPos + 1);
                }
            }
            next = next.left ?? next.right;
            for (; next == null; item = item.Parent)
            {
                int top = rootTop + 2 * level;
                Print(item.Text,top,item.StartPos);
                if (item.Left != null)
                {
                    Print("/",top + 1,item.Left.EndPos);
                    Print("_",item.Left.EndPos + 1,item.StartPos);
                }
                if (item.Right != null)
                {
                    Print("_",item.EndPos,item.Right.StartPos - 1);
                    Print("",item.Right.StartPos - 1);
                }
                if (--level < 0) break;
                if (item == item.Parent.Left)
                {
                    item.Parent.StartPos = item.EndPos + 1;
                    next = item.Parent.Node.right;
                }
                else
                {
                    if (item.Parent.Left == null)
                        item.Parent.EndPos = item.StartPos - 1;
                    else
                        item.Parent.StartPos += (item.StartPos - 1 - item.Parent.EndPos) / 2;
                }
            }
        }
        Console.SetCursorPosition(0,rootTop + 2 * last.Count - 1);
    }

    private static void Print(string s,int top,int left,int right = -1)
    {
        Console.SetCursorPosition(left,top);
        if (right < 0) right = left + s.Length;
        while (Console.CursorLeft < right) Console.Write(s);
    }
}

您可以看到,我添加了一些影响格式的参数.默认情况下,它产生最紧凑的表示.

为了玩它,我修改了BTree类,如下所示：

public class BTree
{
    // ...

    public BNode Root { get { return _root; } }

    public void Print()
    {
        Root.Print();
    }
}

使用您的样本数据,这里有一些结果：

btr.Root.Print();

btr.Root.Print(textFormat：“(0)”,spacing：2);

更新：IMO上面的默认格式是紧凑可读的,但只是为了乐趣,调整的算法产生更多的“图形”输出(textFormat和间距参数被删除)：

public static class BTreePrinter
{
    class NodeInfo
    {
        public BNode Node;
        public string Text;
        public int StartPos;
        public int Size { get { return Text.Length; } }
        public int EndPos { get { return StartPos + Size; } set { StartPos = value - Size; } }
        public NodeInfo Parent,Text = next.item.ToString(" 0 ") };
            if (level < last.Count)
            {
                item.StartPos = last[level].EndPos + 1;
                last[level] = item;
            }
            else
            {
                item.StartPos = leftMargin;
                last.Add(item);
            }
            if (level > 0)
            {
                item.Parent = last[level - 1];
                if (next == item.Parent.Node.left)
                {
                    item.Parent.Left = item;
                    item.EndPos = Math.Max(item.EndPos,item.Parent.StartPos);
                }
                else
                {
                    item.Parent.Right = item;
                    item.StartPos = Math.Max(item.StartPos,item.Parent.EndPos);
                }
            }
            next = next.left ?? next.right;
            for (; next == null; item = item.Parent)
            {
                Print(item,rootTop + 2 * level);
                if (--level < 0) break;
                if (item == item.Parent.Left)
                {
                    item.Parent.StartPos = item.EndPos;
                    next = item.Parent.Node.right;
                }
                else
                {
                    if (item.Parent.Left == null)
                        item.Parent.EndPos = item.StartPos;
                    else
                        item.Parent.StartPos += (item.StartPos - item.Parent.EndPos) / 2;
                }
            }
        }
        Console.SetCursorPosition(0,rootTop + 2 * last.Count - 1);
    }

    private static void Print(NodeInfo item,int top)
    {
        SwapColors();
        Print(item.Text,item.StartPos);
        SwapColors();
        if (item.Left != null)
            PrintLink(top + 1,"┌","┘",item.Left.StartPos + item.Left.Size / 2,item.StartPos);
        if (item.Right != null)
            PrintLink(top + 1,"└","┐",item.EndPos - 1,item.Right.StartPos + item.Right.Size / 2);
    }

    private static void PrintLink(int top,string start,string end,int startPos,int endPos)
    {
        Print(start,startPos);
        Print("─",startPos + 1,endPos);
        Print(end,endPos);
    }

    private static void Print(string s,top);
        if (right < 0) right = left + s.Length;
        while (Console.CursorLeft < right) Console.Write(s);
    }

    private static void SwapColors()
    {
        var color = Console.ForegroundColor;
        Console.ForegroundColor = Console.BackgroundColor;
        Console.BackgroundColor = color;
    }
}

结果是：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!