烤树题。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

烤树题。

烤树题。# Programming - 葵花宝典

k*r2007-10-13 07:10

1 楼

Write a method： Node* Copy(Node* root)
that takes a pointer to a Node structure as a parameter. The
Node structure contains two pointers to other Node structures. The function
should return a complete copy of the passed-in data structure.
请问是这样做吗？
typedef struct node{
int value;
struct node *child1;
struct node *child2;
}Node;
Node* Copy(Node* root){
Node *n = new Node;
Copywrapper(n, root);
return n;
}
void Copywrapper(Node* n, Node* root){
if(!root) return;
n->v

s*e2007-10-13 07:10

2 楼

there might be a circle in the tree structure which need to be considered.
so we might need to store the copied nodes use a hash or map
node * completecopy_help(node* root, std::map& copied){
if(!root)return null;
if(copied[root])return copied[root];
// not copied before
node * r=new node;
copied[root]=r;
r->left= completecopy_help(root->left,copied);
r->right=completecopy_help(root->right,copied);
return r;

}
node* copy(node* root){
std::map

k*r2007-10-13 07:10

3 楼

3x. 树还会loop啊？

【在 s***e 的大作中提到】

: there might be a circle in the tree structure which need to be considered.
: so we might need to store the copied nodes use a hash or map
: node * completecopy_help(node* root, std::map& copied){
: if(!root)return null;
: if(copied[root])return copied[root];
: // not copied before
: node * r=new node;
: copied[root]=r;
: r->left= completecopy_help(root->left,copied);
: r->right=completecopy_help(root->right,copied);

k*k2007-10-13 07:10

4 楼

I don't think so...

【在 k********r 的大作中提到】

: 3x. 树还会loop啊？

t*t2007-10-13 07:10

5 楼

如果是树,当然不会
但是问题在于,原题中有说这是树吗?

【在 k********r 的大作中提到】

: 3x. 树还会loop啊？

c*x2007-10-13 07:10

6 楼

The question is to test you to write a recursive funtion.

c*e2007-10-13 07:10

7 楼

Node *copy(Node *root)
{
if (root == NULL) return NULL;
Node *newnode = new Node;
newnode->value = root->value;
newnode->child1=copy(root->child1);
newnode->child2=copy(root->child2);
return newnode;
}

c*x2007-10-13 07:10

8 楼

very nice.

【在 c****e 的大作中提到】

: Node *copy(Node *root)
: {
: if (root == NULL) return NULL;
: Node *newnode = new Node;
: newnode->value = root->value;
: newnode->child1=copy(root->child1);
: newnode->child2=copy(root->child2);
: return newnode;
: }

d*d2007-10-13 07:10

9 楼

DFS,BFS都可以.

function

【在 k********r 的大作中提到】

: Write a method： Node* Copy(Node* root)
: that takes a pointer to a Node structure as a parameter. The
: Node structure contains two pointers to other Node structures. The function
: should return a complete copy of the passed-in data structure.
: 请问是这样做吗？
: typedef struct node{
: int value;
: struct node *child1;
: struct node *child2;
: }Node;

w*i2007-10-13 07:10

10 楼

原题中根本就没有提要copy的是什么data structure
原题:
Write a method that takes a pointer to a Node structure as a parameter. The
Node structure contains two pointers to other Node structures. The function
should return a complete copy of the passed-in data structure.
For example, the method signature could look like so:
Node* Copy(Node* root);
Note:
· Do not make any assumptions about the data structure – it could
be a tree, linked list, graph etc.
· Feel free to choose the language you are most comfortable wit