二叉树插入算法 [英] Binary Tree Insert Algorithm

问题描述

我最近完成实现的二进制搜索树的一个项目我工作。它顺利，我学到了很多东西。不过，现在我需要实现一个普通二叉树...由于某种原因已经难倒我。

I recently finished implementing a Binary search tree for a project I was working on. It went well and I learned a lot. However, now I need to implement a regular Binary Tree... which for some reason has me stumped.

我在寻找一种方式做我InsertNode功能。

I'm looking for a way to do my InsertNode function..

通常在BST你只检查数据是否＆LT;根然后插入左，反之亦然。然而，在一个正常的二叉树，它只是从一次从左到右，一层一层充满..

normally in a BST you just check if data < root then insert left and vice versa. However, In a normal Binary tree, it is just filled from left to right, one level at a time..

任何人都可以帮我实现一个功能，只是增加了一个新的节点二叉树从左至右中没有特定的顺序？

could anyone help me implement a function that just adds a new Node to the Binary tree from left to right in no specific order?

下面是我的一个BST插入：

Here's my Insert for a 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);
    }
  }
}

感谢任何帮助将是AP preciated！

Thanks any help would be appreciated!

推荐答案

我知道的事实，这是一个问题发布前一段时间，但我还是想分享就可以了我的想法。

I am aware of the fact that this is a question posted some time ago, but I still wanted to share my thoughts on it.

我会做什么（因为这确实不是非常有据可查）是使用广度优先搜索（使用队列），然后将孩子带到第一个空我遇到的问题。这将确保你的树会首先填补水平它去到另一个层次了。随着节点的正确数量，它将始终是完整的。

What I would do (since this indeed is not very well documented) is use a Breadth-First-Search (using a queue) and insert the child into the first null I encounter. This will ensure that your tree will fill up the levels first before it goes to another level. With the right number of nodes, it will always be complete.

我没有工作，许多使用C ++，所以，以确保它是正确的，我做到了在Java中，但你的想法：

I haven't worked that much with c++, so to be sure it was correct I did it in Java, but you get the idea:

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

这篇关于二叉树插入算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！