等級順序樹遍歷一棵普通的樹，按級別顯示樹級別

Question

我想逐級顯示樹型結構。我當前的代碼執行BFS或級別順序遍歷，但我無法獲得輸出以顯示樹狀結構，如樹狀圖 查看當前輸出和預期輸出。

我的想法是使用某種類型的計數遍歷從隊列中的同一級別的元素。

我怎麼可以這樣做。

沒有此功能的原始代碼可以在下面的情況下，有人需要整個實施其他只是看看下面的displayBFS功能的鏈接中找到。

Level Order traversal of a generic tree(n-ary tree) in java

謝謝！

void displayBFS(NaryTreeNode n) 
    { 
     Queue<NaryTreeNode> q = new LinkedList<NaryTreeNode>(); 
     System.out.println(n.data); 

     while(n!=null) 
    { 
     for(NaryTreeNode x:n.nary_list) 
     { 
      q.add(x); 
      System.out.print(x.data + " "); 
     } 
     n=q.poll(); 
     System.out.println(); 
     } 
    } 

Current Tree Structure for reference: 

     root(100) 
     / |  \ 
     90  50  70 
    /  \ 
    20 30 200 300 


    Current Output: 
     100 
     90 50 70 
     20 30 
     200 300 

    Expected Output 
     100 
     90 50 70 
     20 30 200 300  

而且，我已經張貼具有相同功能的早期邏輯問題，因爲這是回答當前問題realtes到一個不同的問題，我發佈了一個新問題，就是這個方法行不行，或者我應該進行編輯到先前的問題，而不是打開一個新的？

Answer 1

只需要跟蹤當前級別和一個新的水平。

static void displayBFS(NaryTreeNode root) { 
    int curlevel = 1; 
    int nextlevel = 0; 

    LinkedList<NaryTreeNode> queue = new LinkedList<NaryTreeNode>(); 
    queue.add(root); 

    while(!queue.isEmpty()) { 
     NaryTreeNode node = queue.remove(0); 

     if (curlevel == 0) { 
      System.out.println(); 
      curlevel = nextlevel; 
      nextlevel = 0; 
     } 

     for(NaryTreeNode n : node.nary_list) { 
      queue.addLast(n); 
      nextlevel++; 
     } 

     curlevel--; 
     System.out.print(node.data + " "); 
    } 
} 

當您切換水平，爲交換currentlevel nextlevel和復位nextlevel。我更喜歡簡單的保留一個單獨的隊列。

上星期我爲微軟這個問題採訪......它沒有通過電話去所以很適合我。善於研究它。

Answer 2

使用另一個隊列來指示深度。 下面的代碼沒有進行測試，但它應該給你的想法（SEP的變量引入避免拖尾的空格）：

void displayBFS(NaryTreeNode n) { 
    Queue<NaryTreeNode> q = new LinkedList<NaryTreeNode>(); 
    Queue<Integer> depth = new LinkedList<Integer>(); 
    q.add(n); 
    depth.add(0); 

    String sep = ""; 
    int oldDepth = 0 

    while(!q.isEmpty()) { 
    NaryTreeNode currN = q.poll(); 
    int currDepth = depth.poll(); 
    if (currDepth > oldDepth) { 
     System.out.println(); 
     oldDepth = currDepth; 
     sep = ""; 
    } 
    System.out.print(sep + currN.data); 
    sep = " "; 

    for(NaryTreeNode x : currN.nary_list) { 
     q.add(x); 
     depth.add(currDepth + 1); 
    } 
    } 
} 

我的口味相對於其他方式這一做法更是不言自明人們可以做到這一點。

Answer 3

我認爲我們還需要三個變量。 numInCurrentLevel用於跟蹤當前級別的元素數量，indexInCurrentLevel用於在當前級別遍歷時進行計數，以及numInNextLevel用於跟蹤下一級別中的元素數量。代碼如下：

static void displayBFS(NaryTreeNode root) { 

    Queue<NaryTreeNode> q = new LinkedList<NaryTreeNode>();; 
    q.add(root); 
    int numInCurrentLevel = 1; 
    int numInNextLevel = 0; 
    int indexInCurrentLevel=0; 

    while(!q.isEmpty()) { 
     NaryTreeNode node = q.poll(); 
     System.out.print(node.data + " "); 
     indexInCurrentLevel++; 

     for(NaryTreeNode n : node.nary_list) { 
      q.add(n); 
      numInNextLevel++; 
     } 

     //finish traversal in current level 
     if(indexInCurrentLevel==numInCurrentLevel) { 
      System.out.println(); 
      numInCurrentLevel=numInNextLevel; 
      numInNextLevel=0;   
      indexInCurrentLevel=0; 
     } 
    } 
} 

希望它有幫助，我不是很熟悉java編程。

Answer 4

我知道這個問題的最簡單的解決方法是使用一個哨兵。隊列被初始化爲根節點其次是定點，然後遍歷隊列：

1. 去掉前面的元素
2. 如果是哨兵：
   • 我們在年底如果隊列不是空的，我們可以結束輸出線
   • ，最後將標記推回到隊列上。
3. 如果不是前哨：
   • 打印出來
   • 推動其所有的孩子到隊列中。

我不這樣做Java的，但我有一個深度感知BFS，我剝了下來做這個打印任務的一些C++代碼：

void show_tree_by_levels(std::ostream& os, Node* tree) { 
    Node* sentinel = new Node; 
    std::deque<Node*> queue{tree, sentinel}; 
    while (true) { 
    Node* here = queue.front(); 
    queue.pop_front(); 
    if (here == sentinel) { 
     os << std::endl; 
     if (queue.empty()) 
     break; 
     else 
     queue.push_back(sentinel); 
    } else { 
     for (Node* child = here->child; child; child = child->sibling) 
     queue.push_back(child); 
     os << here->value << ' '; 
    } 
    } 
} 

注意，我喜歡使用雙指針解決方案（first_child/next_sibling），因爲它通常比嵌入式列表更簡單。因人而異。