logo标签列表

二叉树的层序遍历

c++algorithmbinary-treebreadth-first-searchtree-traversal
8
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;
   }
 }

上面发布的代码是我的层序遍历代码。这段代码对我来说运行良好，但我不喜欢的一件事是我明确地初始化temp_node = NULL或使用break。但在我看来，这似乎不是一个好的代码。
是否有比这更简洁的实现方法或如何使这段代码更好？
使用制表符进行缩进以保持一致性。 - Potatoswatter
1
哦，它通常不被称为“层序遍历”。与“深度优先”相对应，它通常被称为“广度优先”。 - Omnifarious
在我看来，level-order比breadth first search(BFS)术语更具表现力和简洁性。只需按层遍历即可。听起来很简单！ - RBT
8个回答
14
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);
        }
    }
}

好了，不再有特殊情况。缩进也已经整理好，更加易于理解。

或者：

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);
        }
    }
}

使用for循环完成。个人而言，我喜欢多加一个变量。这个变量名比每次说“q.front()”更简洁。

第一个版本（使用while）在root == NULL时可能会出现问题。 - Arun
但是如果我想要像这样打印： 1 2 3 4 5 6 .......目前它只会输出单个垂直行： 1 2 3 ... 5 - Chandra Shekhar
@ChandraShekharRam - 你想要的是“中序遍历”。这段代码可以被改编为执行中序遍历，但这超出了原始问题的范围。 - Omnifarious
3
您可以尝试这种方法：
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();
    }
}
2

您现有的代码存在一个严重问题，即在调用空树（root = NULL）时会崩溃。

您需要决定是否希望在队列中有NULL指针。

如果不允许，则只能将非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);
        }
    }
}

如果你决定在队列中使用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);
        }
    }   
}

第一种方法更为优选，因为大型树有许多空子节点（叶子节点的子节点），在稍后不处理它们时，将它们排队是没有意义的。
1

尝试：

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);
   }
 }
1
我认为上面的代码片段允许以数组格式打印层序遍历。这段代码可以帮助按照层次顺序编写解决方案。
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;
}

输出：

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

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

   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); 
              }
    }
0
一个非常简单的方式遍历二叉搜索树中的所有节点
class Node():
    def __init__(self,value):
        self.value=value
        self.left_node=None
        self.right_node=None

class BTree():
    def __init__(self):
        self.root_node=None
        self.pre_order_list=[]
    def push_element(self,value):
        node=Node(value)
        if self.root_node is None:
            self.root_node=node
            return
        else:
            self.recursion_insert(value,self.root_node)

    def recursion_insert(self,value,crnt_node):
        node=Node(value)
        if node.value<crnt_node.value:
            if crnt_node.left_node is None:             
                crnt_node.left_node=node                
            elif crnt_node.left_node is not None and node.value>crnt_node.left_node.value:
                crnt_node.left_node.right_node=node             
            else:
                self.recursion_insert(value,crnt_node.left_node)
        elif node.value>crnt_node.value:
            if crnt_node.right_node is None:
                crnt_node.right_node=node
                
            elif crnt_node.right_node is not None and node.value<crnt_node.right_node.value:
                crnt_node.right_node.left_node=node
            else:
                self.recursion_insert(value,crnt_node.right_node)
        else:
            print('Duplicate Values')

    def print_preorder_traversal(self):
        self.preOrder(self.root_node)
        for i in self.pre_order_list:
            print(i,end='->')
        print('None')

    def print_inorder_traversal(self):
        self.in_order(self.root_node)

    def print_post_order_traversal(self):
        self.post_order(self.root_node)

    def print_level_order_traversal(self):
        self.level_order(self.root_node)    

    def preOrder(self,crnt_node):
        if crnt_node:
            self.pre_order_list.append(crnt_node.value)
            #print(crnt_node.value,end='->')
            self.preOrder(crnt_node.left_node)
            self.preOrder(crnt_node.right_node)
        
    def in_order(self,crnt_node):
        if crnt_node:           
            self.in_order(crnt_node.left_node)
            print(crnt_node.value,end='->')
            self.in_order(crnt_node.right_node)

    def post_order(self,crnt_node):
        if crnt_node :
            self.post_order(crnt_node.left_node)
            self.post_order(crnt_node.right_node)   
            print(crnt_node.value)

    def level_order(self,crnt_node):    
        queue_list=[]
        queue_list.append(crnt_node.value)
        while queue_list:
            if crnt_node.left_node:
                queue_list.append(crnt_node.left_node)
            if crnt_node.right_node:
                queue_list.append(crnt_node.right_node)
            queue_list.pop(0)
            print(crnt_node.value,end='->')
            if queue_list:
                crnt_node=queue_list[0]
        
tree_obj=BTree()
tree_obj.push_element(70)
tree_obj.push_element(31)
tree_obj.push_element(93)
tree_obj.push_element(34)
tree_obj.push_element(14)
tree_obj.push_element(23)
tree_obj.push_element(73)
tree_obj.push_element(94)
#tree_obj.print_preorder_traversal()
#tree_obj.print_inorder_traversal()
#tree_obj.print_post_order_traversal()
tree_obj.print_level_order_traversal()
请问您能否解释一下您做了什么修改以及为什么它有效吗？ - Yaron
嗨，我的代码是用Python编写的。我根据排序值编写了一段代码。对于层序遍历，我只是使用并确保第一个节点进入队列，同时将其左右子节点附加到该节点，之后我会删除节点值、节点左值和右节点值。[70,31,93.....]，[31,93,14,34]。[93,14,34,73,94] - Mayank Awasthi
最终它将打印出70->31->93->14->34->73->94->23这样的结果。如果您不是指层序遍历，请告诉我。 - Mayank Awasthi
请编辑您的答案并添加解释，谢谢 :) - Yaron
你好，你能具体说明一下你想了解什么吗？我认为我已经解释了我的代码在做什么。如果你有任何疑虑，请在这里写下来，我会尽力解释。 - Mayank Awasthi
0
#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;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接