Рубрики

Вставка двоичного дерева поиска с родительским указателем

Мы обсудили простую вставку BST . Как вставить в дерево, где родительский указатель должен быть сохранен. Родительские указатели полезны для быстрого поиска предков узла, LCA двух узлов, преемника узла и т. Д.

В рекурсивных вызовах простой вставки мы возвращаем указатель корня поддерева, созданного в поддереве. Таким образом, идея состоит в том, чтобы сохранить этот указатель для левого и правого поддеревьев. Мы устанавливаем родительские указатели для этих возвращаемых указателей после рекурсивных вызовов. Это гарантирует, что все родительские указатели будут установлены во время вставки. Родитель корня установлен в NULL. Мы справляемся с этим, присваивая parent как NULL по умолчанию всем вновь выделенным узлам.

C ++

// C ++ программа для демонстрации операции вставки
// в двоичном дереве поиска с родительским указателем
#include<stdio.h>
#include<stdlib.h>

  

struct Node

{

    int key;

    struct Node *left, *right, *parent;

};

  
// Вспомогательная функция для создания нового узла BST

struct Node *newNode(int item)

{

    struct Node *temp =  new Node;

    temp->key = item;

    temp->left = temp->right = NULL;

    temp->parent = NULL;

    return temp;

}

  
// Утилита для обхода порядка следования 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);

    }

}

  
/ * Утилита для вставки нового узла с

   данный ключ в BST * /

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()

{

    / * Давайте создадим следующий 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);

  

    // распечатать iNoder обход BST

    inorder(root);

  

    return 0;

}

Джава

// Java-программа для демонстрации операции вставки
// в двоичном дереве поиска с родительским указателем

class GfG { 

  

static class Node 

    int key; 

    Node left, right, parent; 

}

  
// Вспомогательная функция для создания нового узла BST

static Node newNode(int item) 

    Node temp = new Node(); 

    temp.key = item; 

    temp.left = null;

    temp.right = null

    temp.parent = null

    return temp; 

  
// Утилита для обхода порядка следования 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); 

    

  
/ * Утилита для вставки нового узла с
данный ключ в BST * /

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) 

    / * Давайте создадим следующий 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); 

  

    // распечатать iNoder обход BST

    inorder(root); 

}

python3

# Python3 программа для демонстрации операции вставки
# в двоичном дереве поиска с родительским указателем

  
# Утилита для создания нового узла BST

class newNode:

    def __init__(self, item):

        self.key = item 

        self.left = self.right = None

        self.parent = None

  
# Полезная функция, чтобы сделать заказ
# обход 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)

  
# Полезная функция для вставки нового
# Узел с данным ключом в BST

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__':

      

    # Давайте создадим следующий 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 iNoder обход BST

    inorder(root)

  
# Этот код предоставлен PranchalK

C #

// C # программа для демонстрации операции вставки
// в двоичном дереве поиска с родительским указателем

using System;

  

class GfG 

    class Node 

    

        public int key; 

        public Node left, right, parent; 

    

  

    // Вспомогательная функция для создания нового узла BST

    static Node newNode(int item) 

    

        Node temp = new Node(); 

        temp.key = item; 

        temp.left = null

        temp.right = null

        temp.parent = null

        return temp; 

    

  

    // Полезная функция для выполнения

    // обход порядка 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); 

        

    

  

    / * Утилита для вставки нового узла с

    данный ключ в BST * /

    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) 

    

        / * Давайте создадим следующий 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); 

  

        // распечатать iNoder обход BST

        inorder(root); 

    

  
// Этот код предоставлен 29AjayKumar


Выход :

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