2012-04-01 290 views
3

我编程二叉树项目。我完成了所有操作(插入,删除,创建,查找),而是完成了一项功能,即打印操作。我应该这样打印:打印二叉树结点

5 
46 
X557 
XXX6XXX9 

基本上打印所有节点,但打印X如果节点为空。我一直在试图弄清楚如何做到这一点,而且我一直在死路一条。这会像inorder-traversal?谢谢

+2

这听起来像你想要一个广度优先搜索。 – 2012-04-01 16:58:56

+0

为什么二叉树有空节点?我的理解是,当节点(或值,项目)被删除时,树被重构以消除空节点。 – 2012-04-01 18:05:21

回答

3

使用等级序遍历(广度优先搜索)打印每个节点,你经过一个水平,一个换行符在每个级别的结束。

你可以找到BFS伪代码here

+0

简单地做BFS不会照顾打印X如果节点是空的。 – 2012-04-01 18:21:33

0

您可以使用BFS,但有轻微的修改:

简单BFS,访问节点后添加其子队列。如果没有孩子, 什么都不添加。

对于你的问题,如果没有孩子的节点所访问,添加一个特殊的节点到队列,其作为“X”的价值,使其在输出打印的“X”相应。在每个级别后打印一个换行符。

0

如梦里说,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; 
    } 
}