二叉树插入算法

我最近完成了我正在从事的一个项目的二叉搜索树的实现。一切都很顺利，我学到了很多东西。然而，现在我需要实现一个常规的二叉树......由于某种原因，这让我感到困惑。

我正在寻找一种方法来执行我的 InsertNode 功能..

通常在 BST 中，您只需检查 data

谁能帮助我实现一个函数，该函数仅以不特定顺序从左到右将新节点添加到二叉树中？

这是我的 BST 插入内容：

void Insert(Node *& root, int data)
{
  if(root == nullptr)
  {
    Node * NN = new Node;
    root = NN;
  }
  else
  {
    if(data < root->data)
    { 
      Insert(root->left, data);
    }
    else
    {
      Insert(root->right, data);
    }
  }
}

我知道这是一个不久前发布的问题，但我仍然想分享我的想法。

我要做的（因为这确实没有很好的记录）是使用广度优先搜索（使用队列）并将子项插入到我遇到的第一个空值中。这将确保您的树在进入另一个级别之前首先填满级别。有了正确数量的节点，它就总是完整的。

我没有太多使用 C++ 的工作，所以为了确保它是正确的，我用 Java 做了它，但你明白了：

public void insert(Node node) {
    if(root == null) {
        root = node;
        return;
    }

    /* insert using Breadth-first-search (queue to the rescue!) */
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(root);

    while(true) {
        Node n = queue.remove();
        if(!n.visited) System.out.println(n.data);
        n.visited = true;

        if(n.left == null) {
            n.left = node;
            break;
        } else {
            queue.offer(n.left);
        }           

        if(n.right == null) {
            n.right = node;
            break;
        } else {
            queue.offer(n.right);
        }
    }
}