C++ 二叉树的层序遍历

Level Order Traversal of a Binary Tree

提问by brett

void traverse(Node* root)
{
    queue<Node*> q;

    Node* temp_node= root;

    while(temp_node)
    {
        cout<<temp_node->value<<endl;

        if(temp_node->left)
            q.push(temp_node->left);

        if(temp_node->right)
            q.push(temp_node->right);

        if(!q.empty())
        {
            temp_node = q.front();
            q.pop();
        }
        else
            temp_node = NULL;
   }
 }

The above posted code is my level order traversal code. This code works fine for me but One thing I dont like is I am explicitly initializing temp_node = NULLor I use break. But it does not seem to be a good code to me.

上面贴出的代码是我的关卡遍历代码。这段代码对我来说很好用，但我不喜欢的一件事是我正在明确初始化temp_node = NULL或使用 break。但这对我来说似乎不是一个好的代码。

Is there a neat implementation than this or how can I make this code better?

有没有比这更简洁的实现，或者我怎样才能使这段代码更好？

回答by Omnifarious

void traverse(Node* root)
{
    queue<Node*> q;

    if (root) {
        q.push(root);
    }
    while (!q.empty())
    {
        const Node * const temp_node = q.front();
        q.pop();
        cout<<temp_node->value<<"\n";

        if (temp_node->left) {
            q.push(temp_node->left);
        }
        if (temp_node->right) {
            q.push(temp_node->right);
        }
    }
}

There, no more special case. And the indentation is cleaned up so it can be understood more easily.

在那里，没有更多的特殊情况。并且缩进被清理，以便更容易理解。

Alternatively:

或者：

void traverse(Node* root)
{
    queue<Node*> q;

    if (!root) {
        return;
    }
    for (q.push(root); !q.empty(); q.pop()) {
        const Node * const temp_node = q.front();
        cout<<temp_node->value<<"\n";

        if (temp_node->left) {
            q.push(temp_node->left);
        }
        if (temp_node->right) {
            q.push(temp_node->right);
        }
    }
}

Done up as a forloop. Personally, I like the extra variable. The variable name is a nicer shorthand than saying 'q.front()` all the time.

作为一个for循环完成。就个人而言，我喜欢额外的变量。变量名是比一直说 'q.front()` 更好的速记。

回答by Md. Rezwanul Haque

You can try this way:

你可以试试这个方法：

struct Node
{
    char data;
    Node* left;
    Node* right;
};
void LevelOrder(Node* root)
{
    if(root == NULL) return;
    queue<Node*> Q;
    Q.push(root);
    while(!Q.empty())
    {
        Node* current = Q.front();
        cout<< current->data << " ";
        if(current->left != NULL) Q.push(current->left);
        if(current->right != NULL) Q.push(current->right);
        Q.pop();
    }
}

回答by codaddict

One serious problem with your existing code is it crashes when it is called on an empty tree (root = NULL).

现有代码的一个严重问题是在空树 ( root = NULL)上调用时会崩溃。

You need to decide if you want to have NULLpointers in the queue or not.

您需要决定是否要NULL在队列中放置指针。

If not them you can only enqueue non-NULLvalues.

如果不是他们，你只能排队非NULL值。

void traverse(Node* root) {
    queue<Node*> q;

    // no tree no level order.
    if(root == NULL) {
        return;
    }

    // push the root to start with as we know it is not NULL.
    q.push(root);

    // loop till there are nodes in the queue.
    while(!q.empty()) {
        // dequeue the front node.
        Node *tmpNode = q.front();
        q.pop();

        // print it..we are sure it is not NULL.
        cout<<tmpNode->value<<" ";

        // enqueue left child if it exists.
        if(tmpNode->left) {
            q.push(tmpNode->left);
        }
        // enqueue right child if it exists.
        if(tmpNode->right) {
            q.push(tmpNode->right);
        }
    }
}

Alternatively if you decide to have NULLin the queue you can do:

或者，如果您决定加入NULL队列，您可以执行以下操作：

void traverse(Node* root) {
    queue<Node*> q;

    // push the root..even if it is NULL.
    q.push(root);

    // loop till the queue is not empty.
    while(!q.empty()) {
        // dequeue the front node.
        Node *tmpNode = q.front();
        q.pop();

        // the dequeued pointer can be NULL or can point to a node.
        // process the node only if it is not NULL.     
        if(tmpNode) {       
            cout<<tmpNode->value<<" ";
            q.push(tmpNode->left);
            q.push(tmpNode->right);
        }
    }   
}

The first method is preferred as a large tree has plenty of NULLchildren (children of leaf nodes) and there is no point in having them enqueued in the queue when we later just don't process them.

第一种方法是首选，因为一棵大树有很多NULL子节点（叶节点的子节点），当我们稍后不处理它们时，将它们排入队列是没有意义的。

回答by Martin York

Try:

尝试：

void traverse(Node* root)
{
    queue<Node*> q;
    q.push(root);

    while(!q.empty())
    {
        Node* temp_node = q.front();
        q.pop();
        if (temp_node == NULL)
        {   continue;
        }

        cout << temp_node->value << endl;

        q.push(temp_node->left);
        q.push(temp_node->right);
   }
 }

回答by Venkata Gogu

I think above code snippets allow to print the level order traversal in array format. This code can help to write the solution in form of level order.

我认为上面的代码片段允许以数组格式打印级别顺序遍历。此代码可以帮助以级别顺序的形式编写解决方案。

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> a ; 
    vector<int> b;
    if (root == NULL)   return a;
    std::queue<TreeNode *> q;
    q.push(root);
    int nodeCount ;
    TreeNode* temp;
    while(true){
        nodeCount = q.size();
        if (nodeCount == 0)    break;
        while(!nodeCount){
            temp = q.front();
            b.push_back(temp->val);
            q.pop();
            if(temp->left != NULL)    q.push(temp->left);
            if(temp->right!= NULL)    q.push(temp->right);
            nodeCount-- ;
        }
        a.push_back(b);
        b.resize(0);
    }
    return a;
}

Output:

输出：

[ [1],
  [2,3],
  [4,5]
]

回答by 0xAliHn

My Java solution using Queue data structure and BFS algorithm:

我使用队列数据结构和 BFS 算法的 Java 解决方案：

   void levelOrder(Node root) {
        //LinkedList is class of Queue interface
        Queue<Node> queue=new LinkedList<>(); 
        queue.add(root); 

        //Using BFS algorithm and queue used in BFS solution
        while(!queue.isEmpty()) { 
                Node node=queue.poll(); 
                System.out.print(node.data+" "); 
                if(node.left!=null) 
                queue.add(node.left); 
                if(node.right!=null) 
                queue.add(node.right); 
              }
    }

回答by Saurabh Kumar

#include<iostream>
#include<queue>
using namespace std;

struct node{
   int data;
   node *left,*right;
};

// function for creating nodes of the tree dynamically...
node * new_node(int item){
   node *temp = new node();
   temp->data = item; 
   temp->left = NULL;
   temp->right = NULL;
}

//function to perform the level order tree traversal... 
void level_order(node *temp){
   queue <node*> q;              
   q.push(temp);
   while(q.empty() == false){
      temp = q.front();
      cout<<temp->data<<endl;
      if(temp->left != NULL ){
         q.push(temp->left);
      }
      if(temp->right !=NULL){
         q.push(temp->right);
      }
      q.pop();
   }
}

int main(){
  node *root = new node();       //Creating object of the structure node...
  root = NULL;
  root = new_node(4);
  root->left = new_node(3);
  root->right = new_node(2);
  root->left->left = new_node(1);
  level_order(root);              
  return 0;
}