Copy of the tree in C++

A simple and at the same time interesting task appeared in the work. You need to write a function that will copy the tree. C or C++, preferably in C++.

Author: Nicolas Chabanovsky, 2010-12-07
Source

2 answers

If we assume that the tree is binary, then we can suggest the following:

Class declaration

class BinaryTreeNode {
public:
    BinaryTreeNode() : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(-1) {}
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}
public: 
    static int getDepth(BinaryTreeNode * node) {
        int left = 0, right = 0;
        left = getDepth(node->leftChild);
        return 0;
    }
public:
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

The copy function returns a pointer to the root of the new tree.

BinaryTreeNode * CopyTree(BinaryTreeNode * node)
{
    if (node == NULL)
        return NULL;

    BinaryTreeNode * newnode = new BinaryTreeNode(node->value);
    newnode->leftChild = CopyTree(node->leftChild);
    newnode->rightChild = CopyTree(node->rightChild);

    return newnode;
}
 4
Author: Nicolas Chabanovsky, 2010-12-07 12:36:24

If we assume that the tree is immutable and references to the parent vertex are not needed, then we can copy the tree in O (1), just copy the root

 2
Author: winger, 2011-01-06 14:09:34