You are here:

# C++/copy and delete trees

Advertisement

Question
QUESTION:  Hi Bill,

I was wondering if I could ask you a question. You have helped me before and I'm very thankful for that.
I have constructed a tree (dynamically allocated FP-tree, to be exact). I now need to extract sub-trees from the big tree. I don't know how to approach this problem. I guess I can either copy the entire tree and then delete unwanted branches, or copy selected brances node by node. My tree only has leaf->root pointers which means I cannot walk it it both directions so I probably want to step through the nodes I want and copy them. My questions are:
1) how do you copy selected nodes from a tree so that the name of the tree changes but all properties (linkages) of the sub-tree remain the same,
2) how do you then get rid of the new tree when it's no longer needed.
Thank you so much!
Andres

ANSWER: Hi Andres,

First, part of the answer to this depends on what is in each node (besides e.g. left and right pointers).  If they are simple nodes, you can allocate new ones and use assignment to copy them:

newOne = new Node;
newOne = originalNode;

If they are complex nodes with allocated members, you may have to define a copy operator which will know how to make a full copy of the node.  If you use a member (e.g. CString in MFC) that has a copy operator, then the assignment will use it.

Your tree copy doesn't matter that it's a sub-tree.  The whole tree is a sub-tree except there is no node which references it.  This copy is a good time for recursion, because copying a tree can be reduced to copying the tree of each leaf, down to each leaf.  Something like:

class Node
{
Node *left;
Node *right;
}

Node *CopyTree( Node *node )
{
Node *newNode;

if( node == NULL )
return NULL;
newNode = new Node;
newNode = node;  // copies, but don't use left and right
// Recurse on left and right trees
newNode->left = CopyTree( node->left );
newNode->right = CopyTree( node->right );
return newNode;
}

I didn't test this code, but it's the general idea.  Notice how it gets to the bottom of each tree and ripples up with new nodes, which get added to previous nodes left and right sides.

I hope this helps you.

Bill

---------- FOLLOW-UP ----------

QUESTION:  Hi Bill,

Thanks so much. It seems that I should be able to copy the nodes of my tree in a simple fashion because the nodes only contain 2 pointers and two integers. But when I do a simple copy I have to reset all the pointers because otherwise they will point to their original parent tree. Is that correct? In order to delete an entire tree (dynamically allocated) do I have to walk through the enire tree and delete each node indicidually using "delete", or is there a way to delete the entire tree immediately with one command?
Thanks again!!

Answer
Hi Andres,

The code I showed you does reset (or initialize) the pointers.  It happens when each subtree is allocated and stored in left and right.  So yes, you can't leave nodes pointing to old trees.  You have to traverse the tree and delete the nodes:

void DeleteTree( Node *node )
{
// Recurse on left and right trees
if(node->left != NULL)
DeleteTree( node->left );
if(node->right != NULL)
DeleteTree( node->right );
delete node;
}

Bill

C++

All Answers

Answers by Expert:

Ask Experts

Volunteer

#### Bill A

##### Expertise

I can answer questions about C++, programming algorithms, Windows programming in MFC (which is C++). I cannot answer questions about STL (templates) and I have no experience with Linux. I do enjoy reviewing code and critiquing it or finding problems in it. I will also gladly show better algorithms or methods if you want to take advantage of that.

##### Experience

I've developed a commercial embedded C compiler/assembler and IDE with debugger toolset, of which the IDE and debugger are written in C++. I work in the industry writing high tech embedded programs and Windows programs to communicate with the embedded devices.

Publications
Book: Embedded Systems Design using the Rabbit 3000 Microprocessor Authored Chapter 10 in its entirety.

Education/Credentials
BS Computer Engineering

©2016 About.com. All rights reserved.

Browse Answers: