Рубрики

Клонировать двоичное дерево со случайными указателями

Дано Бинарное Дерево, где каждый узел имеет следующую структуру.

struct node {  
    int key; 
    struct node *left,*right,*random;
} 

Случайный указатель указывает на любой случайный узел двоичного дерева и может даже указывать на NULL, клонировать данное двоичное дерево.

Способ 1 (использовать хеширование)
Идея состоит в том, чтобы сохранить отображение из заданных узлов дерева в узлы клонированного дерева в хеш-таблице. Ниже приведены подробные шаги.

1) Рекурсивно пройти заданное двоичное и скопировать значение ключа, левый указатель и правый указатель в дерево клонов. При копировании сохраняйте отображение из данного узла дерева в узел дерева клонов в хеш-таблице. В следующем псевдокоде cloneNode в настоящее время посещается узлом дерева клонов, а treeNode — посещаемым узлом данного дерева.

   cloneNode->key  = treeNode->key
   cloneNode->left = treeNode->left
   cloneNode->right = treeNode->right
   map[treeNode] = cloneNode 

2) Рекурсивно обойти оба дерева и установить случайные указатели, используя записи из хеш-таблицы.

   cloneNode->random = map[treeNode->random] 

Ниже приводится реализация вышеуказанной идеи на C ++. Следующая реализация использует unordered_map из C ++ ST L. Обратите внимание, что map не реализует хеш-таблицу, она фактически основана на самобалансирующемся бинарном дереве поиска.

// основанная на хэш-карте программа C ++ для клонирования двоичного файла
// дерево со случайными указателями
#include<iostream>
#include<unordered_map>

using namespace std;

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

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

    случайный узел * /

struct Node

{

    int key;

    struct Node* left, *right, *random;

};

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

   заданные данные и NULL левый, правый и случайный указатели. * /

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

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

    return (temp);

}

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

void printInorder(Node* node)

{

    if (node == NULL)

        return;

  

    / * Первый рецидив на левом поддоне * /

    printInorder(node->left);

  

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

    cout << "[" << node->key << " ";

    if (node->random == NULL)

        cout << "NULL], ";

    else

        cout << node->random->key << "], ";

  

    / * теперь возвращаемся на правильное поддерево * /

    printInorder(node->right);

}

  
// Эта функция создает клон путем копирования ключа и левого и правого указателей
// Эта функция также сохраняет отображение от данного узла дерева к клону.
Node* copyLeftRightNode(Node* treeNode, unordered_map<Node *, Node *> &mymap)
{

    if (treeNode == NULL)

        return NULL;

    Node* cloneNode = newNode(treeNode->key);

    mymap[treeNode] = cloneNode;

    cloneNode->left  = copyLeftRightNode(treeNode->left, mymap);

    cloneNode->right = copyLeftRightNode(treeNode->right, mymap);

    return cloneNode;

}

  
// Эта функция копирует случайный узел, используя hashmap, созданный
// copyLeftRightNode ()

void copyRandom(Node* treeNode,  Node* cloneNode, unordered_map<Node *, Node *> &mymap)

{

    if (cloneNode == NULL)

        return;

    cloneNode->random =  mymap[treeNode->random];

    copyRandom(treeNode->left, cloneNode->left, mymap);

    copyRandom(treeNode->right, cloneNode->right, mymap);

}

  
// Эта функция делает клон данного дерева. В основном использует
// copyLeftRightNode () и copyRandom ()
Node* cloneTree(Node* tree)
{

    if (tree == NULL)

        return NULL;

    unordered_map<Node *, Node *> mymap;

    Node* newTree = copyLeftRightNode(tree, mymap);

    copyRandom(tree, newTree, mymap);

    return newTree;

}

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

int main()

{

    // Тест № 1

    Node *tree = newNode(1);

    tree->left = newNode(2);

    tree->right = newNode(3);

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

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

    tree->random = tree->left->right;

    tree->left->left->random = tree;

    tree->left->right->random = tree->right;

  

    // Тест № 2

    // tree = NULL;

  

    // Тест № 3

    // tree = newNode (1);

  

    // Тест № 4

    / * tree = newNode (1);

        tree-> left = newNode (2);

        tree-> right = newNode (3);

        tree-> random = tree-> right;

        дерево-> левый-> случайный = дерево;

    * /

  

    cout << "Inorder traversal of original binary tree is: \n";

    printInorder(tree);

  

    Node *clone = cloneTree(tree);

  

    cout << "\n\nInorder traversal of cloned binary tree is: \n";

    printInorder(clone);

  

    return 0;

}

Выход:

Inorder traversal of original binary tree is:
[4 1], [2 NULL], [5 3], [1 5], [3 NULL],

Inorder traversal of cloned binary tree is:
[4 1], [2 NULL], [5 3], [1 5], [3 NULL],

Метод 2 (временно изменить данное двоичное дерево)

1. Создайте новые узлы в клонированном дереве и вставьте каждый новый узел в исходное дерево между левым краем указателя соответствующего узла в исходном дереве (см. Изображение ниже).
то есть, если текущий узел — A, а его левый потомок — B (A — >> B), то будет создан новый клонированный узел с ключом A (скажем, cA), и он будет обозначен как A — >> cA — >> B ( B может быть нулевым или ненулевым левым потомком). Указатель правого потомка будет установлен правильно, т.е. если для текущего узла A правый потомок равен C в исходном дереве (A — >> C), то соответствующие клонированные узлы cA и cC будут похожи на cA —- >> cC

2. Установить случайный указатель в клонированном дереве согласно исходному дереву
т.е. если случайный указатель узла A указывает на узел B, то в клонированном дереве cA будет указывать на cB (cA и cB — новый узел в клонированном дереве, соответствующий узлам A и B в исходном дереве)

3. Правильно восстановите левые указатели как в исходном, так и в клонированном дереве.

Следующее — реализация C ++ вышеупомянутого алгоритма.

#include <iostream>

using namespace std;

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

   дочерний и указатель на случайный узел * /

struct Node

{

    int key;

    struct Node* left, *right, *random;

};

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

   заданные данные и NULL левый, правый и случайный указатели. * /

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

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

    return (temp);

}

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

void printInorder(Node* node)

{

    if (node == NULL)

        return;

  

    / * Первый рецидив на левом поддоне * /

    printInorder(node->left);

  

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

    cout << "[" << node->key << " ";

    if (node->random == NULL)

        cout << "NULL], ";

    else

        cout << node->random->key << "], ";

  

    / * теперь возвращаемся на правильное поддерево * /

    printInorder(node->right);

}

  
// Эта функция создает новые узлы клонированного дерева и помещает новый клонированный узел
// между текущим узлом и его левым потомком
// т.е. если текущий узел A, а его левый потомок B (A --- >> B),
// тогда будет создан новый клонированный узел с ключом A (скажем, cA) и
// будет выставлено как
// A --- >> cA --- >> B
// Здесь B может быть нулевым или ненулевым левым потомком
// Правильный дочерний указатель будет установлен правильно
// т.е. если для текущего узла A правый потомок - C в исходном дереве
// (A --- >> C) тогда соответствующие клонированные узлы cA и cC будут похожи
// cA ---- >> cC
Node* copyLeftRightNode(Node* treeNode)
{

    if (treeNode == NULL)

        return NULL;

  

    Node* left = treeNode->left;

    treeNode->left = newNode(treeNode->key);

    treeNode->left->left = left;

    if(left != NULL)

        left->left = copyLeftRightNode(left);

  

    treeNode->left->right = copyLeftRightNode(treeNode->right);

    return treeNode->left;

}

  
// Эта функция устанавливает случайный указатель в клонированном дереве согласно исходному дереву
// т.е. если случайный указатель узла A указывает на узел B, то
// в клонированном дереве cA будет указывать на cB (cA и cB - новый узел в клонированном
// дерево, соответствующее узлам A и B в исходном дереве)

void copyRandomNode(Node* treeNode, Node* cloneNode)

{

    if (treeNode == NULL)

        return;

    if(treeNode->random != NULL)

        cloneNode->random = treeNode->random->left;

    else

        cloneNode->random = NULL;

  

    if(treeNode->left != NULL && cloneNode->left != NULL)

        copyRandomNode(treeNode->left->left, cloneNode->left->left);

    copyRandomNode(treeNode->right, cloneNode->right);

}

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

void restoreTreeLeftNode(Node* treeNode, Node* cloneNode)

{

    if (treeNode == NULL)

        return;

    if (cloneNode->left != NULL)

    {

        Node* cloneLeft = cloneNode->left->left;

        treeNode->left = treeNode->left->left;

        cloneNode->left = cloneLeft;

    }

    else

        treeNode->left = NULL;

  

    restoreTreeLeftNode(treeNode->left, cloneNode->left);

    restoreTreeLeftNode(treeNode->right, cloneNode->right);

}

  
// Эта функция делает клон данного дерева
Node* cloneTree(Node* treeNode)
{

    if (treeNode == NULL)

        return NULL;

    Node* cloneNode = copyLeftRightNode(treeNode);

    copyRandomNode(treeNode, cloneNode);

    restoreTreeLeftNode(treeNode, cloneNode);

    return cloneNode;

}

  

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

int main()

{
/ * // Тест № 1

    Узел * tree = newNode (1);

    tree-> left = newNode (2);

    tree-> right = newNode (3);

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

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

    tree-> random = tree-> left-> right;

    tree-> left-> left-> random = tree;

    дерево-> левый-> правый-> случайный = дерево-> правый;

  
// Тест № 2
// Node * tree = NULL;
/ *
// Тест № 3

    Узел * tree = newNode (1);

  
// Тест № 4

    Узел * tree = newNode (1);

    tree-> left = newNode (2);

    tree-> right = newNode (3);

    tree-> random = tree-> right;

    дерево-> левый-> случайный = дерево;

  

  Тест № 5

    Узел * tree = newNode (1);

    tree-> left = newNode (2);

    tree-> right = newNode (3);

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

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

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

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

    tree-> random = tree-> left;

* /
// Тест № 6

    Node *tree = newNode(10);

    Node *n2 = newNode(6);

    Node *n3 = newNode(12);

    Node *n4 = newNode(5);

    Node *n5 = newNode(8);

    Node *n6 = newNode(11);

    Node *n7 = newNode(13);

    Node *n8 = newNode(7);

    Node *n9 = newNode(9);

    tree->left = n2;

    tree->right = n3;

    tree->random = n2;

    n2->left = n4;

    n2->right = n5;

    n2->random = n8;

    n3->left = n6;

    n3->right = n7;

    n3->random = n5;

    n4->random = n9;

    n5->left = n8;

    n5->right = n9;

    n5->random = tree;

    n6->random = n9;

    n9->random = n8;

  
/ * Тест № 7

    Узел * tree = newNode (1);

    tree-> left = newNode (2);

    tree-> right = newNode (3);

    дерево-> левый-> случайный = дерево;

    tree-> right-> random = tree-> left;

* /

    cout << "Inorder traversal of original binary tree is: \n";

    printInorder(tree);

  

    Node *clone = cloneTree(tree);

  

    cout << "\n\nInorder traversal of cloned binary tree is: \n";

    printInorder(clone);

  

    return 0;

}

Выход:

Inorder traversal of original binary tree is:
[5 9], [6 7], [7 NULL], [8 10], [9 7], [10 6], [11 9], [12 8], [13 NULL],

Inorder traversal of cloned binary tree is:
[5 9], [6 7], [7 NULL], [8 10], [9 7], [10 6], [11 9], [12 8], [13 NULL],

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

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

Клонировать двоичное дерево со случайными указателями

0.00 (0%) 0 votes