C＃在控制台中显示二进制搜索树 [英] C# Display a Binary Search Tree in Console

问题描述

我有简单的二叉搜索树

  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（）
 {
打印（_root，4）; 
} 
 
 public void打印（BNode p，int padding）
 {
 if（p！= null）
 {
 if p.right！= null）
 {
打印（p.right，padding + 4）; 
} 
 if（padding> 0）
 {
 Console.Write（.PadLeft（padding））; 
} 
 if（p.right！= null）
 {
 Console.Write（/ \\\
）; 
 Console.Write（.PadLeft（padding））; 
} 
 Console.Write（p.item.ToString（）+\\\
）; 
 if（p.left！= null）
 {
 Console.Write（.PadLeft（padding）+\\\\\
）; 
打印（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 是根）但我不高兴。

问题 ：在控制台应用程序中显示这个树有更好的方法吗？

解决方案

我最后得到了以下方法允许你打印任意子树：

  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打印（此BNode根，字符串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 ??下一页
 for（; next == null; item = item.Parent）
 {
 int top = rootTop + 2 * level; 
打印（item.Text，top，item.StartPos）; 
 if（item.Left！= null）
 {
打印（/，top + 1，item.Left.EndPos）; 
打印（_，top，item.Left.EndPos + 1，item.StartPos）; 
} 
 if（item.Right！= null）
 {
 Print（_，top，item.EndPos，item.Right.StartPos  -  1）; 
打印（\\，top + 1，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打印（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（）; 
} 
} 
  

使用示例数据， / p>

btr.Root.Print（）;

btr.Root.Print（textFormat：（0） ）;

UPDATE： IMO上面的默认格式是紧凑和可读的，但只是为了好玩，调整算法产生更多的图形输出（ textFormat 和 spacing 参数已删除）：

  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打印（这个BNode根，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（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 ??下一页
 for（; next == null; item = item.Parent）
 {
打印（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打印（NodeInfo item，int top）
 {
 SwapColors（）; 
打印（item.Text，top，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 ）; 
} 
 
私人静态无效PrintLink（int top，string start，string end，int startPos，int endPos）
 {
打印（start，top，startPos） ; 
打印（─，top，startPos + 1，endPos）; 
打印（end，top，endPos）; 
} 
 
 private static void打印（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）; 
} 
 
 private static void SwapColors（）
 {
 var color = Console.ForegroundColor; 
 Console.ForegroundColor = Console.BackgroundColor; 
 Console.BackgroundColor = color; 
} 
} 
  

，结果是：

I have simple binary search tree

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);
            }
        }
    }
}

where I can insert values like

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);

I want to display my tree within my console application. I have a btr.Print(); which displays my tree from left to right (6 is the root) - but I'm not happy with it.

Question: Is there a better way to display this tree within a console application? Even a improvement of this Print() would help me.

解决方案

I've ended up with the following method that allows you to print arbitrary subtree:

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("_", top, item.Left.EndPos + 1, item.StartPos);
                }
                if (item.Right != null)
                {
                    Print("_", top, item.EndPos, item.Right.StartPos - 1);
                    Print("\\", top + 1, 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);
    }
}

As you can see, I've added some parameters that affect the formatting. By default it produces the most compact representation.

In order to play with it, I've modified the BTree class as follows:

public class BTree
{
    // ...

    public BNode Root { get { return _root; } }

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

Using your sample data, here are some results:

btr.Root.Print();

btr.Root.Print(textFormat: "(0)", spacing: 2);

UPDATE: IMO the default format above is compact and readable, but just for fun, adjusted the algorithm to produce more "graphical" output (textFormat and spacing parameters removed):

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, 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(" 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, top, 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, top, startPos);
        Print("─", top, startPos + 1, endPos);
        Print(end, top, endPos);
    }

    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);
    }

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

and the result is:

这篇关于C＃在控制台中显示二进制搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！