Koska a BST , tehtävänä on lisätä uusi solmu tähän BST .
Esimerkki:
Lisäys binäärihakupuuhun
Arvon lisääminen binäärihakupuuhun:
Uusi avain lisätään aina lehteen säilyttämällä binäärihakupuun ominaisuus. Aloitamme avaimen etsimisen juuresta, kunnes osumme lehtisolmuun. Kun lehtisolmu on löydetty, uusi solmu lisätään lehtisolmun jälkeläiseksi. Alla olevia vaiheita noudatetaan, kun yritämme lisätä solmun binäärihakupuuhun:
- Tarkista lisättävä arvo (esim X ) nykyisen solmun arvolla (esim val ) olemme sisällä:
- Jos X on vähemmän kuin val siirry vasempaan alipuuhun.
- Muussa tapauksessa siirry oikeaan alipuuhun.
- Kun lehtisolmu on saavutettu, aseta se X sen oikealle tai vasemmalle välisen suhteen perusteella X ja lehtisolmun arvo.
Seuraa alla olevaa kuvaa ymmärtääksesi paremmin:
Kuva:
Lisäys BST:hen
Lisäys BST:hen
Lisäys BST:hen
Lisäys BST:hen
Lisäys BST:hen
Lisäys binäärihakupuuhun rekursiolla:
Alla on lisäysoperaation toteutus rekursiolla.
C++14
kumoa viimeinen sitoumus
// C++ program to demonstrate insertion> // in a BST recursively> #include> using> namespace> std;> class> BST {> >int> data;> >BST *left, *right;> public>:> >// Default constructor.> >BST();> >// Parameterized constructor.> >BST(>int>);> >// Insert function.> >BST* Insert(BST*,>int>);> >// Inorder traversal.> >void> Inorder(BST*);> };> // Default Constructor definition.> BST::BST()> >: data(0)> >, left(NULL)> >, right(NULL)> {> }> // Parameterized Constructor definition.> BST::BST(>int> value)> {> >data = value;> >left = right = NULL;> }> // Insert function definition.> BST* BST::Insert(BST* root,>int> value)> {> >if> (!root) {> >// Insert the first node, if root is NULL.> >return> new> BST(value);> >}> >// Insert data.> >if> (value>root-> data) {> >// Insert right node data, if the 'value'> >// to be inserted is greater than 'root' node data.> >// Process right nodes.> >root->oikea = Insert(juuri->oikea, arvo);> >}> >else> if> (value data) {> >// Insert left node data, if the 'value'> >// to be inserted is smaller than 'root' node data.> >// Process left nodes.> >root->vasen = Insert(juuri->vasen, arvo);> >}> >// Return 'root' node, after insertion.> >return> root;> }> // Inorder traversal function.> // This gives data in sorted order.> void> BST::Inorder(BST* root)> {> >if> (!root) {> >return>;> >}> >Inorder(root->vasemmalle);> >cout ' '; Inorder(root->oikea); } // Ohjainkoodi int main() { BST b, *root = NULL; juuri = b.Insert(juuri, 50); b.Insert(juuri, 30); b.Insert(juuri, 20); b.Insert(juuri, 40); b.Insert(juuri, 70); b.Insert(juuri, 60); b.Insert(juuri, 80); b.Inorder(juuri); paluu 0; }> |
>
>
C
// C program to demonstrate insert> // operation in binary> // search tree.> #include> #include> struct> node {> >int> key;> >struct> node *left, *right;> };> // A utility function to create a new BST node> struct> node* newNode(>int> item)> {> >struct> node* temp> >= (>struct> node*)>malloc>(>sizeof>(>struct> node));> >temp->avain = tuote;> >temp->vasen = temp->right = NULL;> >return> temp;> }> // A utility function to do inorder traversal of BST> void> inorder(>struct> node* root)> {> >if> (root != NULL) {> >inorder(root->vasemmalle);> >printf>(>'%d '>, root->avain);> >inorder(root->oikealla);> >}> }> // A utility function to insert> // a new node with given key in BST> struct> node* insert(>struct> node* node,>int> key)> {> >// If the tree is empty, return a new node> >if> (node == NULL)> >return> newNode(key);> >// Otherwise, recur down the tree> >if> (key key)> >node->vasen = insert(solmu->vasen, avain);> >else> if> (key>solmu->avain)> >node->oikea = insert(solmu->oikea, avain);> >// Return the (unchanged) node pointer> >return> node;> }> // Driver Code> int> main()> {> >/* Let us create following BST> >50> >/> >30 70> >/ /> >20 40 60 80 */> >struct> node* root = NULL;> >root = insert(root, 50);> >insert(root, 30);> >insert(root, 20);> >insert(root, 40);> >insert(root, 70);> >insert(root, 60);> >insert(root, 80);> >// Print inorder traversal of the BST> >inorder(root);> >return> 0;> }> |
>
>
Java
// Java program to demonstrate> // insert operation in binary> // search tree> import> java.io.*;> public> class> BinarySearchTree {> >// Class containing left> >// and right child of current node> >// and key value> >class> Node {> >int> key;> >Node left, right;> >public> Node(>int> item)> >{> >key = item;> >left = right =>null>;> >}> >}> >// Root of BST> >Node root;> >// Constructor> >BinarySearchTree() { root =>null>; }> >BinarySearchTree(>int> value) { root =>new> Node(value); }> >// This method mainly calls insertRec()> >void> insert(>int> key) { root = insertRec(root, key); }> >// A recursive function to> >// insert a new key in BST> >Node insertRec(Node root,>int> key)> >{> >// If the tree is empty,> >// return a new node> >if> (root ==>null>) {> >root =>new> Node(key);> >return> root;> >}> >// Otherwise, recur down the tree> >else> if> (key root.left = insertRec(root.left, key); else if (key>root.key) root.right = insertRec(root.right, key); // Palauta (muuttumaton) solmuosoittimen palautusjuuri; } // Tämä menetelmä kutsuu pääasiassa InorderRec() void inorder() { inorderRec(root); } // Aputoiminto // BST:n inorder läpikulku void inorderRec(Solmun juuri) { if (root != null) { inorderRec(root.left); System.out.print(root.key + ' '); inorderRec(root.right); } } // Ohjainkoodi public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Luodaan seuraava BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); puu.lisäys(30); puu.lisäys(20); puu.lisäys(40); puu.lisäys(70); puu.lisäys(60); puu.lisäys(80); // Tulosta BST-puun inorder traversal.inorder(); } } // Tämän koodin tarjoaa Ankur Narain Verma> |
sql concat
>
>
Python 3
# Python program to demonstrate> # insert operation in binary search tree> # A utility class that represents> # an individual node in a BST> class> Node:> >def> __init__(>self>, key):> >self>.left>=> None> >self>.right>=> None> >self>.val>=> key> # A utility function to insert> # a new node with the given key> def> insert(root, key):> >if> root>is> None>:> >return> Node(key)> >else>:> >if> root.val>=>=> key:> >return> root> >elif> root.val root.right = insert(root.right, key) else: root.left = insert(root.left, key) return root # A utility function to do inorder tree traversal def inorder(root): if root: inorder(root.left) print(root.val, end=' ') inorder(root.right) # Driver program to test the above functions if __name__ == '__main__': # Let us create the following BST # 50 # / # 30 70 # / / # 20 40 60 80 r = Node(50) r = insert(r, 30) r = insert(r, 20) r = insert(r, 40) r = insert(r, 70) r = insert(r, 60) r = insert(r, 80) # Print inorder traversal of the BST inorder(r)> |
>
>
C#
// C# program to demonstrate> // insert operation in binary> // search tree> using> System;> class> BinarySearchTree {> >// Class containing left and> >// right child of current node> >// and key value> >public> class> Node {> >public> int> key;> >public> Node left, right;> >public> Node(>int> item)> >{> >key = item;> >left = right =>null>;> >}> >}> >// Root of BST> >Node root;> >// Constructor> >BinarySearchTree() { root =>null>; }> >BinarySearchTree(>int> value) { root =>new> Node(value); }> >// This method mainly calls insertRec()> >void> insert(>int> key) { root = insertRec(root, key); }> >// A recursive function to insert> >// a new key in BST> >Node insertRec(Node root,>int> key)> >{> >// If the tree is empty,> >// return a new node> >if> (root ==>null>) {> >root =>new> Node(key);> >return> root;> >}> >// Otherwise, recur down the tree> >if> (key root.left = insertRec(root.left, key); else if (key>root.key) root.right = insertRec(root.right, key); // Palauta (muuttumaton) solmuosoittimen palautusjuuri; } // Tämä menetelmä kutsuu pääasiassa InorderRec() void inorder() { inorderRec(root); } // Aputoiminto // BST:n inorder läpikulku void inorderRec(Solmun juuri) { if (root != null) { inorderRec(root.left); Console.Write(root.key + ' '); inorderRec(root.right); } } // Ohjainkoodi public static void Main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Luodaan seuraava BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); puu.lisäys(30); puu.lisäys(20); puu.lisäys(40); puu.lisäys(70); puu.lisäys(60); puu.lisäys(80); // Tulosta BST-puun inorder traversal.inorder(); } } // Tämän koodin tarjoaa aashish1995>> |
>
>// javascript program to demonstrate>// insert operation in binary>// search tree>>/*>>* Class containing left and right child of current node and key value>>*/>>class Node {>>constructor(item) {>>this>.key = item;>>this>.left =>this>.right =>null>;>>}>>}>>// Root of BST>>var>root =>null>;>>// This method mainly calls insertRec()>>function>insert(key) {>>root = insertRec(root, key);>>}>>// A recursive function to insert a new key in BST>>function>insertRec(root, key) {>>// If the tree is empty, return a new node>>if>(root ==>null>) {>>root =>new>Node(key);>>return>root;>>}>>// Otherwise, recur down the tree>>if>(key root.left = insertRec(root.left, key); else if (key>root.key) root.right = insertRec(root.right, key); // Palauta (muuttumaton) solmuosoittimen palautusjuuri; } // Tämä menetelmä kutsuu pääasiassa InorderRec()-funktiota inorder() { inorderRec(root); } // Aputoiminto, jolla // tehdään BST-funktion inorder läpikulku inorderRec(root) { if (root != null) { inorderRec(root.left); document.write(root.key+' '); inorderRec(root.right); } } // Ohjainkoodi /* Luodaan seuraava BST 50 / 30 70 / / 20 40 60 80 */ insert(50); insert(30); insert(20); insert(40); insert(70); insert(60); insert(80); // Tulosta inorder traversal of BST inorder(); // Tämän koodin tarjoaa Rajput-Ji>>>20 30 40 50 60 70 80> Aika monimutkaisuus:
- Lisääntymistoimintojen pahin aika monimutkaisuus on Vai niin) missä h on binaarihakupuun korkeus.
- Pahimmassa tapauksessa saatamme joutua matkustamaan juuresta syvimpään lehtisolmuun. Vinopuun korkeus voi nousta n ja lisäystoiminnon aika monimutkaisuus voi tulla Päällä).
Aputila: Apulainen binäärihakupuuhun lisäämisen monimutkaisuus on O(1)
Lisäys binäärihakupuuhun iteratiivisella lähestymistavalla:
Rekursion sijaan voimme toteuttaa lisäysoperaation myös iteratiivisesti käyttämällä a kun silmukka . Alla on toteutus, jossa käytetään while-silmukkaa.
kuinka muuntaa merkkijono int javaksiC++
// C++ Code to insert node and to print inorder traversal>// using iteration>#include>using>namespace>std;>// BST Node>class>Node {>public>:>>int>val;>>Node* left;>>Node* right;>>Node(>int>val)>>: val(val)>>, left(NULL)>>, right(NULL)>>{>>}>};>// Utility function to insert node in BST>void>insert(Node*& root,>int>key)>{>>Node* node =>new>Node(key);>>if>(!root) {>>root = node;>>return>;>>}>>Node* prev = NULL;>>Node* temp = root;>>while>(temp) {>>if>(temp->val> avain) {>>prev = temp;>>temp = temp->vasemmalle;>>}>>else>if>(temp->val prev = lämpötila; lämpötila = lämpötila->oikea; } } if (edellinen->val> avain) prev->vasen = solmu; else prev->right = solmu; } // Aputoiminto tulostaa inorder traversal void inorder(Solmu* root) { Solmu* temp = juuri; pino st; while (temp != NULL || !st.empty()) { if (temp != NULL) { st.push(temp); temp = temp->vasen; } else { temp = st.top(); st.pop(); cout ' '; lämpötila = lämpötila->oikea; } } } // Ohjainkoodi int main() { Solmu* root = NULL; insert(juuri, 30); insert(juuri, 50); insert(juuri, 15); insert(juuri, 20); insert(juuri, 10); insert(juuri, 40); insert(juuri, 60); // Toimintokutsu tulostaa inorder traversal inorder(root); paluu 0; }>>>Java
// Java code to implement the insertion>// in binary search tree>import>java.io.*;>import>java.util.*;>class>GFG {>>// Driver code>>public>static>void>main(String[] args)>>{>>BST tree =>new>BST();>>tree.insert(>30>);>>tree.insert(>50>);>>tree.insert(>15>);>>tree.insert(>20>);>>tree.insert(>10>);>>tree.insert(>40>);>>tree.insert(>60>);>>tree.inorder();>>}>}>class>Node {>>Node left;>>int>val;>>Node right;>>Node(>int>val) {>this>.val = val; }>}>class>BST {>>Node root;>>// Function to insert a key>>public>void>insert(>int>key)>>{>>Node node =>new>Node(key);>>if>(root ==>null>) {>>root = node;>>return>;>>}>>Node prev =>null>;>>Node temp = root;>>while>(temp !=>null>) {>>if>(temp.val>avain) {>>prev = temp;>>temp = temp.left;>>}>>else>if>(temp.val prev = temp; temp = temp.right; } } if (prev.val>avain) prev.left = solmu; else prev.right = solmu; } // Toiminto, joka tulostaa järjestyksen arvon public void inorder() { Node temp = root; Pino pino = new Pino(); while (temp != null || !pino.isEmpty()) { if (temp != null) { pino.add(temp); temp = temp.left; } else { temp = pino.pop(); System.out.print(temp.val + ' '); temp = temp.right; } } } }>>>Python 3
# Python 3 code to implement the insertion># operation iteratively>class>GFG:>>@staticmethod>>def>main(args):>>tree>=>BST()>>tree.insert(>30>)>>tree.insert(>50>)>>tree.insert(>15>)>>tree.insert(>20>)>>tree.insert(>10>)>>tree.insert(>40>)>>tree.insert(>60>)>>tree.inorder()>class>Node:>>left>=>None>>val>=>0>>right>=>None>>def>__init__(>self>, val):>>self>.val>=>val>class>BST:>>root>=>None>># Function to insert a key in the BST>>def>insert(>self>, key):>>node>=>Node(key)>>if>(>self>.root>=>=>None>):>>self>.root>=>node>>return>>prev>=>None>>temp>=>self>.root>>while>(temp !>=>None>):>>if>(temp.val>avain):>>prev>=>temp>>temp>=>temp.left>>elif>(temp.val prev = temp temp = temp.right if (prev.val>avain): prev.left = solmu else: prev.right = solmu # Toiminto, jolla tulostetaan BST:n järjestyksen läpikulku inorder(self): temp = self.root pino = [] while (temp != Ei mitään tai ei (len( pino) == 0)): if (temp != Ei mitään): pino.append(temp) temp = temp.left else: temp = pino.pop() print(str(temp.val) + ' ', end='') temp = temp.right if __name__ == '__main__': GFG.main([]) # Tämän koodin tarjoaa rastogik346.>>>
mistä löydän selaimeni asetukset
// Function to implement the insertion>// operation iteratively>using>System;>using>System.Collections.Generic;>public>class>GFG {>>// Driver code>>public>static>void>Main(String[] args)>>{>>BST tree =>new>BST();>>tree.insert(30);>>tree.insert(50);>>tree.insert(15);>>tree.insert(20);>>tree.insert(10);>>tree.insert(40);>>tree.insert(60);>>// Function call to print the inorder traversal>>tree.inorder();>>}>}>public>class>Node {>>public>Node left;>>public>int>val;>>public>Node right;>>public>Node(>int>val) {>this>.val = val; }>}>public>class>BST {>>public>Node root;>>// Function to insert a new key in the BST>>public>void>insert(>int>key)>>{>>Node node =>new>Node(key);>>if>(root ==>null>) {>>root = node;>>return>;>>}>>Node prev =>null>;>>Node temp = root;>>while>(temp !=>null>) {>>if>(temp.val>avain) {>>prev = temp;>>temp = temp.left;>>}>>else>if>(temp.val prev = temp; temp = temp.right; } } if (prev.val>avain) prev.left = solmu; else prev.right = solmu; } // Toiminto, joka tulostaa BST:n inorder traversalin public void inorder() { Node temp = root; Pino pino = new Pino(); while (temp != null || pino.Count != 0) { if (temp != null) { pino.Push(temp); temp = temp.left; } else { temp = pino.Pop(); Console.Write(temp.val + ' '); temp = temp.right; } } } } // Tämän koodin tarjoaa Rajput-Ji>>>Javascript
// JavaScript code to implement the insertion>// in binary search tree>class Node {>>constructor(val) {>>this>.left =>null>;>>this>.val = val;>>this>.right =>null>;>>}>}>class BST {>>constructor() {>>this>.root =>null>;>>}>>// Function to insert a key>>insert(key) {>>let node =>new>Node(key);>>if>(>this>.root ==>null>) {>>this>.root = node;>>return>;>>}>>let prev =>null>;>>let temp =>this>.root;>>while>(temp !=>null>) {>>if>(temp.val>avain) {>>prev = temp;>>temp = temp.left;>>}>else>if>(temp.val prev = temp; temp = temp.right; } } if (prev.val>avain) prev.left = solmu; else prev.right = solmu; } // Toiminto inorder-arvon tulostamiseksi inorder() { let temp = this.root; anna pino = []; while (temp != null || pino.pituus> 0) { if (temp != null) { pino.push(temp); temp = temp.left; } else { temp = pino.pop(); console.log(temp.val + ' '); temp = temp.right; } } } } anna puu = new BST(); puu.lisäys(30); puu.lisäys(50); puu.lisäys(15); puu.lisäys(20); puu.lisäys(10); puu.lisäys(40); puu.lisäys(60); puu.inorder(); // tämän koodin on kehittänyt devendrasolunke>>>10 15 20 30 40 50 60> The aika monimutkaisuus / tilauksen läpikulku On Päällä) , koska jokaisessa solmussa käydään kerran.
The Aputila On Päällä) , koska käytämme pinoa solmujen tallentamiseen rekursiota varten.Liittyvät linkit:
- Binäärihakupuuhakutoiminto
- Binäärihakupuun poistotoiminto