Мы обсудили простую вставку BST . Как вставить в дерево, где родительский указатель должен быть сохранен. Родительские указатели полезны для быстрого поиска предков узла, LCA двух узлов, преемника узла и т. Д.
В рекурсивных вызовах простой вставки мы возвращаем указатель корня поддерева, созданного в поддереве. Таким образом, идея состоит в том, чтобы сохранить этот указатель для левого и правого поддеревьев. Мы устанавливаем родительские указатели для этих возвращаемых указателей после рекурсивных вызовов. Это гарантирует, что все родительские указатели будут установлены во время вставки. Родитель корня установлен в NULL. Мы справляемся с этим, присваивая parent как NULL по умолчанию всем вновь выделенным узлам.
C ++
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int key;
struct Node *left, *right, *parent;
};
struct Node *newNode(int item)
{
struct Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
temp->parent = NULL;
return temp;
}
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);
}
}
struct Node* insert(struct Node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key)
{
Node *lchild = insert(node->left, key);
node->left = lchild;
lchild->parent = node;
}
else if (key > node->key)
{
Node *rchild = insert(node->right, key);
node->right = rchild;
rchild->parent = node;
}
return node;
}
int main()
{
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);
inorder(root);
return 0;
}
|
Джава
class GfG {
static class Node
{
int key;
Node left, right, parent;
}
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
temp.parent = null;
return temp;
}
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);
}
}
static Node insert(Node node, int key)
{
if (node == null) return newNode(key);
if (key < node.key)
{
Node lchild = insert(node.left, key);
node.left = lchild;
lchild.parent = node;
}
else if (key > node.key)
{
Node rchild = insert(node.right, key);
node.right = rchild;
rchild.parent = node;
}
return node;
}
public static void main(String[] args)
{
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);
inorder(root);
}
}
|
python3
class newNode:
def __init__(self, item):
self.key = item
self.left = self.right = None
self.parent = None
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)
def insert(node, key):
if node == None:
return newNode(key)
if key < node.key:
lchild = insert(node.left, key)
node.left = lchild
lchild.parent = node
elif key > node.key:
rchild = insert(node.right, key)
node.right = rchild
rchild.parent = node
return node
if __name__ == '__main__':
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)
inorder(root)
|
C #
using System;
class GfG
{
class Node
{
public int key;
public Node left, right, parent;
}
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
temp.parent = null;
return temp;
}
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);
}
}
static Node insert(Node node, int key)
{
if (node == null) return newNode(key);
if (key < node.key)
{
Node lchild = insert(node.left, key);
node.left = lchild;
lchild.parent = node;
}
else if (key > node.key)
{
Node rchild = insert(node.right, key);
node.right = rchild;
rchild.parent = node;
}
return node;
}
public static void Main(String[] args)
{
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);
inorder(root);
}
}
|
Выход :
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
Упражнение:
Как сохранить родительский указатель во время удаления.
Эта статья предоставлена Shubham Gupta . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Рекомендуемые посты:
Вставка двоичного дерева поиска с родительским указателем
0.00 (0%) 0 votes