我編程二叉樹項目。我完成了所有操作(插入,刪除,創建,查找),而是完成了一項功能,即打印操作。我應該這樣打印:打印二叉樹結點
5
46
X557
XXX6XXX9
基本上打印所有節點,但打印X如果節點爲空。我一直在試圖弄清楚如何做到這一點,而且我一直在死路一條。這會像inorder-traversal?謝謝
我編程二叉樹項目。我完成了所有操作(插入,刪除,創建,查找),而是完成了一項功能,即打印操作。我應該這樣打印:打印二叉樹結點
5
46
X557
XXX6XXX9
基本上打印所有節點,但打印X如果節點爲空。我一直在試圖弄清楚如何做到這一點,而且我一直在死路一條。這會像inorder-traversal?謝謝
使用等級序遍歷(廣度優先搜索)打印每個節點,你經過一個水平,一個換行符在每個級別的結束。
你可以找到BFS僞代碼here
簡單地做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