Algorytm wstawiania drzewa binarnego

Question

Niedawno zakończyłem implementację drzewa wyszukiwania binarnego dla projektu, nad którym pracowałem. Wszystko poszło dobrze i wiele się nauczyłem. Jednak teraz muszę zaimplementować zwykłe drzewo binarne ... które z jakiegoś powodu mnie zaskoczyło.

szukam sposób wykonywać swoją funkcję InsertNode ..

zwykle w BST po prostu sprawdzić, czy dane < korzeń włóż lewy i vice versa. Jednak w normalnym drzewie binarnym jest on po prostu wypełniany od lewej do prawej, jeden poziom na raz ..

Czy ktoś mógłby mi pomóc zaimplementować funkcję, która dodaje nowy węzeł do drzewa binarnego od lewej do prawej w brak konkretnego zamówienia?

Oto mój Włóż do 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

należy spróbować użyć rekurencyjnej podejście takie jak x = new (x), jeśli wiesz, co to znaczy. W ten sposób nie musisz się martwić o węzeł główny. Mam zamiar napisać Pseudokod dla Ciebie:

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

Zrobiłem samouczek dotyczące wdrożenia BST w C++, here

Answer 2

Zdaję sobie sprawę z faktu, że jest to pytanie pisał jakiś czas temu , ale wciąż chciałem podzielić się z nim swoimi przemyśleniami.

Co bym zrobił (skoro to naprawdę nie jest dobrze udokumentowane), skorzystaj z funkcji "Szerokość" (używając kolejki) i wstaw dziecko do pierwszego zera, z którym się spotykam. Zapewni to, że twoje drzewo zapełni poziomy najpierw zanim przejdzie na inny poziom. Przy odpowiedniej liczbie węzłów zawsze będzie kompletna.

Nie pracuję, że wiele z C++, tak aby mieć pewność, że to poprawna Zrobiłem to w Javie, ale masz pomysł:

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

Wziąłem bknopper kodu, modyfikacji trochę i przetłumaczone na C++. Jak stwierdził, co zaskakujące, nie jest to dobrze udokumentowane.

Oto struktura węzeł, a funkcja insert:

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

to nazwać w ten sposób: inserta(&root, val);

Jako główny wskaźnik do węzła struct i Val wartość całkowitą, który chcesz wstawić.

Mam nadzieję, że komuś pomaga.

Answer 4

Z kilku modyfikacjach kodu, mam nadzieję, że to powinno pomóc:

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

Stąd ta funkcja zwraca węzeł główny zaktualizowanego BST.

Answer 5

realizacja Javascript (kopiuj-wklej gotowy do konsoli internetowej):

ES6 realizacji (nowsze składni javscript z klasy hasła)

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 wzór realizacja

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

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