当前位置： 首页 > news >正文

北碚网站建设上海网络推广服务公司

news 2025/7/23 16:30:40
北碚网站建设,上海网络推广服务公司,政府网站开发周期,独立商城网站建设原文地址：Clone a Binary Tree with Random Pointers 已知一个二叉树，树每个节点是以下结构： struct node { int key; struct node *left,*right,*random; } 随机指针指向二叉树的一个随机节点，甚至可以指向NULL，…

原文地址：Clone a Binary Tree with Random Pointers

已知一个二叉树，树每个节点是以下结构：

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

随机指针指向二叉树的一个随机节点，甚至可以指向NULL，克隆这个已知的二叉树。

方法1（用哈希法）

这个思想是把已知的树的节点保存隐射到克隆树的哈希表中。下面是详细步骤：

1）递归遍历这个二叉树，并复制key的值，左指针和右指针来复制树。在复制过程中，保存已知树节点到克隆树在哈希表中的映射。在下面的伪代码中，‘cloneNode’就是克隆树当前访问的节点，‘treeNode’是已知的树的当前访问节点。

   cloneNode->key  = treeNode->keycloneNode->left = treeNode->leftcloneNode->right = treeNode->rightmap[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<iostream>
#include<map>
using namespace std;/* A binary tree node has data, pointer to left child, a pointer to rightchild and a pointer to random node*/
struct Node
{int key;struct Node* left, *right, *random;
};/* Helper function that allocates a new Node with thegiven 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], ";elsecout << 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, 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, 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;map<Node *, Node *> *mymap = new  map<Node *, Node *>;Node* newTree = copyLeftRightNode(tree, mymap);copyRandom(tree, newTree, mymap);return newTree;
}/* Driver program to test above functions*/
int main()
{//Test No 1Node *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: \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 )，那么key为A的新克隆节点将被创建（假设是cA），那么它将这样插入 A — >> cA — >> B（B可以是NULL，或者是一个非NULL的左孩子）。右边的孩子将被正确地设置。例如，如果当前节点是A，原树的右孩子是C(A — >> C)，那么相关的克隆节点cA和cC将是这样的： cA —- >> cC。


这里写图片描述

  1. 在克隆树中设置随机指针作为原树的对等树。
    例如：如果节点A的随机指针指向B，那么在克隆树中，cA将指向cB（cA和cB是原树中A与B节点相对应在克隆树中的节点）。

  2. 正确地恢复原树和克隆树中的左指针。

下面是以上算法的C++实现。

#include <iostream>
using namespace std;/* A binary tree node has data, pointer to left child, a pointer to rightchild and a pointer to random node*/
struct Node
{int key;struct Node* left, *right, *random;
};/* Helper function that allocates a new Node with thegiven 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], ";elsecout << 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 ---- >> 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 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;elsecloneNode->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;}elsetreeNode->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 1Node *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 3Node *tree = newNode(1);//  Test No 4Node *tree = newNode(1);tree->left = newNode(2);tree->right = newNode(3);tree->random = tree->right;tree->left->random = tree;Test No 5Node *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 6Node *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 7Node *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],
http://www.lbrq.cn/news/2430217.html

相关文章：

  • c2b网站开发外贸公司一般怎么找客户
  • 阳江企业网站排名优化大连seo顾问
  • 做b2b比较好的网站有哪些网站流量分析工具
  • 怎么做和京东一样网站域名注册查询官网
  • 可以做游戏的网站有哪些seo深度优化公司
  • 网站建设 工具百度seo搜索引擎优化方案
  • b2b有哪些电商平台网站营销策划方案范文
  • 返利网站建设怎么宣传自己的产品
  • 做电子商务网站实验总结如何推广一个品牌
  • 网站服务器内部错误是怎么回事山东济南seo整站优化公司
  • 国家高新技术企业查询系统广州谷歌优化
  • 做微信推送封面的网站百度网站收录入口
  • 广州网站制作公司联系方式市场调研报告怎么做
  • 网络推广具体方式有哪些平台优化是指什么
  • 昆明网站建设方案报价产品营销
  • 网站建设需要多少时间百度运营推广
  • 用手机做自己的网站郑州网站关键词优化公司
  • 本地计算机做网站服务器同城推广引流平台
  • 学校网站建设协议模板百度免费优化
  • 设计师可以做兼职的网站百度投诉中心入口
  • 给女朋友做网站的素材北仑seo排名优化技术
  • 营销网站的方法网络营销推广的要点
  • 那些卖外挂的怎么做的网站seo按照搜索引擎的什么对网站
  • 太原网站建设vhuashi如何推广公司
  • wordpress建站注册新用户如何做好市场推广
  • 投票链接制作福州seo外包公司
  • 重庆大渡口网站建设免费注册网页网址
  • 做网站的如何找业务网络营销员岗位的职责与要求
  • 建立主题网站的顺序制作网站的app
  • 广告设计是做什么旺道seo推广系统怎么收费
  • 使用qemu命令启动虚拟机
  • 使用 Ansys Fluent 软件参数化工作流程对搅拌罐中的稳态涡流进行仿真
  • 数据结构 之 【排序】(直接插入排序、希尔排序)
  • Unity 插件Resize Pro 最快的 Texture2D 调整大小工具
  • Linux的磁盘存储管理实操——（中）——逻辑卷管理实战
  • Lua：小巧而强大的脚本语言，游戏与嵌入式的秘密武器