英文:
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𝑛),那就没有问题。
不过,由于该函数是尾递归,你可以轻松将其重写为迭代过程。
其他注意事项
- 不要使用
#include <bits/stdc++.h>
。而是包含你需要的标准库(在这种情况下是iostream
和queue
)。 - 不要使用
using namespace std
- 最好在C++中使用
nullptr
- 不需要显式与
NULL
进行比较 - 将独立的语句放在独立的行上。不要这样写:
public : node* left=NULL;node *right=NULL;
- 将关闭大括号放在行的开头,不要这样写:
level_order(q.front(),q);}
- 使用有意义的名称。
a
是没有意义的。q
还好,因为它是命名队列变量的常见做法。 level_order
传递一个也在队列前面的节点:这是过度的:你可以只传递队列并让第一个操作是提取前面的元素。
这是一个可能的迭代级别顺序遍历的实现:
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
- Don't use
#include <bits/stdc++.h>
. Instead include the standard libraries you need (iostream
andqueue
in this case). - Don't use
using namespace std
- Preferrably use
nullptr
in C++ - Explicitly comparing with
NULL
is not needed - Put separate statements on separate lines. So not
public : node* left=NULL;node *right=NULL;
- Put closing braces at the start of a line, so not
level_order(q.front(),q);}
- Use meaningful names.
a
is meaningless.q
is not so bad, as it is common practice for naming a queue variable. level_order
passes a node that is also at the front of the queue: this is overkill: you might as well only pass the queue and let the first action be to extract that front element.
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);
}
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论