Я пишу шаблон класса под названием 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
Заранее спасибо всем, кто ответит на это! Ваша помощь очень ценится.
Я бы сделал это путем реализации частного метода 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();
}
Других решений пока нет …