Рубрики

Найти родителя узла в данном двоичном дереве

По заданному дереву и узлу задача состоит в том, чтобы найти родителя данного узла в дереве. Выведите -1, если данный узел является корневым узлом.

Примеры:

Input: Node = 3
     1
   /   \
  2     3
 / \
4   5
Output: 1

Input: Node = 1
     1
   /   \
  2     3
 /       \
4         5
         /
        6
Output: -1

Подход: напишите рекурсивную функцию, которая принимает текущий узел и его родителя в качестве аргументов (корневой узел передается с -1 в качестве его родителя). Если текущий узел равен требуемому узлу, выведите его родительский элемент и вернитесь, иначе вызовите функцию рекурсивно для его дочерних узлов и текущего узла в качестве родительского.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

  
/ * Узел двоичного дерева имеет данные, указатель
оставить ребенка и указатель
правый ребенок * /

struct Node {

    int data;

    struct Node *left, *right;

    Node(int data)

    {

        this->data = data;

        left = right = NULL;

    }

};

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

void findParent(struct Node* node,

                int val, int parent)

{

    if (node == NULL)

        return;

  

    // Если текущий узел является обязательным узлом

    if (node->data == val) {

  

        // Распечатать свой родительский

        cout << parent;

    }

    else {

  

        // Рекурсивные звонки для детей

        // текущего узла

        // Текущий узел теперь новый родитель

        findParent(node->left, val, node->data);

        findParent(node->right, val, node->data);

    }

}

  
// Код драйвера

int main()

{

    struct Node* root = new Node(1);

    root->left = new Node(2);

    root->right = new Node(3);

    root->left->left = new Node(4);

    root->left->right = new Node(5);

    int node = 3;

  

    findParent(root, node, -1);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

  
/ * Узел двоичного дерева имеет данные, указатель
оставить ребенка и указатель
правый ребенок * /

static class Node 

{

    int data;

    Node left, right;

    Node(int data)

    {

        this.data = data;

        left = right = null;

    }

};

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

static void findParent(Node node,

                       int val, int parent)

{

    if (node == null)

        return;

  

    // Если текущий узел является обязательным узлом

    if (node.data == val) 

    {

  

        // Распечатать свой родительский

        System.out.print(parent);

    }

    else 

    {

  

        // Рекурсивные звонки для детей

        // текущего узла

        // Текущий узел теперь новый родитель

        findParent(node.left, val, node.data);

        findParent(node.right, val, node.data);

    }

}

  
// Код драйвера

public static void main(String []args)

{

    Node root = new Node(1);

    root.left = new Node(2);

    root.right = new Node(3);

    root.left.left = new Node(4);

    root.left.right = new Node(5);

    int node = 3;

  

    findParent(root, node, -1);

}
}

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

C #

// C # реализация подхода

using System;

      

class GFG

{

  
/ * Узел двоичного дерева имеет данные, указатель
оставить ребенка и указатель
правый ребенок * /

public class Node 

{

    public int data;

    public Node left, right;

    public Node(int data)

    {

        this.data = data;

        left = right = null;

    }

};

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

static void findParent(Node node,

                         int val, int parent)

{

    if (node == null)

        return;

  

    // Если текущий узел является обязательным узлом

    if (node.data == val) 

    {

  

        // Распечатать свой родительский

        Console.Write(parent);

    }

    else

    {

  

        // Рекурсивные звонки для детей

        // текущего узла

        // Текущий узел теперь новый родитель

        findParent(node.left, val, node.data);

        findParent(node.right, val, node.data);

    }

}

  
// Код драйвера

public static void Main(String []args)

{

    Node root = new Node(1);

    root.left = new Node(2);

    root.right = new Node(3);

    root.left.left = new Node(4);

    root.left.right = new Node(5);

    int node = 3;

  

    findParent(root, node, -1);

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

1

Рекомендуемые посты:

Найти родителя узла в данном двоичном дереве

0.00 (0%) 0 votes