Печать узлов двоичного дерева - PullRequest
Новая
       8

Печать узлов двоичного дерева

3 голосов
/ 01 апреля 2012

Я программирую проект BinaryTree.Я закончил все (вставить, удалить, создать, найти), кроме одной функции, операция печати.Я должен напечатать это так: 

5
46
X557
XXX6XXX9

В основном выведите все узлы, но напечатайте X, если узел пуст.Я пытался понять, как это сделать, и я все время захожу в тупик.Будет ли это что-то вроде обхода inorder ??Спасибо

Ответы [ 3 ]

3 голосов
/ 01 апреля 2012

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

Вы можете найти псевдокод BFS здесь

0 голосов
/ 02 апреля 2012

Как сказал Dream Lane, BFS будет работать здесь. Я предложил свою собственную реализацию JAVA здесь для справки. 

public static void printBST(Node root) {
    // empty tree
    if (root == null)
        return;

    Queue<Node> que = new LinkedList<Node>();
    que.add(root);
    boolean allChildNull = false;// end condition

    while (que.size() > 0 && !allChildNull) {
        allChildNull = true;
        Queue<Node> childQue = new LinkedList<Node>();

        for (Node n : que) {
            // print out noe value, X for null
            if (n == null)
                System.out.printf("%1$s", "X");
            else
                System.out.printf("%1$s", n.value);

            // add next level child nodes
            if (n == null) {
                childQue.add(null);
                childQue.add(null);
            } else {
                childQue.add(n.left);
                childQue.add(n.right);
                if (n.left != null || n.right != null)
                    allChildNull = false;
            }
        }
        System.out.printf("\n");// newline
        que = childQue;
    }
}
0 голосов
/ 01 апреля 2012

Вы можете использовать BFS, но с небольшим изменением:

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

Для вашей проблемы, если нет дочерних узлов для посещаемого узла, добавьте в очередь специальный узел со значением «x», чтобы он соответственно напечатал «X» в вашем выводе.Распечатайте новую строку после каждого уровня.

...