Печать значений в древовидной структуре в Java? - PullRequest
Новая
       37

Печать значений в древовидной структуре в Java?

0 голосов
/ 06 ноября 2018

Я пытаюсь написать этот код для печати заданных пользовательских данных в древовидной структуре, следующей за 

      x
  x       x
x            x

но это не выводится таким образом. Я получаю вывод как 

x
x
x

Это написанная мной функция, которая получает и печатает: 

private void inOrder(Node n)
{
    if(n == null) // recursion ends when node is null
    return;
{
    inOrder(n.left);
    System.out.println(n.data);
    inOrder(n.right);
}
}

public void printInorder()
{
    inOrder(root);
}

Ответы [ 3 ]

0 голосов
/ 06 ноября 2018

Веселое упражнение! Ваш подход сталкивается с проблемами, потому что любые вызовы println() не позволяют печатать дополнительные узлы в строке. Использование обхода порядка на уровне / BFS позволит вам вызвать println() для перехода на следующую строку только после того, как вы закончили печатать все узлы на данном уровне дерева.

Большая сложность заключается в отслеживании горизонтального размещения каждого узла на уровне. Для этого необходимо учитывать глубину, длину данных узла и пустых дочерних элементов. Если это допустимо, рассмотрите возможность печати дерева с увеличением глубины слева направо, аналогично команде unix tree, а не сверху вниз.

Вот упрощенное доказательство концепции, чтобы дать представление о том, что может повлечь за собой печать сверху вниз (пробел / между формулами из этого превосходного поста по этой самой теме). Стратегия, которую я использовал, - запускать BFS с использованием очереди, сохраняя узлы (и нули) в списке на уровне. По достижении конца уровня пробелы перед / разделением определяются на основе количества узлов на уровне, равном 2 n-1 , и печатаются. 

import java.util.*;


class Main {
    public static void main(String[] args) {
        printLevelOrder(
            new Node(
                1, 
                new Node(
                    2, 
                    new Node(
                        4, 
                        new Node(7, null, null), 
                        null
                    ),
                    null
                ),
                new Node(
                    3, 
                    new Node(
                        5, 
                        new Node(8, null, null),
                        null
                    ),
                    new Node(
                        6, 
                        null,
                        new Node(9, null, null)                        
                    )
                )
            )
        );
    }

    static void printLevelOrder(Node root) {
        LinkedList<Item> queue = new LinkedList<>();
        ArrayList<Node> level = new ArrayList<>();
        int depth = height(root, 0);
        queue.add(new Item(root, depth));

        for (;;) {
            Item curr = queue.poll();

            if (curr.depth <= 0) {
                for (Node n : level) {
                    System.out.print((n == null ? " " : n.val) + " "); 
                }

                System.out.println();
                break;
            }
            else if (curr.depth < depth) {
                depth = curr.depth;

                for (int i = (int)Math.pow(2, depth) - 1; i > 0; i--) { 
                    System.out.print(" "); 
                }

                for (Node n : level) {
                    System.out.print((n == null ? " " : n.val));

                    for (int i = (int)Math.pow(2, depth + 1); i > 1; i--) {
                        System.out.print(" ");
                    }
                }

                level.clear();
                System.out.println();
            }

            if (curr.node != null) {
                level.add(curr.node);
                queue.add(new Item(curr.node.left, depth - 1));
                queue.add(new Item(curr.node.right, depth - 1));
            }
            else {
                level.add(null);
                queue.add(new Item(null, depth - 1));
                queue.add(new Item(null, depth - 1));
            }
        }
    }

    static int height(Node root, int height) {
        if (root != null) {
            return 1 + Math.max(
                height(root.left, height), 
                height(root.right, height)
            );
        }

        return height;
    }
}

class Node {
    Node left;
    Node right;
    int val;

    public Node(int val, Node left, Node right) {
        this.left = left;
        this.right = right;
        this.val = val;
    }
}

class Item {
    Node node;
    int depth;
    int width;

    public Item(Node node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

Выход: 

       1               
   2       3       
 4       5   6   
7       8     9

Попробуйте!

0 голосов
/ 06 ноября 2018

Это лучшее решение, которое я видел: https://stackoverflow.com/a/42449385/9319615

Вот мой фрагмент кода, использующий его. Этот класс будет работать как есть. 

class Node {
    final int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }

    public void print() {
        print("", this, false);
    }

    private void print(String prefix, Node n, boolean isLeft) {
        if (n != null) {
            System.out.println(prefix + (isLeft ? "|-- " : "\\-- ") + n.value);
            print(prefix + (isLeft ? "|   " : "    "), n.left, true);
            print(prefix + (isLeft ? "|   " : "    "), n.right, false);
        }
    }


}

class BinaryTree {
    Node root;

    private Node addRecursive(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }

        if (value < current.value) {
            current.left = addRecursive(current.left, value);
        } else if (value > current.value) {
            current.right = addRecursive(current.right, value);
        } else {
            // value already exists
            return current;
        }

        return current;
    }

    public void add(int value) {
        root = addRecursive(root, value);
    }

    public void traverseInOrder(Node node) {
        if (node != null) {
            traverseInOrder(node.left);
            System.out.print(" " + node.value);
            traverseInOrder(node.right);
        }
    }


}

public class Main {

    public static void main(String[] args) {

        BinaryTree bt = new BinaryTree();
        bt.add(6);
        bt.add(4);
        bt.add(8);
        bt.add(3);
        bt.add(5);
        bt.add(7);
        bt.add(9);

        System.out.println("Print in order->");
        bt.traverseInOrder(bt.root);

        System.out.println("\n\nPrint Tree Structure");
        bt.root.print();
    }

}

Пример вывода

0 голосов
/ 06 ноября 2018

У вас проблема с печатью так, как вы хотите. По порядку будет напечатан левый, текущий и правый. Они находятся на разных уровнях в дереве. Как только вы напечатаете нижний уровень, вы не сможете распечатать текущий выше, потому что он уже был напечатан.

Также не забудьте, что println напечатает эту строку и даст новую строку после.

Чтобы иметь причудливый дизайн, вам, вероятно, нужно сделать какую-то причудливую конструкцию, чтобы выровнять их идеально, что-то вроде этого:

Вам нужна очередь для посещения узлов. 

printNode(Node root, queueWithNodesAndStartAndEnd, start, end)
   print me at the middle of start and end
   put my left child in the queue with start = myStart and end = middle of my start and my end
   put my right child in the queue with start = middle of my start and my end and end  = my end
   pop (get and remove) first element from queue
   if not empty print popped node with start and end provided

Я знаю, что это псевдокод, но вы должны иметь возможность его реализовать.

...