使用二叉搜索树 C++ 进行广度优先遍历
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17939247/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Breadth First Traversal With Binary Search Tree C++
提问by Conor
Maybe fast/simple Question. I have a a Binary Tree Implemented already, Then I was hoping to convert binary search tree into an array or at least print it out as if in an array. Where I am having trouble with is how to get the NULL/flags in there '\0'.
也许快速/简单的问题。我已经实现了二叉树，然后我希望将二叉搜索树转换为数组，或者至少将其打印出来，就像在数组中一样。我遇到问题的地方是如何在“\0”中获取 NULL/标志。
for example lets say I have a tree like:
例如，假设我有一棵树，如：
10
/ \
6 12
/ \ \
1 8 15
\
4
And I want it to print how its supposed to print. Like:
我希望它打印它应该如何打印。喜欢：
[10,6,12,1,8, 10
/ \
6 12
/ \ \
1 8 15
\
4
,15,void BreadthFirstTravseral(struct 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->data << " ";
if (temp_node->left) {
q.push(temp_node->left);
}
if (temp_node->right) {
q.push(temp_node->right);
}
}
}
,4,if (root) {
q.push(root);
cout << root->data << " ";
} else {
cout << "NULL ";
}
while (!q.empty()) {
const node * const temp_node = q.front();
q.pop();
if (temp_node->left) {
q.push(temp_node->left);
cout << temp_node->left->data << " ";
} else {
cout << "NULL ";
}
if (temp_node->right) {
q.push(temp_node->right);
cout << temp_node->right->data << " ";
} else {
cout << "NULL ";
}
}
,void BreadthFirstTravseral(struct node* root)
{
queue<node*> q;
if (!root) {
return;
}
for (q.push(root); !q.empty(); q.pop()) {
const node * const temp_node = q.front();
if( temp_node->special_blank ){
cout << "\0 " ;
continue;//don't keep pushing blanks
}else{
cout<<temp_node->data << " ";
}
if (temp_node->left) {
q.push(temp_node->left);
}else{
//push special node blank
}
if (temp_node->right) {
q.push(temp_node->right);
}else{
//push special node blank
}
}
}
,std::vector<node*> list;
list.push_back(root);
int i = 0;
while (i != list.size()) {
if (list[i] != null) {
node* n = list[i];
list.push_back(n->left);
list.push_back(n->right);
}
i++;
}
,void TreeBreadthFirst(Node* treeRoot)
{
Queue *queue = new Queue();
if (treeRoot == NULL) return;
queue->insert(treeRoot);
while (!queue->IsEmpty())
{
Node * traverse = queue->dequeue();
cout<< traverse->data << “ “ ;
if (traverse->left != NULL)
queue->insert( traverse->left);
if (traverse->right != NULL)
queue->insert(traverse->right);
}
delete queue;
}
,struct node{
int val;
struct node *l,*r;
};
typedef struct node node;
int findDepth(node *t){
if(!t) return 0;
int l,r;
l=findDepth(t->l);
r=findDepth(t->r);
return l>r?l+1:r+1;
}
void disp(node *t){
if(!t)
return;
int l,r,i=0;
node *a[100],*p;
int front=0,rear=-1,d[100],dep,cur,h;
a[++rear]=t;
d[rear]=0;
cur=-1;
h=findDepth(t);
printf("\nDepth : %d \n",h-1);
while(rear>=front){
dep = d[front];
p=a[front++];
if(dep>cur){
cur=dep;
printf("\n");
for(i=0;i<h-cur;i++) printf("\t");
}
if(p){
printf("%d\t\t",p->val);
a[++rear]=p->l;
d[rear]=dep+1;
a[++rear]=p->r;
d[rear]=dep+1;
}
else printf ("-\t\t");
}
}
,##代码##]
^Something Like this^ I don't know if I counted the NULL correctly.
Or Another Option on how i want to go about showing Visually my Tree is how to get the spacing correctly outputted like with the '/' and '\' pointing to the keys from the parents:
或者关于我想如何在视觉上显示我的树的另一个选项是如何正确输出间距，例如“/”和“\”指向父项的键：
##代码##Here is something that I tried elaborating on code wise but im stuck:
这是我尝试在代码方面详细阐述的内容，但我卡住了：
##代码##Any Kind of Help or Link and or advice and or example code would be very much appreciated.
非常感谢任何类型的帮助或链接和/或建议和/或示例代码。
回答by Ivaylo Strandjev
It will be very hard to get the spacing correctly as a key may have multiple digits and this should affect the spacing for all levels above the given node.
很难正确获得间距，因为一个键可能有多个数字，这应该会影响给定节点上方所有级别的间距。
As for how to add NULL- simply add else clauses for your ifs where you print a NULL:
至于如何添加NULL- 只需为您打印 NULL 的 ifs 添加 else 子句：
回答by jeremyvillalobos
回答by Bogdan B
How about this:
这个怎么样：
##代码##Not tested but I think it should work.
未经测试，但我认为它应该可以工作。
回答by nidhi
回答by Jayadeep KM
I've made a program in c. This code will display somewhat like a tree.
我在 c 中做了一个程序。这段代码的显示有点像一棵树。
##代码##