本文共 9268 字,大约阅读时间需要 30 分钟。
原文地址:
已知一个二叉树,树每个节点是以下结构:
struct node { int key; struct node *left,*right,*random;}
随机指针指向二叉树的一个随机节点,甚至可以指向NULL,克隆这个已知的二叉树。
方法1(用哈希法)
这个思想是把已知的树的节点保存隐射到克隆树的哈希表中。下面是详细步骤:
1)递归遍历这个二叉树,并复制key的值,左指针和右指针来复制树。在复制过程中,保存已知树节点到克隆树在哈希表中的映射。在下面的伪代码中,‘cloneNode’就是克隆树当前访问的节点,‘treeNode’是已知的树的当前访问节点。
cloneNode->key = treeNode->key cloneNode->left = treeNode->left cloneNode->right = treeNode->right map[treeNode] = cloneNode
2)递归地遍历两个树,用哈希表中的实体设置随机指针。
cloneNode->random = map[treeNode->random]
下面是上述思想的C++实现。下面的实现用了C++ STL中的map。注意map没有实现哈希表,实际上它是基于二叉平衡树的。
// A hashmap based C++ program to clone a binary tree with random pointers#include#include
输出:
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(临时修改已知树)
例如:如果当前节点是A,它的左孩子是B ( A — >> B ),那么key为A的新克隆节点将被创建(假设是cA),那么它将这样插入 A — >> cA — >> B(B可以是NULL,或者是一个非NULL的左孩子)。右边的孩子将被正确地设置。例如,如果当前节点是A,原树的右孩子是C(A — >> C),那么相关的克隆节点cA和cC将是这样的: cA —- >> cC。
在克隆树中设置随机指针作为原树的对等树。
例如:如果节点A的随机指针指向B,那么在克隆树中,cA将指向cB(cA和cB是原树中A与B节点相对应在克隆树中的节点)。正确地恢复原树和克隆树中的左指针。
下面是以上算法的C++实现。
#includeusing 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 sutree */ 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 wil 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 ---- >> cCNode* 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 wil 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 treevoid 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 treeNode* 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: \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],