在二叉樹的單個給定級別上打印所有元素

我需要打印（訪問）二叉樹的單個級別上的節點。
我不明白這是如何做到的，但我再次對算法不熟練。
我知道，在廣度優先遍歷中，您使用一個隊列，並且首先將根節點放入隊列中，然後您將它列入隊列並將其排入子隊列，然後您將第一個被取消的子隊列出隊列，然後將其排入子隊列等等......
據我所知，這使得不可能確切地知道何時一個層次結束，另一個層次開始，除非您在創建二叉樹時將其分配給每個節點，然後在您執行該操作時檢查層次廣度優先遍歷。在二叉樹的單個給定級別上打印所有元素

像這樣的東西（代碼是在PHP中，但這不是一個PHP相關的問題，這是一個通用算法相關的問題 - 這是一個函數的一部分，添加一個節點到一個二進制樹，每個節點添加）：

if($this->root == null) 
    { 
     $this->root = $node; 
        $this->root->level = 1; 
     return; 
    } 

    $nextnode = $this->root; 

      $level = 1; 

    while (true) 
    { 
     if($node->value > $nextnode->value) 
     { 
         if($nextnode->right != null) 
         { 
          $nextnode = $nextnode->right; 
          $level++; 
         } 
         else 
         { 
          $nextnode->right = $node; 
          $nextnode->right->level = ++$level; 
          return; 
         } 
     } 
     else if($node->value < $nextnode->value) 
     { 
         if($nextnode->left != null) 
         { 
          $nextnode = $nextnode->left; 
          $level++; 
         } 
         else 
         { 
          $nextnode->left = $node; 
          $nextnode->left->level = ++$level; 
          return; 
         } 
     } 
     else if($node->value == $nextnode->value) 
      return; 
    }

所以我的問題是：

這是印上一個二叉樹的單級節點的唯一途徑？
還有別的辦法嗎？
創建樹時沒有存儲關卡還有其他方法嗎？

來源

2010-01-23 Para

會遞歸解決方案套件嗎？我在C中寫過這個，我希望這對你來說不是問題。

void traverse_tree_rec(TreeNode *ptn, int current_level, int targeted_level, (void*)(pVisit)(TreeElement*)){  
    if (ptn==NULL) 
     return; 
    else if(current_level == targeted_level) 
     pVisit(ptn->entry); 
    else{ 
     traverse_tree_rec(ptn->left, current_level+1, targeted_level, pVisit); 
     traverse_tree_rec(ptn->right, current_level+1, targeted_level, pVisit); 
    } 
} 

void traverse_level(Tree *pTree, int level, (void*)(pFunction)(TreeElement)){ 
    traverse_level_rec(pTree->root, 0, level, pFunction); 
}

來源

2010-01-23 08:33:40

需求第一和第二條款切換或有一個空指針引用可能。首先訪問左側分支也更自然！ – 2010-01-23 10:41:34

完成並完成。謝謝你，先生。 – 2010-01-23 21:10:54

@Para，

這使得它無法確切地知道一個關卡結束和另一個開始，除非....

你不必在遍歷整個樹BFS遍歷您正在嘗試。您可以通過引入數組級別[]來修改wiki中給出的BFS psedocode; 你必須做這些：

初始化級別0的每個節點。
只要你在行中標記○：o ← G.opposite(t,e)賦值級別[o] =級別[t] +1;
後t ← Q.dequeue()如果level[t] > targeted_level break;

來源

2012-09-10 14:53:31

在二叉樹的單個給定級別上打印所有元素

回答

相關問題