当前位置： 文江博客话题详情

二叉树的层序遍历

发布于 2024-09-16 11:42:00 字数 638 浏览 13 评论 0原文 

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。但对我来说这似乎不是一个好的代码。

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

原文 
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 = NULL or I use break. But it does not seem to be a good code to me.

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（8）

呆° 2024-09-23 11:42:00
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()”更好的速记。

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 for loop. Personally, I like the extra variable. The variable name is a nicer shorthand than saying 'q.front()` all the time.

回复 原文
无人接听 2024-09-23 11:42:00

你可以尝试这样的方法：

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

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();
    }
}
回复 原文
听风念你 2024-09-23 11:42:00

现有代码的一个严重问题是在空树 (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);
        }
    }   
}

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

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

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

If not them you can only enqueue non-NULL values.

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 NULL in the queue you can do:

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 NULL children (children of leaf nodes) and there is no point in having them enqueued in the queue when we later just don't process them.

回复 原文
谁对谁错谁最难过 2024-09-23 11:42:00

尝试：

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

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);
   }
 }
回复 原文
囍孤女 2024-09-23 11:42:00

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

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]
]

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]
]
回复 原文
零時差 2024-09-23 11:42:00

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

My Java solution using Queue data structure and BFS algorithm:

   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); 
              }
    }
回复 原文
初与友歌 2024-09-23 11:42:00
#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;
}

#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;
}
回复 原文
信愁 2024-09-23 11:42:00

以非常简单的方式实现 BST 全序遍历

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()

A BST all order traversal in very simple Way

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()
回复 原文
~没有更多了~

关于作者

携余温的黄昏

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

苦中寻乐

文章 0 评论 0

lueluelue

文章 0 评论 0

嗼ふ静

文章 0 评论 0

王权女流氓

文章 0 评论 0

与花如笺

文章 0 评论 0

残酷

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文