Распечатать AVL-дерево в JTextPane: Java - PullRequest
Новая
       21

Распечатать AVL-дерево в JTextPane: Java

1 голос
/ 10 июня 2011

Я создал дерево AVL с рабочими методами Add и Remove.Тем не менее, мне нужно распечатать дерево в визуальном формате.Например, если бы сбалансированное дерево в настоящее время содержало 1, 2, 3, оно выглядело бы примерно так: 

   3
2
   1

Есть ли относительно простой способ сделать это ??(Вы можете предположить, что мое дерево всегда будет правильно сбалансировано после добавления или удаления значения.)

1 Ответ

1 голос
/ 10 июня 2011

Для того, что вы хотите, есть простой алгоритм, который будет работать не так уж плохо в зависимости от ваших требований. В общем (то есть рисование узлов) эту проблему довольно трудно решить - и если я не совсем ошибаюсь, NP трудно в 3d (но для этого тоже есть несколько хороших генетических алгоритмов).

В любом случае я использовал нечто подобное 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);
        }

Если вы хотите, чтобы это было более типичным для дерева способом, вам придется выполнить некоторые предварительные вычисления (в основном, поскольку вы хотите, чтобы корневой узел находился в середине дерева, вы должны знать глубину для вычисления необходимого отступа). уровень и рабочая линия для линии - не должно быть слишком плохо, если эффективность не важна)

...