La inserción en árbol binario de búsqueda (BST)

La inserción en árbol binario de búsqueda : Aquí, vamos a aprender a inserción de un nodo en el árbol de búsqueda binaria ? En este artículo encontrará algoritmo, ejemplo en C ++.

árbol de búsqueda binaria es una de las más importantes estructuras de datos en la informática.

Esta estructura de datos permite a uno buscar y encontrar un elemento con un medio de funcionamiento f tiempo (n) = O (log2 n) . También le permite a uno para insertar y eliminar (Supresión de búsqueda binaria Árbol) elementos. Esta estructura contrasta con la ayuda de la matriz y la lista enlazada.

Supongamos T es un árbol binario. Entonces T se llama un binario if árbol de búsqueda cada Nodo N del árbol T tiene la siguiente propiedad: El valor en N es mayor que todos los valores en el subárbol izquierdo de N y es menos de cada valor en el subárbol derecho de N . (No es difícil ver que las garantías de propiedad que el recorrido en orden de T dará lugar a una ordenados lista de los elementos de T .)

Algoritmo (Esquema):

Supongamos que un elemento de se da información. PUNTO El siguiente algoritmo insertos como un nuevo nodo en su lugar apropiado en el árbol.

(a) Compare ITEM with the root node N of the tree.
(i) If ITEM< N , Proceed to the left Child of N.
(ii) If ITEM > N, proceed to the right child of N.
(b)Repeat Step (a) until one of the following occurs:
(i) We meet a node N such that ITEM=N. In this case the search is successful.
(ii) We meet an empty subtree, which indicates that the search is unsuccessful,
and we insert ITEM in place of the empty subtree.

Considere el programa:

#include<iostream>
using namespace std;
struct node
{
int data;
node* left;
node* right;
};
struct node* getNode(int data)
{
node* newNode=new node();
newNode->data=data;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}
void inorder(struct node* root)
{
if (root != NULL)
{
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
struct node* Insert(struct node* root, int data)
{
if (root == NULL)
return getNode(data);
if (data < root->data)
root->left = Insert(root->left, data);
else if (data > root->data)
root->right = Insert(root->right, data);
return root;
}
int main()
{
node* root=NULL;
root=Insert(root,20);
Insert(root,15);
Insert(root,25);
Insert(root,18);
Insert(root,10);
Insert(root,16);
Insert(root,19);
cout<<"Before Insertion: ";
cout<<"nInorder: ";
inorder(root);
cout<<endl;
root=Insert(root,17);
cout<<"nNode Inserted"<<endl;
cout<<"nAfter Insertion: ";
cout<<"nInorder: ";
inorder(root);
cout<<endl;
return 0;
}

salida

Before Insertion:
Inorder: 10 15 16 18 19 20 25
Node Inserted
After Insertion:
Inorder: 10 15 16 17 18 19 20 25


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *