Рубрики

Печать общих узлов в двух бинарных поисковых деревьях

По двум бинарным деревьям поиска найдите в них общие узлы. Другими словами, найти пересечение двух BST.

Пример:

Метод 1 (простое решение) Простой способ — один за другим искать каждый узел первого дерева во втором дереве. Временная сложность этого решения составляет O (m * h), где m — количество узлов в первом дереве, а h — высота второго дерева.

Метод 2 (линейное время) Мы можем найти общие элементы в O (n) времени.
1) Выполните обход первого дерева и сохраните обход во вспомогательном массиве ar1 []. Смотрите sortedInorder () здесь .
2) Выполнить обход второго дерева и сохранить его во вспомогательном массиве ar2 []
3) Найти пересечение ar1 [] и ar2 []. Смотрите это для деталей.

Временная сложность этого метода составляет O (m + n), где m и n — количество узлов в первом и втором дереве соответственно. Это решение требует O (m + n) дополнительного пространства.

Метод 3 (Линейное время и ограниченное дополнительное пространство) Мы можем найти общие элементы в O (n) времени и O (h1 + h2) дополнительном пространстве, где h1 и h2 — высоты первого и второго BST соответственно.
Идея состоит в том, чтобы использовать итеративный обход по порядку . Мы используем два вспомогательных стека для двух BST. Поскольку нам нужно найти общие элементы, всякий раз, когда мы получаем один и тот же элемент, мы печатаем его.

C ++

// C ++ программа метода итеративного обхода
// найти общие элементы в двух BST.
#include<iostream>
#include<stack>

using namespace std;

  
// узел BST

struct Node

{

    int key;

    struct Node *left, *right;

};

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

Node *newNode(int ele)

{

    Node *temp = new Node;

    temp->key = ele;

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

    return temp;

}

  
// Функция двух печатных общих элементов в заданных двух деревьях

void printCommon(Node *root1, Node *root2)

{

    // Создаем два стека для двух обходов

    stack<Node *> stack1, s1, s2;

  

    while (1)

    {

        // вставляем узлы первого дерева в стек s1

        if (root1)

        {

            s1.push(root1);

            root1 = root1->left;

        }

  

        // вставляем узлы второго дерева в стек s2

        else if (root2)

        {

            s2.push(root2);

            root2 = root2->left;

        }

  

        // Здесь root1 и root2 равны NULL

        else if (!s1.empty() && !s2.empty())

        {

            root1 = s1.top();

            root2 = s2.top();

  

            // Если текущие ключи в двух деревьях совпадают

            if (root1->key == root2->key)

            {

                cout << root1->key << " ";

                s1.pop();

                s2.pop();

  

                // перейти к наследнику преемника

                root1 = root1->right;

                root2 = root2->right;

            }

  

            else if (root1->key < root2->key)

            {

                // Если узел первого дерева меньше, чем у

                // второе дерево, то очевидно, что порядок

                // наследники текущего узла могут иметь одинаковое значение

                // как узел второго дерева. Таким образом, мы поп

                // из s2

                s1.pop();

                root1 = root1->right;

  

                // root2 установлен в NULL, потому что нам нужно

                // новые узлы дерева 1

                root2 = NULL;

            }

            else if (root1->key > root2->key)

            {

                s2.pop();

                root2 = root2->right;

                root1 = NULL;

            }

        }

  

        // Оба корня и оба стека пусты

        else  break;

    }

}

  
// Полезная функция для обхода inorder

void inorder(struct Node *root)

{

    if (root)

    {

        inorder(root->left);

        cout<<root->key<<" ";

        inorder(root->right);

    }

}

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

struct Node* insert(struct Node* node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == NULL) return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Драйвер программы

int main()

{

    // Создать первое дерево, как показано в примере

    Node *root1 = NULL;

    root1 = insert(root1, 5);

    root1 = insert(root1, 1);

    root1 = insert(root1, 10);

    root1 = insert(root1,  0);

    root1 = insert(root1,  4);

    root1 = insert(root1,  7);

    root1 = insert(root1,  9);

  

    // Создать второе дерево, как показано в примере

    Node *root2 = NULL;

    root2 = insert(root2, 10);

    root2 = insert(root2, 7);

    root2 = insert(root2, 20);

    root2 = insert(root2, 4);

    root2 = insert(root2, 9);

  

    cout << "Tree 1 : ";

    inorder(root1);

    cout << endl;

  

    cout << "Tree 2 : ";

    inorder(root2);

  

    cout << "\nCommon Nodes: ";

    printCommon(root1, root2);

  

    return 0;

}

Джава

// Java-программа метода итеративного обхода
// найти общие элементы в двух BST.

import java.util.*;

class GfG { 

  
// узел BST

static class Node 

    int key; 

    Node left, right; 

}

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

static Node newNode(int ele) 

    Node temp = new Node(); 

    temp.key = ele; 

    temp.left = null;

    temp.right = null

    return temp; 

  
// Функция двух печатных общих элементов в заданных двух деревьях

static void printCommon(Node root1, Node root2) 

    Stack<Node> stack1 = new Stack<Node> ();

    Stack<Node> s1 = new Stack<Node> (); 

    Stack<Node> s2 = new Stack<Node> ();

  

    while (true

    

        // вставляем узлы первого дерева в стек s1

        if (root1 != null

        

            s1.push(root1); 

            root1 = root1.left; 

        

  

        // вставляем узлы второго дерева в стек s2

        else if (root2 != null

        

            s2.push(root2); 

            root2 = root2.left; 

        

  

        // Здесь root1 и root2 равны NULL

        else if (!s1.isEmpty() && !s2.isEmpty()) 

        

            root1 = s1.peek(); 

            root2 = s2.peek(); 

  

            // Если текущие ключи в двух деревьях совпадают

            if (root1.key == root2.key) 

            

                System.out.print(root1.key + " "); 

                s1.pop(); 

                s2.pop(); 

  

                // перейти к наследнику преемника

                root1 = root1.right; 

                root2 = root2.right; 

            

  

            else if (root1.key < root2.key) 

            

                // Если узел первого дерева меньше, чем у

                // второе дерево, то очевидно, что порядок

                // наследники текущего узла могут иметь одинаковое значение

                // как узел второго дерева. Таким образом, мы поп

                // из s2

                s1.pop(); 

                root1 = root1.right; 

  

                // root2 установлен в NULL, потому что нам нужно

                // новые узлы дерева 1

                root2 = null

            

            else if (root1.key > root2.key) 

            

                s2.pop(); 

                root2 = root2.right; 

                root1 = null

            

        

  

        // Оба корня и оба стека пусты

        else break

    

  
// Полезная функция для обхода inorder

static void inorder(Node root) 

    if (root != null

    

        inorder(root.left); 

        System.out.print(root.key + " "); 

        inorder(root.right); 

    

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

static Node insert(Node node, int key) 

    / * Если дерево пустое, вернуть новый узел * /

    if (node == null) return newNode(key); 

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node.key) 

        node.left = insert(node.left, key); 

    else if (key > node.key) 

        node.right = insert(node.right, key); 

  

    / * вернуть (неизмененный) указатель узла * /

    return node; 

  
// Драйвер программы

public static void main(String[] args) 

    // Создать первое дерево, как показано в примере

    Node root1 = null

    root1 = insert(root1, 5); 

    root1 = insert(root1, 1); 

    root1 = insert(root1, 10); 

    root1 = insert(root1, 0); 

    root1 = insert(root1, 4); 

    root1 = insert(root1, 7); 

    root1 = insert(root1, 9); 

  

    // Создать второе дерево, как показано в примере

    Node root2 = null

    root2 = insert(root2, 10); 

    root2 = insert(root2, 7); 

    root2 = insert(root2, 20); 

    root2 = insert(root2, 4); 

    root2 = insert(root2, 9); 

  

    System.out.print("Tree 1 : " + "\n"); 

    inorder(root1); 

    System.out.println();

    System.out.print("Tree 2 : " + "\n"); 

    inorder(root2); 

    System.out.println();

    System.out.println("Common Nodes: ");

  

    printCommon(root1, root2); 

  
}

python3

# Python3 программа итеративного обхода
# метод поиска общих элементов в двух BST.

  
# Сервисная функция для создания нового узла

class newNode:

    def __init__(self, key):

        self.key = key

        self.left = self.right = None

  
# Функция двух печатных общих элементов
# в данных двух деревьев

def printCommon(root1, root2):

      

    # Создать два стека для двух заказов

    # обходы

    s1 = []

    s2 = []

  

    while 1:

          

        # добавить узлы первого

        # дерево в стеке s1

        if root1:

            s1.append(root1)

            root1 = root1.left

  

        # добавить узлы второго дерева

        # в стеке s2

        elif root2:

            s2.append(root2)

            root2 = root2.left

  

        # Здесь root1 и root2 равны NULL

        elif len(s1) != 0 and len(s2) != 0:

            root1 = s1[-1

            root2 = s2[-1

  

            # Если текущие ключи в двух деревьях совпадают

            if root1.key == root2.key:

                print(root1.key, end = " ")

                s1.pop(-1

                s2.pop(-1)

  

                # перейти к наследнику преемника

                root1 = root1.right 

                root2 = root2.right

  

            elif root1.key < root2.key:

                  

                # Если Узел первого дерева меньше, чем

                # что из второго дерева, то очевидно

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

                # Узел может иметь то же значение, что и у

                # Узел второго дерева. Таким образом, мы поп с s2

                s1.pop(-1)

                root1 = root1.right 

  

                # root2 имеет значение NULL, потому что нам нужно

                # новые узлы дерева 1

                root2 = None

            elif root1.key > root2.key:

                s2.pop(-1)

                root2 = root2.right 

                root1 = None

  

        # Оба корня и оба стека пусты

        else:

            break

  
# Полезная функция для обхода inorder

def inorder(root):

    if root:

        inorder(root.left) 

        print(root.key, end = " ")

        inorder(root.right)

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

def insert(node, key):

      

    # Если дерево пусто, вернуть новый узел

    if node == None:

        return newNode(key) 

  

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

    if key < node.key: 

        node.left = insert(node.left, key) 

    elif key > node.key: 

        node.right = insert(node.right, key)

          

    # вернуть (неизмененный) указатель узла

    return node

  
Код водителя

if __name__ == '__main__':

      

    # Создайте первое дерево, как показано в примере

    root1 = None

    root1 = insert(root1, 5

    root1 = insert(root1, 1

    root1 = insert(root1, 10

    root1 = insert(root1, 0

    root1 = insert(root1, 4

    root1 = insert(root1, 7

    root1 = insert(root1, 9

  

    # Создайте второе дерево, как показано в примере

    root2 = None

    root2 = insert(root2, 10

    root2 = insert(root2, 7

    root2 = insert(root2, 20

    root2 = insert(root2, 4

    root2 = insert(root2, 9)

  

    print("Tree 1 : "

    inorder(root1) 

    print()

      

    print("Tree 2 : ")

    inorder(root2)

    print()

  

    print("Common Nodes: "

    printCommon(root1, root2)

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

C #

using System;

using System.Collections.Generic;

  
// C # программа метода итеративного обхода
// найти общие элементы в двух BST.

public class GfG

{

  
// узел BST

public class Node

{

    public int key;

    public Node left, right;

}

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

public static Node newNode(int ele)

{

    Node temp = new Node();

    temp.key = ele;

    temp.left = null;

    temp.right = null;

    return temp;

}

  
// Функция двух печатных общих элементов в заданных двух деревьях

public static void printCommon(Node root1, Node root2)

{

    Stack<Node> stack1 = new Stack<Node> ();

    Stack<Node> s1 = new Stack<Node> ();

    Stack<Node> s2 = new Stack<Node> ();

  

    while (true)

    {

        // вставляем узлы первого дерева в стек s1

        if (root1 != null)

        {

            s1.Push(root1);

            root1 = root1.left;

        }

  

        // вставляем узлы второго дерева в стек s2

        else if (root2 != null)

        {

            s2.Push(root2);

            root2 = root2.left;

        }

  

        // Здесь root1 и root2 равны NULL

        else if (s1.Count > 0 && s2.Count > 0)

        {

            root1 = s1.Peek();

            root2 = s2.Peek();

  

            // Если текущие ключи в двух деревьях совпадают

            if (root1.key == root2.key)

            {

                Console.Write(root1.key + " ");

                s1.Pop();

                s2.Pop();

  

                // перейти к наследнику преемника

                root1 = root1.right;

                root2 = root2.right;

            }

  

            else if (root1.key < root2.key)

            {

                // Если узел первого дерева меньше, чем у

                // второе дерево, то очевидно, что порядок

                // наследники текущего узла могут иметь одинаковое значение

                // как узел второго дерева. Таким образом, мы поп

                // из s2

                s1.Pop();

                root1 = root1.right;

  

                // root2 установлен в NULL, потому что нам нужно

                // новые узлы дерева 1

                root2 = null;

            }

            else if (root1.key > root2.key)

            {

                s2.Pop();

                root2 = root2.right;

                root1 = null;

            }

        }

  

        // Оба корня и оба стека пусты

        else

        {

            break;

        }

    }

}

  
// Полезная функция для обхода inorder

public static void inorder(Node root)

{

    if (root != null)

    {

        inorder(root.left);

        Console.Write(root.key + " ");

        inorder(root.right);

    }

}

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

public static Node insert(Node node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == null)

    {

        return newNode(key);

    }

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node.key)

    {

        node.left = insert(node.left, key);

    }

    else if (key > node.key)

    {

        node.right = insert(node.right, key);

    }

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Драйвер программы

public static void Main(string[] args)

{

    // Создать первое дерево, как показано в примере

    Node root1 = null;

    root1 = insert(root1, 5);

    root1 = insert(root1, 1);

    root1 = insert(root1, 10);

    root1 = insert(root1, 0);

    root1 = insert(root1, 4);

    root1 = insert(root1, 7);

    root1 = insert(root1, 9);

  

    // Создать второе дерево, как показано в примере

    Node root2 = null;

    root2 = insert(root2, 10);

    root2 = insert(root2, 7);

    root2 = insert(root2, 20);

    root2 = insert(root2, 4);

    root2 = insert(root2, 9);

  

    Console.Write("Tree 1 : " + "\n"); 

    inorder(root1); 

    Console.WriteLine(); 

    Console.Write("Tree 2 : " + "\n"); 

    inorder(root2); 

    Console.WriteLine(); 

    Console.Write("Common Nodes: " + "\n"); 

  

    printCommon(root1, root2);

  
}
}

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


Выход:

4 7 9 10

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

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

Печать общих узлов в двух бинарных поисковых деревьях

0.00 (0%) 0 votes