打印二叉树结点
问题描述:
我编程二叉树项目。我完成了所有操作(插入,删除,创建,查找),而是完成了一项功能,即打印操作。我应该这样打印:打印二叉树结点
5
46
X557
XXX6XXX9
基本上打印所有节点,但打印X如果节点为空。我一直在试图弄清楚如何做到这一点,而且我一直在死路一条。这会像inorder-traversal?谢谢
答
使用等级序遍历(广度优先搜索)打印每个节点,你经过一个水平,一个换行符在每个级别的结束。
你可以找到BFS伪代码here
+0
简单地做BFS不会照顾打印X如果节点是空的。 – 2012-04-01 18:21:33
答
您可以使用BFS,但有轻微的修改:
简单BFS,访问节点后添加其子队列。如果没有孩子, 什么都不添加。
对于你的问题,如果没有孩子的节点所访问,添加一个特殊的节点到队列,其作为“X”的价值,使其在输出打印的“X”相应。在每个级别后打印一个换行符。
答
如梦里说,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;
}
}
这听起来像你想要一个广度优先搜索。 – 2012-04-01 16:58:56
为什么二叉树有空节点?我的理解是,当节点(或值,项目)被删除时,树被重构以消除空节点。 – 2012-04-01 18:05:21