0

我正在编写一个名为 的模板类RootedBinaryTree，它具有类似链表的结构，其元素的类型为Node，这是我在下面的头文件中定义的结构。二叉树中的每个节点都有 aparent Node *并且可以有 aleftChild Node *和 arightChild 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 来跟踪我到达那里的路径 if我沿着树向左走，如果我从树向右走，则为 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

提前感谢任何回答这个问题的人！非常感谢您的帮助。

4

1 回答 1

0

我会通过实现一个私有方法来实现，该方法getPath()返回从 t​​o 导致的移动（左或右）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();
}
于 2013-11-20T19:18:27.687 回答