Копия дерева на С++

#дерево #c #бинарное_дерево #алгоритм #cpp

В работе появилась простая, и в тоже время интересная задачка. Необходимо написать
функцию, которая будет копировать дерево. Язык С или С++, лучше на С++.
    

Ответы

Ответ 1

Если считать, что дерево бинарное, то можно предложить следующее:
Объявление класса
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;
};

Функция копирования возвращает указатель на корень нового дерева.
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;
}


Ответ 2

Если считать что дерево immutable и ссылки на родительскую вершину не нужны, то можно
скопировать дерево за O(1), достаточно скопировать только корень