Перегрузчик opertator = () в шаблонном классе корневого бинарного дерева

Я пишу шаблон класса под названием RootedBinaryTree, которая имеет структуру, похожую на связанный список, элементы которой имеют тип Node, который является структурой, которую я определил в заголовочном файле ниже. Каждый узел в двоичном дереве имеет parent Node * и может иметь leftChild Node * и rightChild Node * или нет детей. (Например: если вы хотите нарисовать корневое двоичное дерево, оно должно выглядеть примерно так http://mathworld.wolfram.com/images/eps-gif/CompleteBinaryTree_1000.gif).

Укорененное двоичное дерево состоит из двух членов: root а также currentPosition которые имеют тип узла.
Когда я перегружаю operator=() Я должен сделать что-то вроде currentPosition = RHS.currentPosition; (это то, что я написал там в настоящее время). Я знаю, что это неправильно, и что мне нужно сделать, это найти узел в *this дерево, которое соответствует currentPosition Node * в RHS дерево.

Мой вопрос: что такое хороший алгоритм для обхода дерева RHS, чтобы найти его currentPosition Node * и найти соответствующий Node в вызывающем дереве?

Моя идея состоит в том, чтобы создать пустую строку и пройти RHS с какой-то глубиной сначала ищите алгоритм поиска, начиная с корня вниз, пока я не найду currentPosition, и отследите путь, который я выбрал, чтобы попасть туда, добавив 0 к концу строки, если я спустился вниз по дереву слева, или 1, если я спустился вниз по дереву вправо, а затем с помощью этой строки, чтобы пройти *this дерево, которое должно привести меня к соответствующему Node, Однако я знаю, что должен быть лучший способ сделать это (частично из интуиции, частично потому, что мой инструктор сказал мне, что есть лучший способ, ха-ха).

Вот соответствующие файлы:

RootedBinaryTree.h

#ifndef ROOTEDBINARYTREE_H
#define ROOTEDBINARYTREE_H

template <class T>
class RootedBinaryTree
{
private:
template <class T>
struct Node
{
T nodeData;
Node<T> * parent;
Node<T> * leftChild;
Node<T> * rightChild;

Node<T>::Node()
{
parent = leftChild = rightChild = 0L;
}
};
Node<T> * root;
Node<T> * currentPosition;

void copySubtree(Node<T> * & target, Node<T> * const & original);
void deleteSubtree(Node<T> * n);

public:
RootedBinaryTree(const T & rootData);
RootedBinaryTree(const RootedBinaryTree<T> & original);
~RootedBinaryTree();
void toRoot();
bool moveLeft();
bool moveRight();
bool moveUp();
T getData() const {return currentPosition->nodeData;};
RootedBinaryTree<T> & operator=(const RootedBinaryTree<T> & RHS);
void combineTrees(const RootedBinaryTree<T> & leftTree, const RootedBinaryTree<T> & rightTree);
void setNodeData(const T & nodeData);
};

#endif

RootedBinaryTree.cpp

#ifndef ROOTEDBINARYTREE_CPP
#define ROOTEDBINARYTREE_CPP

#include "RootedBinaryTree.h"
template<class T>
void RootedBinaryTree<T>::copySubtree(Node<T> * & target, Node<T> * const & original)
{// Assumes that target's leftChild = rightChild = 0L. I.e. target is a leaf.
target = new Node<T>;
if(original->leftChild != 0L)
{
target->leftChild->parent = target;
copySubtree(target->leftChild, original->leftChild);
}
else
{
target->leftChild = 0L;
}
// ^^^ copy targets left (and right) children to originals
if(original->rightChild != 0L)
{
target->rightChild->parent = target;
copySubtree(target->rightChild, original->rightChild);
}
else
{
target->rightChild = 0L;
}
target->nodeData = original->nodeData;
}

template <class T>
void RootedBinaryTree<T>::deleteSubtree(Node<T> * n)                                                // Done
{// Assumes that n is a valid node.
if(n->leftChild != 0L) deleteSubtree(n->leftChild);                                             // Delete all nodes in left subtree
if(n->rightChild != 0L) deleteSubtree(n->rightChild);                                           // Delete all nodes in right subtree
delete n;
}

template <class T>
RootedBinaryTree<T>::RootedBinaryTree(const T & rootData)                                           // Done
{
root = new Node <T>;                                                                            // Roots parent = leftChild = rightChild = 0L
root->nodeData = rootData;
currentPosition = root;
}

template <class T>
RootedBinaryTree<T>::RootedBinaryTree(const RootedBinaryTree<T> & original)                         // done
{
root = currentPosition = new Node<T>;
*this = original;
}

template <class T>
RootedBinaryTree<T>::~RootedBinaryTree()                                                            // done
{
deleteSubtree(root);                                                                            // root will be valid because of our constructor and other methods
root = currentPosition = 0L;
}

template <class T>
void RootedBinaryTree<T>::toRoot()                                                                  // Done
{
currentPosition = root;
}

template <class T>
bool RootedBinaryTree<T>::moveUp()                                                                  // Done
{
if(currentPosition->parent == 0L) return false;                                                 // If we are at the root of the tree, we cannot move up it.
currentPosition = currentPosition->parent;
return true;
}

template <class T>
bool RootedBinaryTree<T>::moveLeft()                                                                // Done
{
if(currentPosition->leftChild == 0L) return false;
currentPosition = currentPosition->leftChild;
return true;
}

template <class T>
bool RootedBinaryTree<T>::moveRight()                                                               // Done
{
if(currentPosition->rightChild == 0L) return false;
currentPosition = currentPosition->rightChild;
return true;
}

template <class T>
RootedBinaryTree<T> & RootedBinaryTree<T>::operator=(const RootedBinaryTree<T> & RHS)
{
if(&RHS == this)
{
return *this;
}
this->~RootedBinaryTree();
copySubtree(root, RHS.root);
currentPosition = RHS.currentPosition; // This is wrong.

return *this;
}

template <class T>
void RootedBinaryTree<T>::combineTrees(const RootedBinaryTree<T> & leftTree, const RootedBinaryTree<T> & rightTree)
{ // Copies leftTree into root's left tree and rightTree into root's right tree.
if(this == &leftTree || this == &rightTree)
{
throw "A rooted binary tree cannot be combined with itself.";
}
if(root->leftChild != 0L) deleteSubtree(root->leftChild);
if(root->rightChild != 0L) deleteSubtree(root->rightChild);
copySubtree(root->leftChild, leftTree.root);
copySubtree(root->rightChild, rightTree.root);
}

template <class T>
void RootedBinaryTree<T>::setNodeData(const T & nodeData)
{
currentPosition->nodeData = nodeData;
}

#endif

Заранее спасибо всем, кто ответит на это! Ваша помощь очень ценится.

0

Решение

Я бы сделал это путем реализации частного метода getPath() который возвращает список ходов (влево или вправо), который ведет от root в currentPosition:

template <class T>
list<bool> RootedBinaryTree<T>::getPath() const
{
list<bool> path;

Node<T> *p1=currentPosition;
Node<T> *p2 = p1->parent;

while(p2 != 0L)
{
if(p2->leftChild==p1)
path.push_front(true);
else
path.push_front(false); // yes, I know this can be done more concisely; I'm going for clarity
p1=p2;
p2=p1->parent;
}
return(path);
}

Вызовите этот метод в другом дереве, получите путь, затем следуйте по этому пути в этом дереве:

template <class T>
void RootedBinaryTree<T>::followPath(list<bool> path)
{
currentPosition = root;

for(list<bool>::const_iterator itr=path.begin(); itr !=path.end() ; ++itr)
if(*itr)
moveLeft();
else
moveRight();
}
0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]