کلون کردن درخت دودویی با اشاره گرهای تصادفی — راهنمای کاربردی

۹۸ بازدید
آخرین به‌روزرسانی: ۱۹ تیر ۱۴۰۲
زمان مطالعه: ۷ دقیقه
کلون کردن درخت دودویی با اشاره گرهای تصادفی — راهنمای کاربردی

در این مطلب، چگونگی «کلون کردن درخت دودویی با اشاره گرهای تصادفی» (Clone a Binary Tree with Random Pointers) بیان و پیاده‌سازی آن در زبان برنامه‌نویسی ++C انجام شده است. در اینجا، منظور از کلون کردن در واقع کپی کردن است.

کلون کردن درخت دودویی با اشاره گرهای تصادفی

یک «درخت دودویی» (Binary Tree) داده شده که در آن هر «گره» (Node)، دارای ساختار زیر است.

1struct node {  
2    int key; 
3    struct node *left,*right,*random;
4}

اشاره‌گر تصادفی به هر گره تصادفی از درخت دودویی اشاره دارد و حتی می‌تواند به Null نیز اشاره و درخت دودویی داده شده را کلون کند.

روش ۱: استفاده از درهم‌سازی

ایده نهفته در پس روش استفاده از «درهم‌سازی» (Hash) آن است که نگاشت گره‌های درخت داده شده را در «جدول هش» (Hashtable) ذخیره کند. در ادامه، گام‌های انجام این کار همراه با جزئیات بیان شده‌اند.

۱. به صورت بازگشتی، درخت دودویی داده شده را پیمایش و مقادیر کلید، اشاره گر چپ و اشاره گر راست را برای کلون کردن درخت کپی کن. در حین کپی، نگاشت را از گره درخت داده شده به گره درخت کلون شده در جدول هش ذخیره کن. در شبه کد زیر، «cloneNode» گره کنونی مشاهده شده از درخت کلون و «treeNode» گره کنونی مشاهده شده از درخت داده شده است.

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

۲. به صورت بازگشتی، هر دو درخت را پیمایش کن و نقاط تصادفی را با استفاده از ورودی‌های جدول هش تنظیم کن.

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

در ادامه، پیاده‌سازی ++C ایده بالا، ارائه شده است. پیاده‌سازی که در ادامه آمده از unordered_map از STL استفاده کرده است.

1// A hashmap based C++ program to clone a binary  
2// tree with random pointers 
3#include<iostream> 
4#include<unordered_map> 
5using namespace std; 
6  
7/* A binary tree node has data, pointer to left child, 
8    a pointer to right child and a pointer to  
9    random node*/
10struct Node 
11{ 
12    int key; 
13    struct Node* left, *right, *random; 
14}; 
15  
16/* Helper function that allocates a new Node with the 
17   given data and NULL left, right and random pointers. */
18Node* newNode(int key) 
19{ 
20    Node* temp = new Node; 
21    temp->key = key; 
22    temp->random = temp->right = temp->left = NULL; 
23    return (temp); 
24} 
25  
26/* Given a binary tree, print its Nodes in inorder*/
27void printInorder(Node* node) 
28{ 
29    if (node == NULL) 
30        return; 
31  
32    /* First recur on left sutree */
33    printInorder(node->left); 
34  
35    /* then print data of Node and its random */
36    cout << "[" << node->key << " "; 
37    if (node->random == NULL) 
38        cout << "NULL], "; 
39    else
40        cout << node->random->key << "], "; 
41  
42    /* now recur on right subtree */
43    printInorder(node->right); 
44} 
45  
46// This function creates clone by copying key and left and right pointers 
47// This function also stores mapping from given tree node to clone. 
48Node* copyLeftRightNode(Node* treeNode, unordered_map<Node *, Node *> &mymap) 
49{ 
50    if (treeNode == NULL) 
51        return NULL; 
52    Node* cloneNode = newNode(treeNode->key); 
53    mymap[treeNode] = cloneNode; 
54    cloneNode->left  = copyLeftRightNode(treeNode->left, mymap); 
55    cloneNode->right = copyLeftRightNode(treeNode->right, mymap); 
56    return cloneNode; 
57} 
58  
59// This function copies random node by using the hashmap built by 
60// copyLeftRightNode() 
61void copyRandom(Node* treeNode,  Node* cloneNode, unordered_map<Node *, Node *> &mymap) 
62{ 
63    if (cloneNode == NULL) 
64        return; 
65    cloneNode->random =  mymap[treeNode->random]; 
66    copyRandom(treeNode->left, cloneNode->left, mymap); 
67    copyRandom(treeNode->right, cloneNode->right, mymap); 
68} 
69  
70// This function makes the clone of given tree. It mainly uses 
71// copyLeftRightNode() and copyRandom() 
72Node* cloneTree(Node* tree) 
73{ 
74    if (tree == NULL) 
75        return NULL; 
76    unordered_map<Node *, Node *> mymap; 
77    Node* newTree = copyLeftRightNode(tree, mymap); 
78    copyRandom(tree, newTree, mymap); 
79    return newTree; 
80} 
81  
82/* Driver program to test above functions*/
83int main() 
84{ 
85    //Test No 1 
86    Node *tree = newNode(1); 
87    tree->left = newNode(2); 
88    tree->right = newNode(3); 
89    tree->left->left = newNode(4); 
90    tree->left->right = newNode(5); 
91    tree->random = tree->left->right; 
92    tree->left->left->random = tree; 
93    tree->left->right->random = tree->right; 
94  
95    //  Test No 2 
96    //    tree = NULL; 
97  
98    //  Test No 3 
99    //    tree = newNode(1); 
100  
101    //  Test No 4 
102    /*    tree = newNode(1); 
103        tree->left = newNode(2); 
104        tree->right = newNode(3); 
105        tree->random = tree->right; 
106        tree->left->random = tree; 
107    */
108  
109    cout << "Inorder traversal of original binary tree is: \n"; 
110    printInorder(tree); 
111  
112    Node *clone = cloneTree(tree); 
113  
114    cout << "\n\nInorder traversal of cloned binary tree is: \n"; 
115    printInorder(clone); 
116  
117    return 0; 
118}

خروجی قطعه کد بالا، به صورت زیر است.

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],

روش ۲: ویرایش موقت درخت دودویی داده شده

الگوریتم این روش، در ادامه آمده است.

۱. گره‌های جدید را در درخت کلون شده بساز و هر گره جدید را در درخت اصلی، بین لبه اشاره‌گر چپ از گره متناظر درج کن. (مشاهده تصویر زیر، برای درک بهتر این موضوع، توصیه می‌شود.)

اگر کره کنونی A و فرزند سمت چپ آن B است (A — >> B)، گره جدید کلون شده با کلید A ساخته می‌شود (cA) و به عنوان A — >> cA — >> B قرار داده می‌شود (B می‌تواند نال یا فرزند غیر نال سمت چپ باشد). اشاره‌گر فرزند سمت راست به درستی تنظیم می‌شود. اگر برای فرزند کنونی A، فرزند راست در درخت اصلی C است (A — >> C)، سپس، گره‌های کلون شده متناظر cA و cC مشابه cA —- >> cC هستند.

کلون کردن درخت دودویی با اشاره گرهای تصادفی -- راهنمای کاربردی

۲. تنظیم اشاره‌گر تصادفی در درخت کلون شده به ازای درخت اصلی.

اگر اشاره‌گر تصادفی A به گره B اشاره کند، در درخت کلون شده، cA به cB اشاره می‌کند (cA و cB گره‌های جدید در درخت کلون شده و متناظر با گره‌های A و B در درخت اصلی هستند).

۳. اشاره‌گرهای سمت چپ را به درستی در درخت اصلی و درخت کلون شده، بازیابی کن.

در ادامه، پیاده‌سازی الگوریتم بالا در  زبان برنامه‌نویسی ++C ارائه شده است.

1#include <iostream> 
2using namespace std; 
3  
4/* A binary tree node has data, pointer to left child, a pointer to right 
5   child and a pointer to random node*/
6struct Node 
7{ 
8    int key; 
9    struct Node* left, *right, *random; 
10}; 
11  
12/* Helper function that allocates a new Node with the 
13   given data and NULL left, right and random pointers. */
14Node* newNode(int key) 
15{ 
16    Node* temp = new Node; 
17    temp->key = key; 
18    temp->random = temp->right = temp->left = NULL; 
19    return (temp); 
20} 
21  
22/* Given a binary tree, print its Nodes in inorder*/
23void printInorder(Node* node) 
24{ 
25    if (node == NULL) 
26        return; 
27  
28    /* First recur on left sutree */
29    printInorder(node->left); 
30  
31    /* then print data of Node and its random */
32    cout << "[" << node->key << " "; 
33    if (node->random == NULL) 
34        cout << "NULL], "; 
35    else
36        cout << node->random->key << "], "; 
37  
38    /* now recur on right subtree */
39    printInorder(node->right); 
40} 
41  
42// This function creates new nodes cloned tree and puts new cloned node 
43// in between current node and it's left child 
44// i.e. if current node is A and it's left child is B ( A --- >> B ), 
45//      then new cloned node with key A wil be created (say cA) and 
46//      it will be put as 
47//      A --- >> cA --- >> B 
48// Here B can be a NULL or a non-NULL left child 
49// Right child pointer will be set correctly 
50// i.e. if for current node A, right child is C in original tree 
51// (A --- >> C) then corresponding cloned nodes cA and cC will like 
52// cA ---- >> cC 
53Node* copyLeftRightNode(Node* treeNode) 
54{ 
55    if (treeNode == NULL) 
56        return NULL; 
57  
58    Node* left = treeNode->left; 
59    treeNode->left = newNode(treeNode->key); 
60    treeNode->left->left = left; 
61    if(left != NULL) 
62        left->left = copyLeftRightNode(left); 
63  
64    treeNode->left->right = copyLeftRightNode(treeNode->right); 
65    return treeNode->left; 
66} 
67  
68// This function sets random pointer in cloned tree as per original tree 
69// i.e. if node A's random pointer points to node B, then 
70// in cloned tree, cA wil point to cB (cA and cB are new node in cloned 
71// tree corresponding to node A and B in original tree) 
72void copyRandomNode(Node* treeNode, Node* cloneNode) 
73{ 
74    if (treeNode == NULL) 
75        return; 
76    if(treeNode->random != NULL) 
77        cloneNode->random = treeNode->random->left; 
78    else
79        cloneNode->random = NULL; 
80  
81    if(treeNode->left != NULL && cloneNode->left != NULL) 
82        copyRandomNode(treeNode->left->left, cloneNode->left->left); 
83    copyRandomNode(treeNode->right, cloneNode->right); 
84} 
85  
86// This function will restore left pointers correctly in 
87// both original and cloned tree 
88void restoreTreeLeftNode(Node* treeNode, Node* cloneNode) 
89{ 
90    if (treeNode == NULL) 
91        return; 
92    if (cloneNode->left != NULL) 
93    { 
94        Node* cloneLeft = cloneNode->left->left; 
95        treeNode->left = treeNode->left->left; 
96        cloneNode->left = cloneLeft; 
97    } 
98    else
99        treeNode->left = NULL; 
100  
101    restoreTreeLeftNode(treeNode->left, cloneNode->left); 
102    restoreTreeLeftNode(treeNode->right, cloneNode->right); 
103} 
104  
105//This function makes the clone of given tree 
106Node* cloneTree(Node* treeNode) 
107{ 
108    if (treeNode == NULL) 
109        return NULL; 
110    Node* cloneNode = copyLeftRightNode(treeNode); 
111    copyRandomNode(treeNode, cloneNode); 
112    restoreTreeLeftNode(treeNode, cloneNode); 
113    return cloneNode; 
114} 
115  
116  
117/* Driver program to test above functions*/
118int main() 
119{ 
120/*  //Test No 1 
121    Node *tree = newNode(1); 
122    tree->left = newNode(2); 
123    tree->right = newNode(3); 
124    tree->left->left = newNode(4); 
125    tree->left->right = newNode(5); 
126    tree->random = tree->left->right; 
127    tree->left->left->random = tree; 
128    tree->left->right->random = tree->right; 
129  
130//  Test No 2 
131//    Node *tree = NULL; 
132/* 
133//  Test No 3 
134    Node *tree = newNode(1); 
135  
136//  Test No 4 
137    Node *tree = newNode(1); 
138    tree->left = newNode(2); 
139    tree->right = newNode(3); 
140    tree->random = tree->right; 
141    tree->left->random = tree; 
142  
143  Test No 5 
144    Node *tree = newNode(1); 
145    tree->left = newNode(2); 
146    tree->right = newNode(3); 
147    tree->left->left = newNode(4); 
148    tree->left->right = newNode(5); 
149    tree->right->left = newNode(6); 
150    tree->right->right = newNode(7); 
151    tree->random = tree->left; 
152*/
153//    Test No 6 
154    Node *tree = newNode(10); 
155    Node *n2 = newNode(6); 
156    Node *n3 = newNode(12); 
157    Node *n4 = newNode(5); 
158    Node *n5 = newNode(8); 
159    Node *n6 = newNode(11); 
160    Node *n7 = newNode(13); 
161    Node *n8 = newNode(7); 
162    Node *n9 = newNode(9); 
163    tree->left = n2; 
164    tree->right = n3; 
165    tree->random = n2; 
166    n2->left = n4; 
167    n2->right = n5; 
168    n2->random = n8; 
169    n3->left = n6; 
170    n3->right = n7; 
171    n3->random = n5; 
172    n4->random = n9; 
173    n5->left = n8; 
174    n5->right = n9; 
175    n5->random = tree; 
176    n6->random = n9; 
177    n9->random = n8; 
178  
179/*    Test No 7 
180    Node *tree = newNode(1); 
181    tree->left = newNode(2); 
182    tree->right = newNode(3); 
183    tree->left->random = tree; 
184    tree->right->random = tree->left; 
185*/
186    cout << "Inorder traversal of original binary tree is: \n"; 
187    printInorder(tree); 
188  
189    Node *clone = cloneTree(tree); 
190  
191    cout << "\n\nInorder traversal of cloned binary tree is: \n"; 
192    printInorder(clone); 
193  
194    return 0; 
195}

خروجی قطعه کد بالا، به صورت زیر است.

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],

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *