这是二叉树的层序遍历的正确方式吗?

huangapple go评论70阅读模式
英文:

Is this the correct way to do level-order traversal of Binary tree?

问题

你编写的代码输出是正确的。我只是想知道这种方法是否会在较大的输入大小下遇到问题。

英文:

The code which I have written gives the correct output. I just wanted to know if this method will run into problems with larger input sizes.

#include <bits/stdc++.h> 
using namespace std;

//LEVEL ORDER TRAVERSAL

class node{
 private: int data;
 public : node* left=NULL;node *right=NULL;
 node(int dat){
     data=dat;
 } 
 int getVal(){
     return data;
 }
};

void level_order(node *a,queue<node*> q){
  if(a->left!=NULL){
    q.push(a->left);
  }
  if(a->right!=NULL){
    q.push(a->right);
  }
  cout<<a->getVal()<<",";
  q.pop();
  if(!q.empty()){
  level_order(q.front(),q);}
}

int main(){
    node* root=new node(1);
    root->left=new node(2);
    root->right=new node(3);
    root->left->left=new node(4);
    root->left->right=new node(5);
    root->left->right->left=new node(6);
    root->right->left=new node(7);
    root->right->right=new node(8);
    root->right->right->left=new node(9);
    root->right->right->right=new node(10);
    queue<node*> a;
    a.push(root);
    level_order(root,a);
    return 0;
}

I am just getting started with Data Structures. Sorry if this seems like a silly question.

答案1

得分: 2

如果树是退化的(偏斜),即它完全不平衡(节点从不具有两个子节点,每个级别只有一个节点),那么级别的数量是O(𝑛),因此递归所需的堆栈空间也是O(𝑛)。这意味着你可能会达到堆栈空间限制... 但如果你确信树的高度是O(log𝑛),那就没有问题。

不过,由于该函数是尾递归,你可以轻松将其重写为迭代过程。

其他注意事项

这是一个可能的迭代级别顺序遍历的实现:

void levelOrder(std::queue<Node*> nodes) {
    while (!nodes.empty()) {
        Node *root = nodes.front();
        nodes.pop();
        std::cout << root->getVal() << ",";
        if (root->left) {
            nodes.push(root->left);
        }
        if (root->right) {
            nodes.push(root->right);
        }
    }
}
英文:

If the tree is degenerate (skewed) in the sense that it is completely unbalanced (nodes never have two children, i.e. each level has just one node), then the number of levels is O(𝑛), and thus the stack space needed for recursion is also O(𝑛). This means you could hit the stack space limit... If however you are confident the tree will have a height that is O(log𝑛), then there is no issue.

Still, as that function is tail recursive, you can easily rewrite it as an iterative procedure.

Other remarks

Here is a possible iterative implementation of a level order traversal:

void levelOrder(std::queue<Node*> nodes) {
    while (!nodes.empty()) {
        Node *root = nodes.front();
        nodes.pop();
        std::cout << root->getVal() << ",";
        if (root->left) {
            nodes.push(root->left);
        }
        if (root->right) {
            nodes.push(root->right);
        }
    }
}

huangapple
  • 本文由 发表于 2023年6月26日 17:37:42
  • 转载请务必保留本文链接:https://go.coder-hub.com/76555431.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定