二叉树插入算法

Question

我最近完成了一个项目的二进制搜索树，我正在工作。很顺利，我学到了很多。然而，现在我需要实现一个常规的二叉树...出于某种原因，这让我难倒了。

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

通常在BST中，您只需检查数据

有谁能帮我实现一个函数，只需将一个新节点从左到右不按特定顺序添加到二叉树中？

以下是我的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);
    }
  }
}

Answer 1

对代码进行一些修改后，我希望这会有所帮助：

Node * Insert(Node * root, int data)
{
  if(root == nullptr)
  {
    Node * NN = new Node();
    root = NN;
    root->data = data;
    root->left = root ->right = NULL;

  }
  else
  {
    if(data < root->data)
    { 
      root->left = Insert(root->left, data);
    }
    else
    {
      root->right = Insert(root->right, data);
    }
  }
  return root;
}

因此，此函数返回更新的BST的根节点。

Answer 2

Javascript实现（为web控制台准备复制粘贴）：

ES6实现（更新的javcript语法与class关键字）

  class BinaryTree {
      constructor(value){
          this.root = value;
          this.left = null;
          this.right = null;
      }

      insert(value){
          var queue = [];
          queue.push(this); //push the root
          while(true){
              var node = queue.pop();
              if(node.left === null){
                  node.left = new BinaryTree(value);
                  return;
              } else {
                  queue.unshift(node.left)
              }

              if(node.right === null){
                node.right = new BinaryTree(value);
                return;
              } else {
                queue.unshift(node.right)
              }
          }
      }
  }

  var myBinaryTree = new BinaryTree(5);
  myBinaryTree.insert(4);
  myBinaryTree.insert(3);
  myBinaryTree.insert(2);
  myBinaryTree.insert(1);

     5
   /   \
  4     3
 / \   (next insertions here)
 2  1    

伪经典模式实现

  var BinaryTree = function(value){
    this.root = value;
    this.left = null;
    this.right = null;
  }

  BinaryTree.prototype.insert = function(value){
    //same logic as before
  }

Answer 3

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

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

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