Hemos discutido el inserto BST simple . Cómo insertar en un árbol donde se debe mantener el puntero principal. Los punteros principales son útiles para encontrar rápidamente antepasados de un Node, LCA de dos Nodes, sucesor de un Node, etc.
En llamadas recursivas de inserción simple, devolvemos puntero de raíz de subárbol creado en un subárbol. Entonces, la idea es almacenar este puntero para los subárboles izquierdo y derecho. Establecemos punteros principales de estos punteros devueltos después de las llamadas recursivas. Esto asegura que todos los punteros principales se establezcan durante la inserción. El padre de la raíz se establece en NULL. Manejamos esto asignando padre como NULL de forma predeterminada a todos los Nodes recién asignados.
Implementación:
C++
// C++ program to demonstrate insert operation
// in binary search tree with parent pointer
#include<bits/stdc++.h>
struct Node
{
int key;
struct Node *left, *right, *parent;
};
// A utility function to create a new BST Node
struct Node *newNode(int item)
{
struct Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
temp->parent = NULL;
return temp;
}
// A utility function to do inorder traversal of BST
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("Node : %d, ", root->key);
if (root->parent == NULL)
printf("Parent : NULL \n");
else
printf("Parent : %d \n", root->parent->key);
inorder(root->right);
}
}
/* 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 < node->key)
{
Node *lchild = insert(node->left, key);
node->left = lchild;
// Set parent of root of left subtree
lchild->parent = node;
}
else if (key > node->key)
{
Node *rchild = insert(node->right, key);
node->right = rchild;
// Set parent of root of right subtree
rchild->parent = node;
}
/* return the (unchanged) Node pointer */
return node;
}
// Driver Program to test above functions
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 with parent pointer
class GfG {
static class Node
{
int key;
Node left, right, parent;
}
// A utility function to create a new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
temp.parent = null;
return temp;
}
// A utility function to do inorder traversal of BST
static void inorder(Node root)
{
if (root != null)
{
inorder(root.left);
System.out.print("Node : "+ root.key + " , ");
if (root.parent == null)
System.out.println("Parent : NULL");
else
System.out.println("Parent : " + root.parent.key);
inorder(root.right);
}
}
/* A utility function to insert a new Node with
given key in BST */
static Node insert(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 < node.key)
{
Node lchild = insert(node.left, key);
node.left = lchild;
// Set parent of root of left subtree
lchild.parent = node;
}
else if (key > node.key)
{
Node rchild = insert(node.right, key);
node.right = rchild;
// Set parent of root of right subtree
rchild.parent = node;
}
/* return the (unchanged) Node pointer */
return node;
}
// Driver Program to test above functions
public static void main(String[] args)
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
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);
}
}
Python3
# Python3 program to demonstrate insert operation
# in binary search tree with parent pointer
# A utility function to create a new BST Node
class newNode:
def __init__(self, item):
self.key = item
self.left = self.right = None
self.parent = None
# A utility function to do inorder
# traversal of BST
def inorder(root):
if root != None:
inorder(root.left)
print("Node :", root.key, ", ", end = "")
if root.parent == None:
print("Parent : NULL")
else:
print("Parent : ", root.parent.key)
inorder(root.right)
# A utility function to insert a new
# Node with given key in BST
def insert(node, key):
# If the tree is empty, return a new Node
if node == None:
return newNode(key)
# Otherwise, recur down the tree
if key < node.key:
lchild = insert(node.left, key)
node.left = lchild
# Set parent of root of left subtree
lchild.parent = node
elif key > node.key:
rchild = insert(node.right, key)
node.right = rchild
# Set parent of root of right subtree
rchild.parent = node
# return the (unchanged) Node pointer
return node
# Driver Code
if __name__ == '__main__':
# Let us create following BST
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80
root = None
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)
# This code is contributed by PranchalK
C#
// C# program to demonstrate insert operation
// in binary search tree with parent pointer
using System;
class GfG
{
class Node
{
public int key;
public Node left, right, parent;
}
// A utility function to create a new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
temp.parent = null;
return temp;
}
// A utility function to do
// inorder traversal of BST
static void inorder(Node root)
{
if (root != null)
{
inorder(root.left);
Console.Write("Node : "+ root.key + " , ");
if (root.parent == null)
Console.WriteLine("Parent : NULL");
else
Console.WriteLine("Parent : " +
root.parent.key);
inorder(root.right);
}
}
/* A utility function to insert a new Node with
given key in BST */
static Node insert(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 < node.key)
{
Node lchild = insert(node.left, key);
node.left = lchild;
// Set parent of root of left subtree
lchild.parent = node;
}
else if (key > node.key)
{
Node rchild = insert(node.right, key);
node.right = rchild;
// Set parent of root of right subtree
rchild.parent = node;
}
/* return the (unchanged) Node pointer */
return node;
}
// Driver code
public static void Main(String[] args)
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
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);
}
}
// This code is contributed 29AjayKumar
Javascript
<script>
// javascript program to demonstrate insert operation
// in binary search tree with parent pointer
class Node {
constructor() {
this.key = 0;
this.left = null;
this.right = null;
this.parent = null;
}
}
// A utility function to create a new BST Node
function newNode(item)
{
var temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
temp.parent = null;
return temp;
}
// A utility function to do inorder traversal of BST
function inorder(root)
{
if (root != null)
{
inorder(root.left);
document.write("Node : "+ root.key + " , ");
if (root.parent == null)
document.write("Parent : NULL<br/>");
else
document.write("Parent : " + root.parent.key+"<br/>");
inorder(root.right);
}
}
/* A utility function to insert a new Node with
given key in BST */
function insert(node , key)
{
/* If the tree is empty, return a new Node */
if (node == null) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
{
var lchild = insert(node.left, key);
node.left = lchild;
// Set parent of root of left subtree
lchild.parent = node;
}
else if (key > node.key)
{
var rchild = insert(node.right, key);
node.right = rchild;
// Set parent of root of right subtree
rchild.parent = node;
}
/* return the (unchanged) Node pointer */
return node;
}
// Driver Program to test above functions
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
var 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);
// This code contributed by umadevi9616
</script>
Producción
Node : 20, Parent : 30 Node : 30, Parent : 50 Node : 40, Parent : 30 Node : 50, Parent : NULL Node : 60, Parent : 70 Node : 70, Parent : 50 Node : 80, Parent : 70
Ejercicio:
Cómo mantener el puntero principal durante la eliminación.
Este artículo es una contribución de Shubham Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA