二叉樹級別遍歷

三種類型的樹遍歷是inorder，preorder和post order。二叉樹級別遍歷

第四個不常用的遍歷是水平順序遍歷。在級別遍歷中，深度「d」處的所有節點在深度d + 1處的任何節點之前被處理。層級順序遍歷與其他遍歷不同，因爲它不是遞歸地執行;使用隊列而不是隱含的遞歸堆棧。

我上面的文字片段的問題是

爲什麼平次序遍歷未完成遞歸？
如何使用隊列順序遍歷？請求澄清與僞代碼將有所幫助。

謝謝！

來源

2011-09-05 venkysmarty

Level order traversal其實是一個BFS，它本質上不是遞歸的。它使用Queue而不是Stack來保存應該打開的下一個頂點。其中的原因是在此穿越，你想在一個FIFO爲了打開節點，而不是LIFO順序，由遞歸

正如我所說得，等級秩序實際上是一個BFS，其[BFS]僞代碼[來源於維基百科]是：

1 procedure BFS(Graph,source): 
2  create a queue Q 
3  enqueue source onto Q 
4  mark source 
5  while Q is not empty: 
6   dequeue an item from Q into v 
7   for each edge e incident on v in Graph: 
8    let w be the other end of e 
9    if w is not marked: 
10     mark w 
11     enqueue w onto Q

（*）在一棵樹，標記的頂點是不需要的，因爲你不能得到相同節點在2點不同的路徑。

來源

2011-09-05 08:13:05 amit

即使使用代碼片段，您也可以在Wikipedia中找到很好的概述。

來源

2011-09-05 08:16:02 Jiri

void levelorder(Node *n) 
{ queue < Node * >q; 

    q.push(n); 


    while(!q.empty()) 
    { 
      Node *node = q.front(); 
      cout<<node->value; 
      q.pop(); 
      if(node->left != NULL) 
      q.push(node->left); 
      if (node->right != NULL) 
      q.push(node->right); 

    } 

}

來源

2012-12-18 11:35:33 abaid

而不是一個隊列，我用一個地圖來解決這個問題。看看，如果你有興趣。正如我做一個後序遍歷，我維持在其中每個節點被定位，並使用該深度爲重點在地圖中，以收集在同一水平

class Solution { public: map<int, vector<int> > levelValues; void recursivePrint(TreeNode *root, int depth){ if(root == NULL) return; if(levelValues.count(root->val) == 0) levelValues.insert(make_pair(depth, vector<int>())); levelValues[depth].push_back(root->val); recursivePrint(root->left, depth+1); recursivePrint(root->right, depth+1); } vector<vector<int> > levelOrder(TreeNode *root) { recursivePrint(root, 1); vector<vector<int> > result; for(map<int,vector<int> >::iterator it = levelValues.begin(); it!= levelValues.end(); ++it){ result.push_back(it->second); } return result; } };

將全部溶液可以在這裏找到的值的深度 - http://ideone.com/zFMGKU 解決方案返回一個向量向量，每個向量都包含樹中正確順序的元素。

你可以嘗試在這裏解決它 - https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

而且，正如你所看到的，我們也可以在同一時間和空間的複雜性，因爲隊列解決方案做到這一點遞歸！

來源

2014-11-05 00:19:32

https://github.com/arun2pratap/data-structure/blob/master/src/main/java/com/ds/tree/binarytree/BinaryTree.java

完全可以看出來上面的鏈接。

public void levelOrderTreeTraversal(List<Node<T>> nodes){ 
    if(nodes == null || nodes.isEmpty()){ 
     return; 
    } 
    List<Node<T>> levelNodes = new ArrayList<>(); 
    nodes.stream().forEach(node -> { 
     if(node != null) { 
      System.out.print(" " + node.value); 
      levelNodes.add(node.left); 
      levelNodes.add(node.right); 
     } 
    }); 
    System.out.println(""); 
    levelOrderTreeTraversal(levelNodes); 
}

還可以檢查出 http://www.geeksforgeeks.org/

在這裏，你會發現幾乎所有的數據結構相關的答案。

來源

2017-07-21 06:15:09

二叉樹級別遍歷

回答

相關問題