Рубрики

Проверьте, являются ли два узла двоюродными братьями в двоичном дереве

Деревья

Учитывая, что двоичное дерево и два узла говорят «a» и «b», определите, являются ли два узла кузенами друг друга или нет.

Два узла являются двоюродными братьями друг друга, если они находятся на одном уровне и имеют разных родителей.

Пример:

     6
   /   \
  3     5
 / \   / \
7   8 1   3
Say two node be 7 and 1, result is TRUE.
Say two nodes are 3 and 5, result is FALSE.
Say two nodes are 7 and 5, result is FALSE.

Идея состоит в том, чтобы найти уровень одного из узлов. Используя найденный уровень, проверьте, находятся ли «a» и «b» на этом уровне. Если «a» и «b» находятся на заданном уровне, то, наконец, проверьте, не являются ли они потомками одного и того же родителя.

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

С

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

  
// Узел двоичного дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Утилита для создания нового узла Binary Tree

struct Node *newNode(int item)

{

    struct Node *temp =  (struct Node *)malloc(sizeof(struct Node));

    temp->data = item;

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

    return temp;

}

  
// Рекурсивная функция, чтобы проверить, являются ли два Узла родными

int isSibling(struct Node *root, struct Node *a, struct Node *b)

{

    // Базовый вариант

    if (root==NULL)  return 0;

  

    return ((root->left==a && root->right==b)||

            (root->left==b && root->right==a)||

            isSibling(root->left, a, b)||

            isSibling(root->right, a, b));

}

  
// Рекурсивная функция для поиска уровня узла 'ptr' в двоичном дереве

int level(struct Node *root, struct Node *ptr, int lev)

{

    // базовые случаи

    if (root == NULL) return 0;

    if (root == ptr)  return lev;

  

    // Возвращаем уровень, если Node присутствует в левом поддереве

    int l = level(root->left, ptr, lev+1);

    if (l != 0)  return l;

  

    // Остальное поиск в правом поддереве

    return level(root->right, ptr, lev+1);

}

  

  
// Возвращает 1, если a и b двоюродные братья, иначе 0

int isCousin(struct Node *root, struct Node *a, struct Node *b)

{

    // 1. Два узла должны быть на одном уровне в двоичном дереве.

    // 2. Два Узла не должны быть братьями и сестрами (это означает, что они должны

    // не иметь того же родительского узла).

    if ((level(root,a,1) == level(root,b,1)) && !(isSibling(root,a,b)))

        return 1;

    else return 0;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->left->right->right = newNode(15);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

    root->right->left->right = newNode(8);

  

    struct Node *Node1,*Node2;

    Node1 = root->left->left;

    Node2 = root->right->right;

  

    isCousin(root,Node1,Node2)? puts("Yes"): puts("No");

  

    return 0;

}

Джава

// Java-программа для проверки, являются ли два двоичных дерева кузенами

class Node

{

    int data;

    Node left, right;

  

    Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree

{

    Node root;

  

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

    // братья и сестры

    boolean isSibling(Node node, Node a, Node b)

    {

        // Базовый вариант

        if (node == null)

            return false;

  

        return ((node.left == a && node.right == b) ||

                (node.left == b && node.right == a) ||

                isSibling(node.left, a, b) ||

                isSibling(node.right, a, b));

    }

  

    // Рекурсивная функция для определения уровня узла 'ptr' в

    // двоичное дерево

    int level(Node node, Node ptr, int lev)

    {

        // базовые случаи

        if (node == null)

            return 0;

  

        if (node == ptr)

            return lev;

  

        // Возвращаем уровень, если Node присутствует в левом поддереве

        int l = level(node.left, ptr, lev + 1);

        if (l != 0)

            return l;

  

        // Остальное поиск в правом поддереве

        return level(node.right, ptr, lev + 1);

    }

  

    // Возвращает 1, если a и b двоюродные братья, иначе 0

    boolean isCousin(Node node, Node a, Node b)

    {

        // 1. Два узла должны быть на одном уровне

        // в двоичном дереве.

        // 2. Два узла не должны быть братьями и сестрами (значит

        // что у них не должно быть одного и того же родителя

        // Узел).

        return ((level(node, a, 1) == level(node, b, 1)) &&

                (!isSibling(node, a, b)));

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

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

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

        tree.root.left.right.right = new Node(15);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

        tree.root.right.left.right = new Node(8);

  

        Node Node1, Node2;

        Node1 = tree.root.left.left;

        Node2 = tree.root.right.right;

        if (tree.isCousin(tree.root, Node1, Node2))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

# Программа Python для проверки наличия двух узлов в двоичном файле
# дерево кузены

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового двоичного дерева

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  

def isSibling(root, a , b):

  

    # Базовый вариант

    if root is None:

        return 0

  

    return ((root.left == a and root.right ==b) or 

            (root.left == b and root.right == a)or

            isSibling(root.left, a, b) or

            isSibling(root.right, a, b))

  
# Рекурсивная функция для определения уровня узла 'ptr' в
# двоичное дерево

def level(root, ptr, lev):

      

    # Базовый вариант

    if root is None :

        return 0 

    if root == ptr: 

        return lev

  

    # Уровень возврата, если в левом поддереве присутствует узел

    l = level(root.left, ptr, lev+1)

    if l != 0:

        return l

  

    # Остальное поиск в правом поддереве

    return level(root.right, ptr, lev+1)

  

  
# Возвращает 1, если a и b двоюродные братья, в противном случае 0

def isCousin(root,a, b):

      

    # 1. Два узла должны быть на одном уровне в

    # двоичное дерево

    # Два узла не должны быть братьями и сестрами (это означает, что

    # у них не должно быть родительского узла smae

  

    if ((level(root,a,1) == level(root, b, 1)) and 

            not (isSibling(root, a, b))):

        return 1

    else:

        return 0 

  

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.left.right.right = Node(15)

root.right.left = Node(6)

root.right.right = Node(7)

root.right.left.right = Node(8)

  

node1 = root.left.right

node2 = root.right.right 

  

print "Yes" if isCousin(root, node1, node2) == 1 else "No"

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для проверки, если два бинарных
// дерево кузены

using System;

  

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

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

public virtual bool isSibling(Node node, 

                              Node a, Node b)

{

    // Базовый вариант

    if (node == null)

    {

        return false;

    }

  

    return ((node.left == a && node.right == b) || 

            (node.left == b && node.right == a) || 

                     isSibling(node.left, a, b) || 

                     isSibling(node.right, a, b));

}

  
// Рекурсивная функция для поиска уровня
// узла 'ptr' в двоичном дереве

public virtual int level(Node node, Node ptr, int lev)

{

    // базовые случаи

    if (node == null)

    {

        return 0;

    }

  

    if (node == ptr)

    {

        return lev;

    }

  

    // Возвращаем уровень, если Node присутствует

    // в левом поддереве

    int l = level(node.left, ptr, lev + 1);

    if (l != 0)

    {

        return l;

    }

  

    // Остальное поиск в правом поддереве

    return level(node.right, ptr, lev + 1);

}

  
// Возвращает 1, если a и b двоюродные братья,
// иначе 0

public virtual bool isCousin(Node node, 

                             Node a, Node b)

{

    // 1. Два узла должны быть на

    // тот же уровень в двоичном дереве.

    // 2. Два узла не должны быть братьями и сестрами

    // (означает, что они не должны иметь

    // тот же родительский узел).

    return ((level(node, a, 1) == level(node, b, 1)) && 

                            (!isSibling(node, a, b)));

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

    tree.root = new Node(1);

    tree.root.left = new Node(2);

    tree.root.right = new Node(3);

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

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

    tree.root.left.right.right = new Node(15);

    tree.root.right.left = new Node(6);

    tree.root.right.right = new Node(7);

    tree.root.right.left.right = new Node(8);

  

    Node Node1, Node2;

    Node1 = tree.root.left.left;

    Node2 = tree.root.right.right;

    if (tree.isCousin(tree.root, Node1, Node2))

    {

        Console.WriteLine("Yes");

    }

    else

    {

        Console.WriteLine("No");

    }

}
}

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


Выход:

 Yes

Сложность по времени вышеупомянутого решения — O (n), поскольку это делает самое большее три обхода двоичного дерева.

Проверьте, являются ли два узла двоюродными братьями в двоичном дереве | Set-2

Эта статья предоставлена Аюшем Шриваставой . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Проверьте, являются ли два узла двоюродными братьями в двоичном дереве

0.00 (0%) 0 votes