给定一个二叉树，其中每个节点都有以下结构。
null
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++实现和java实现。下面的实现使用了来自C++ STL的无序映射和java中的HASMAP。请注意，映射没有实现哈希表，它实际上是基于一个自平衡的二叉搜索树。
CPP
// A hashmap based C++ program to clone a binary // tree with random pointers #include<iostream> #include<unordered_map> using namespace std; /* A binary tree node has data, pointer to left child, a pointer to right child and a pointer to random node*/ struct Node { int key; struct Node* left, *right, *random; }; /* Helper function that allocates a new Node with the given data and NULL left, right and random pointers. */ Node* newNode( int key) { Node* temp = new Node; temp->key = key; temp->random = temp->right = temp->left = NULL; return (temp); } /* Given a binary tree, print its Nodes in inorder*/ void printInorder(Node* node) { if (node == NULL) return ; /* First recur on left subtree */ printInorder(node->left); /* then print data of Node and its random */ cout << "[" << node->key << " " ; if (node->random == NULL) cout << "NULL], " ; else cout << node->random->key << "], " ; /* now recur on right subtree */ printInorder(node->right); } // This function creates clone by copying key and left and right pointers // This function also stores mapping from given tree node to clone. 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; } // This function copies random node by using the hashmap built by // 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); } // This function makes the clone of given tree. It mainly uses // copyLeftRightNode() and 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; } /* Driver program to test above functions*/ int main() { //Test No 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; // Test No 2 // tree = NULL; // Test No 3 // tree = newNode(1); // Test No 4 /* tree = newNode(1); tree->left = newNode(2); tree->right = newNode(3); tree->random = tree->right; tree->left->random = tree; */ cout << "Inorder traversal of original binary tree is: " ; printInorder(tree); Node *clone = cloneTree(tree); cout << "Inorder traversal of cloned binary tree is: " ; printInorder(clone); return 0; } |
JAVA
import java.lang.*; import java.util.*; class Tree { int data; Tree left, right, random; Tree( int d) { data = d; left = null ; right = null ; random = null ; } } class CloneABT { public static void main(String[] args) { Tree tree = new Tree( 1 ); tree.left = new Tree( 2 ); tree.right = new Tree( 3 ); tree.left.left = new Tree( 4 ); tree.left.right = new Tree( 5 ); tree.random = tree.left.right; tree.left.left.random = tree; tree.left.right.random = tree.right; System.out.println( "Inorder traversal of original binary tree is: " ); printInorder(tree); Tree clone = cloneTree(tree); System.out.println( "Inorder traversal of cloned binary tree is: " ); printInorder(clone); } public static Tree cloneTree(Tree tree) { if (tree == null ) return null ; HashMap<Tree, Tree> map = new HashMap<>(); // create a hashmap to store // the randoms Tree newtree = clonelr(tree, map); copyrandom(tree, newtree, map); return newtree; } // cloning the left and right tree public static Tree clonelr(Tree tree, HashMap<Tree, Tree> map) { if (tree == null ) return null ; Tree clonenode = new Tree(tree.data); map.put(tree, clonenode); clonenode.left = clonelr(tree.left, map); clonenode.right = clonelr(tree.right, map); return clonenode; } // setting the random pointers in the cloned tree public static void copyrandom(Tree tree, Tree clone, HashMap<Tree, Tree> map) { if (clone == null ) return ; clone.random = map.get(tree.random); copyrandom(tree.left, clone.left, map); copyrandom(tree.right, clone.right, map); } static void printInorder(Tree node) { if (node == null ) return ; /* First recur on left subtree */ printInorder(node.left); /* then print data of Node and its random */ System.out.print( "[" + node.data + " " ); if (node.random == null ) System.out.print( "null], " ); else System.out.print(node.data + "]" ); /* now recur on right subtree */ printInorder(node.right); } public static boolean printInorder(Tree a, Tree b) { if ((a == null ) && (b == null )) return true ; if (a != null && b != null ) { boolean check = ((a.data == b.data) && printInorder(a.left, b.left) && printInorder(a.right, b.right)); if (a.random != null && b.random != null ) return ( check && (a.random.data == b.random.data)); if (a.random == b.random) return check; return false ; } return false ; } public static void clone(Tree root, Tree proot, int n1, int n2) { try { if (root == null && proot == null ) return ; if (n1 == root.data) { if (proot.data == n2) root.random = proot; else { clone(root, proot.left, n1, n2); clone(root, proot.right, n1, n2); } } else { clone(root.left, proot, n1, n2); clone(root.right, proot, n1, n2); } } catch (NullPointerException ex) { } } public static void insert(Tree root, int n1, int n2, char lr) { if (root == null ) return ; if (n1 == root.data) { switch (lr) { case 'L' : root.left = new Tree(n2); break ; case 'R' : root.right = new Tree(n2); break ; } } else { insert(root.left, n1, n2, lr); insert(root.right, n1, n2, lr); } } } |
输出
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. 在克隆树中创建新节点，并将原始树中的每个新节点插入原始树中相应节点的左指针边缘之间（请参见下图）。 i、 e.如果当前节点是A，其左子节点是B（A->>B），那么将创建一个带有密钥A的新克隆节点（比如cA），并将其作为A->>cA->>B（B可以是空的或非空的左子节点）。将正确设置右子指针，即，对于当前节点A，如果右子节点是原始树中的C（A->>C），则相应的克隆节点cA和cC将类似于cA–>cC
2. 根据原始树在克隆树中设置随机指针 i、 e.如果节点A的随机指针指向节点B，那么在克隆树中，cA将指向cB（cA和cB是克隆树中与原始树中的节点A和B相对应的新节点） 3. 在原始树和克隆树中正确还原左指针 下面是C++实现上述算法。
CPP
#include <iostream> using namespace std; /* A binary tree node has data, pointer to left child, a pointer to right child and a pointer to random node*/ struct Node { int key; struct Node* left, *right, *random; }; /* Helper function that allocates a new Node with the given data and NULL left, right and random pointers. */ Node* newNode( int key) { Node* temp = new Node; temp->key = key; temp->random = temp->right = temp->left = NULL; return (temp); } /* Given a binary tree, print its Nodes in inorder*/ void printInorder(Node* node) { if (node == NULL) return ; /* First recur on left subtree */ printInorder(node->left); /* then print data of Node and its random */ cout << "[" << node->key << " " ; if (node->random == NULL) cout << "NULL], " ; else cout << node->random->key << "], " ; /* now recur on right subtree */ printInorder(node->right); } // This function creates new nodes cloned tree and puts new cloned node // in between current node and it's left child // i.e. if current node is A and it's left child is B ( A --- >> B ), // then new cloned node with key A will be created (say cA) and // it will be put as // A --- >> cA --- >> B // Here B can be a NULL or a non-NULL left child // Right child pointer will be set correctly // i.e. if for current node A, right child is C in original tree // (A --- >> C) then corresponding cloned nodes cA and cC will like // 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; } // This function sets random pointer in cloned tree as per original tree // i.e. if node A's random pointer points to node B, then // in cloned tree, cA will point to cB (cA and cB are new node in cloned // tree corresponding to node A and B in original tree) 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); } // This function will restore left pointers correctly in // both original and cloned tree 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); } //This function makes the clone of given tree Node* cloneTree(Node* treeNode) { if (treeNode == NULL) return NULL; Node* cloneNode = copyLeftRightNode(treeNode); copyRandomNode(treeNode, cloneNode); restoreTreeLeftNode(treeNode, cloneNode); return cloneNode; } /* Driver program to test above functions*/ int main() { /* //Test No 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; // Test No 2 // Node *tree = NULL; /* // Test No 3 Node *tree = newNode(1); // Test No 4 Node *tree = newNode(1); tree->left = newNode(2); tree->right = newNode(3); tree->random = tree->right; tree->left->random = tree; Test No 5 Node *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; */ // Test No 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; /* Test No 7 Node *tree = newNode(1); tree->left = newNode(2); tree->right = newNode(3); tree->left->random = tree; tree->right->random = tree->left; */ cout << "Inorder traversal of original binary tree is: " ; printInorder(tree); Node *clone = cloneTree(tree); cout << "Inorder traversal of cloned binary tree is: " ; 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],
本文由 导演 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
