打印二叉樹結點

我編程二叉樹項目。我完成了所有操作（插入，刪除，創建，查找），而是完成了一項功能，即打印操作。我應該這樣打印：打印二叉樹結點

5 
46 
X557 
XXX6XXX9

基本上打印所有節點，但打印X如果節點爲空。我一直在試圖弄清楚如何做到這一點，而且我一直在死路一條。這會像inorder-traversal？謝謝

來源

2012-04-01 Richard

這聽起來像你想要一個廣度優先搜索。 – 2012-04-01 16:58:56

爲什麼二叉樹有空節點？我的理解是，當節點（或值，項目）被刪除時，樹被重構以消除空節點。 – 2012-04-01 18:05:21

使用等級序遍歷（廣度優先搜索）打印每個節點，你經過一個水平，一個換行符在每個級別的結束。

你可以找到BFS僞代碼here

來源

2012-04-01 17:03:20

簡單地做BFS不會照顧打印X如果節點是空的。 – 2012-04-01 18:21:33

您可以使用BFS，但有輕微的修改：

簡單BFS，訪問節點後添加其子隊列。如果沒有孩子，什麼都不添加。

對於你的問題，如果沒有孩子的節點所訪問，添加一個特殊的節點到隊列，其作爲「X」的價值，使其在輸出打印的「X」相應。在每個級別後打印一個換行符。

來源

2012-04-01 18:25:23

如夢裏說，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-02 05:36:35 Gin

打印二叉樹結點

回答

相關問題