二叉树插入算法

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

你应该尝试使用递归方法如X =新的（X），如果你知道这意味着什么。这样，你不必担心根节点。我会写一些伪代码给你：

//public function 
add(data){ 
    root = add(data, root) 
} 

//private helper function 
Node add(data, currentNode){ 
    if(currentNode = 0) 
     return new Node(data) 

    if(data less than currentNode's data) 
     currentNode.left = add(data, currentNode.left) 
    if(data more than currentNode's data) 
     currentNode.right = add(data, currentNode.right) 

    return currentNode  
} 

我做了关于C++中的BST实施的教程，here

Answer 2

我知道的事实，这是一个问题发布前一段时间，但我仍然想分享我的想法。

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

我没有工作，许多用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); 
     } 
    } 
} 

Answer 3

我把bknopper代码，修改一点点，转换为C++。正如他所说，令人惊讶的是，这没有很好的记录。

这里是节点结构和插入功能：

struct nodo 
{ 
    nodo(): izd(NULL), der(NULL) {}; 
    int val; 
    struct nodo* izd; 
    struct nodo* der; 
}; 

void inserta(struct nodo** raiz, int num) 
{ 

if(!(*raiz)) 
{ 
    *raiz = new struct nodo; 
    (*raiz)->val = num; 
} 
else 
{ 

    std::deque<struct nodo*> cola; 
    cola.push_back( *raiz ); 

    while(true) 
    { 
     struct nodo *n = cola.front(); 
     cola.pop_front(); 

     if(!n->izd) { 
      n->izd = new struct nodo; 
      n->izd->val = num; 
      break; 
     } else { 
      cola.push_back(n->izd); 
     } 

     if(!n->der) { 
      n->der = new struct nodo; 
      n->der->val = num; 
      break; 
     } else { 
      cola.push_back(n->der); 
     } 
    } 
    } 
} 

你这样调用它： inserta(&root, val);

作为根本指针到节点结构和Val要插入整数值。

希望它可以帮助别人。

Answer 4

有了一些修改你的代码，我希望这将有助于：

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 5

Javascript实现（复制粘贴准备好您的Web控制台）：

ES6实现（用class关键字新javscript语法）

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  

Pseudoclassical模式实现

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

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