Thuật toán chèn cây nhị phân

Question

Gần đây tôi đã hoàn thành việc triển khai cây tìm kiếm nhị phân cho một dự án mà tôi đang làm việc. Nó diễn ra tốt đẹp và tôi đã học được rất nhiều. Tuy nhiên, bây giờ tôi cần phải thực hiện một cây nhị phân thường xuyên ... mà vì một lý do nào đó khiến tôi bối rối.

Tôi đang tìm kiếm một cách để làm chức năng InsertNode tôi ..

bình thường trong BST bạn chỉ cần kiểm tra xem dữ liệu < gốc sau đó chèn trái và ngược lại. Tuy nhiên, trong một cây nhị phân bình thường, nó chỉ được điền từ trái sang phải, một cấp tại một thời điểm ..

bất cứ ai có thể giúp tôi thực hiện một chức năng mà chỉ cần thêm một nút mới vào cây nhị phân từ trái sang phải trong không có thứ tự cụ thể?

Dưới đây là Insert của tôi cho một 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

Bạn nên cố gắng sử dụng một cách tiếp cận đệ quy như x = new (x), nếu bạn biết điều đó có nghĩa là gì. Bằng cách này, bạn không thực sự phải lo lắng về nút gốc. Tôi sẽ viết một số mã giả dành cho bạn:

//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  
} 

tôi đã thực hiện một hướng dẫn liên quan đến việc thực hiện một BST trong C++, here

Answer 2

Tôi nhận thức được thực tế rằng đây là một câu hỏi được đăng một số thời gian trước đây nhưng tôi vẫn muốn chia sẻ suy nghĩ của mình về nó.

Những gì tôi sẽ làm (vì điều này thực sự không được tài liệu rất tốt) là sử dụng một Breadth-First-Search (sử dụng một hàng đợi) và chèn con vào null đầu tiên tôi gặp phải. Điều này sẽ đảm bảo rằng cây của bạn sẽ lấp đầy các cấp độ đầu tiên trước khi nó đi đến một cấp độ khác. Với số lượng nút phù hợp, nó sẽ luôn được hoàn thành.

Tôi chưa từng làm việc nhiều với C++, vì vậy để đảm bảo nó là đúng tôi đã làm nó trong Java, nhưng bạn sẽ có được ý tưởng:

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

tôi mất bknopper mã, sửa đổi một chút và được dịch sang C++. Như ông đã nói, đáng ngạc nhiên, điều này không được ghi chép đầy đủ.

Dưới đây là cấu trúc nút và các chức năng chèn:

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

Bạn gọi nó theo cách này: inserta(&root, val);

Là rễ một con trỏ đến nút struct và val giá trị số nguyên bạn muốn chèn.

Hy vọng nó sẽ giúp ai đó.

Answer 4

Với một vài sửa đổi mã của bạn, tôi hy vọng điều này sẽ giúp:

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

Do đó, chức năng này sẽ trả về nút gốc của BST được cập nhật.

Answer 5

javascript thực hiện (copy-dán sẵn sàng cho giao diện điều khiển web của bạn):

ES6 thực hiện (cú pháp javscript mới với từ khoá 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  

mẫu Pseudoclassical thực hiện

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

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