二进制搜索树C ++的广度优先遍历 [英] Breadth First Traversal With Binary Search Tree C++

问题描述

也许是快速/简单的问题.我已经实现了一个二叉树，然后我希望将二叉搜索树转换为数组，或者至少将其打印出来，就像在数组中一样.我遇到麻烦的地方是如何在其中'\ 0'中获得NULL/标志.

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'.

例如，假设我有一棵像这样的树:

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,\0,15,\0,4,\0,\0,\0,\0,\0,\0]
        ^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:

                10
               /  \
              6   12
             / \   \
            1  8   15
             \
              4   

这是我尝试在代码方面进行详细阐述但被卡住的内容:

Here is something that I tried elaborating on code wise but im stuck:

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

非常感谢您提供任何帮助或链接和/或建议和/或示例代码.

Any Kind of Help or Link and or advice and or example code would be very much appreciated.

推荐答案

由于键可能具有多个数字，因此很难正确获得间距.这将影响给定节点上方所有层的间距.

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.

关于如何添加NULL-只需在打印NULL的ifs中添加else子句:

As for how to add NULL - simply add else clauses for your ifs where you print a NULL:

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

这篇关于二进制搜索树C ++的广度优先遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！