1

我创建了一个 AVL 树,其中包含有效的 Add 和 Remove 方法。但是,我需要以可视格式打印出树。例如,如果平衡树当前包含 1、2、3,它看起来像这样:

   3
2
   1

有没有相对简单的方法来做到这一点?(您可以假设在添加或删除值后,我的树将始终保持适当的平衡。)

4

1 回答 1

1

对于您想要的,有一个简单的算法,根据您的需求,它的效果不会太差。一般来说(即绘制节点)这个问题很难解决——如果我没有完全误解 3d 中的 NP(但也有一些很好的遗传算法)。

无论如何,我已经使用了类似的 quick n'dirty 来进行调试,但我认为它至少应该让您了解它是如何工作的(c# 代码,但这里的差异归结为不同的大小写):

                    // Start Method
        static internal string PrintTree(Node root) {
            StringBuilder sb = new StringBuilder();
            PrintTree(root, "", sb);
            return sb.ToString();
        }

        static private void PrintTree(Node node, string indent, StringBuilder sb) {
            sb.AppendLine(node.ToString());
            if (node.LeftChild != null) {
                if (node.RightChild == null) {
                    PrintLastChild(node.LeftChild, indent, sb);
                }
                else {
                    PrintNormalChild(node.LeftChild, indent, sb);
                    PrintLastChild(node.RightChild, indent, sb);
                }
            }
        }

        static private void PrintNormalChild(Node node, string indent, StringBuilder sb) {
            sb.Append(indent);
            sb.Append('├');
            sb.Append('─');
            PrintTree(node, indent + "│ ", sb);
        }

        static private void PrintLastChild(Node node, string indent, StringBuilder sb) {
            sb.Append(indent);
            sb.Append('└');
            sb.Append('─');
            PrintTree(node, indent + "  ", sb);
        }

如果您希望以更典型的树方式使用它,则必须进行一些预计算(基本上,因为您希望根节点位于树的中间,您必须知道计算必要缩进级别和工作的深度一行一行 - 如果效率不重要,应该不会太糟糕)

于 2011-06-09T20:53:19.883 回答