c++ - 在模板化的 AVL 树中找不到我的错误

Question

我在实现 AVL 树时无法识别语法错误。我真的无法判断我是接近还是遥远（很可能是后者），我只是在寻找任何有足够耐心来看看这个的一般建议。非常感谢你，如果你真的做了一些寻找，这意味着你会花时间提供帮助。请原谅这里的代码量，我只是想确保所有上下文都存在。

我的测试已经识别并突出了一些带有模糊信息的行。我进入了下面的代码，并在注释中添加了“/////Error Here/////”，这样更容易看到。_root 的许多实例也被测试程序视为错误，我不知道为什么。我已经包含了源代码和标头代码。

再次，如果你花时间看这个，非常感谢你。如果不是，我完全理解。

map.cpp

#include "map.h"
#include <map> // helper container for thread copying

template <typename KEY, typename T>
Map<KEY, T>::Map(){
    // create a dummy root node
    _root = new Elem;
    _root->left = _root;  // empty tree
    _root->right = 0;
    _root->rightThread = false;
    _size = 0;

}

// copy constructor
template <typename KEY, typename T>
Map<KEY, T>::Map(const Map<KEY,T> &v){
    // if empty tree
    if (v._root == v._root->left){
        _root = new Elem;
        _root->left = _root;  // empty tree
        _root->right = 0;
        _size = 0;
    } else {
        _root = new Elem;
        _root->left = _root;
        _root->right = 0;
        copyCode(_root->left, v._root->left); // to deep copy the tree without dummy nodes
        copyThread(_root, v._root); // to copy the threading; must pass dummy nodes to complete the threads
        _size = v._size;
    }
}

// construct a key-element map to rethread the new tree
// the map contains all nodes key values and their corresonding elem node address
// for furture lookup in setting up threads
template <typename KEY, typename T>
void Map<KEY, T>::addToMap(Elem* root, map<KEY, Elem*> &keyElemMap){
    if (root) {
        keyElemMap[root->key] = root;
        addToMap(root->left, keyElemMap);
        if (!root->rightThread)
            addToMap(root->right, keyElemMap);
    }
}

// common copy code for thread copying
template <typename KEY, typename T>
void Map<KEY, T>::copyThread(Elem* &newRoot, Elem* origRoot){
    // construct the key-element map for new and orig tree
    map<KEY, Elem*> newKeyElemMap;
    map<KEY, Elem*> origKeyElemMap;
    addToMap(newRoot->left, newKeyElemMap);
    addToMap(origRoot->left, origKeyElemMap);

    // start at the last element in the tree, which threads to root
    typename std::map<KEY, Elem*>::reverse_iterator it = origKeyElemMap.rbegin();
    newKeyElemMap[it->first] -> rightThread = true;
    newKeyElemMap[it->first] -> right = newRoot;

    // then thread the rest of the tree backwardly
    ++it;
    it != origKeyElemMap.rend()){
        if (it->second->rightThread){
            newKeyElemMap[it->first] -> rightThread = true;
            newKeyElemMap[it->first] -> right = newKeyElemMap[ origKeyElemMap[it->first]->right->key ];
        }
        ++it;
    }
}

// common copy code for deep copy a tree without copying threads
template <typename KEY, typename T>
void  Map<KEY,T>::copyCode(Elem* &newRoot, Elem* origRoot){
    if (origRoot == 0)
        newRoot = 0;
    else{
        newRoot = new Elem;
        newRoot->key = origRoot->key;
        newRoot->data = origRoot->data;
        newRoot->rightThread = origRoot->rightThread;
        copyCode(newRoot->left, origRoot->left);
        if (!origRoot->rightThread)
            copyCode(newRoot->right, origRoot->right);
    }
}

template <typename KEY, typename T>
void Map<KEY, T>::destructCode(Map<KEY, T>::Elem *& p) {
    if(p->left) {
     destructCode(p->left);
   }
   if(!p->rightThread) {
     destructCode(p->right);
   }
   delete p;
}

template <typename KEY, typename T>
Map<KEY, T>::~Map() {
    destructCode(_root->left);
    delete _root;
}

template <typename KEY, typename T>
Map<KEY, T>& Map<KEY, T>::operator=(const Map<KEY, T> &rhs) {
    if (rhs._root == rhs._root->left){
        _root = new Elem;
        _root->left = _root;  // empty tree
        _root->right = 0;
        _size = 0;
    } else {
        _root = new Elem;
        _root->left = _root;
        _root->right = 0;
        copyCode(_root->left, rhs._root->left);
        _size = rhs._size;
    }
    return *this;
}

template<typename KEY, typename T>
int Map<KEY, T>::height(Elem *node) {
    return node == 0 ? -1 : node->height;
}

int max(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

template<typename KEY, typename T>
typename Map<KEY, T>::Elem* Map<KEY, T>::rotateRight(Elem* n) {
    Elem* m = n->left;
    Elem* p = m->right;

    // rotate
    m->right = n;
    n->left = p;

    // update height
    n->height = max(height(n->left), height(n->right)) + 1;
    m->height = max(height(m->left), height(m->right)) + 1;

    return m;
}

template<typename KEY, typename T>
typename Map<KEY, T>::Elem* Map<KEY, T>::rotateLeft(Elem* n) {
    Elem* m = n->right;
    Elem* p = m->left;

    // rotate
    m->left = n;
    n->right = p;

    // update height
    n->height = max(height(n->left), height(n->right)) + 1;
    m->height = max(height(m->left), height(m->right)) + 1;

    return m;
}

template<typename KEY, typename T>
typename Map<KEY, T>::Elem* Map<KEY, T>::doubleRotateRight(Elem* n) {
    // rotate right twice
    Elem* p = rotateRight(n);
    return rotateRight(p);
}

template<typename KEY, typename T>
typename Map<KEY, T>::Elem* Map<KEY, T>::doubleRotateLeft(Elem* n) {
    // and left twice
    Elem* p = rotateLeft(n);
    return rotateLeft(p);
}

template <typename KEY, typename T>
bool Map<KEY, T>::insert(KEY key, T info) {
    if (insert(_root->left, key, info, _root)){
    _size++;
        return true;
  }
    return false;
}

template <typename KEY, typename T>
bool Map<KEY, T>::insert(Map<KEY, T>::Elem *&cur, const KEY &key, const T &value, Map<KEY, T>::Elem* lastLeft) {
    if (cur == _root || cur == 0) { // map is empty
    cur = new Map<KEY, T>::Elem;
    cur->data = value;
    cur->left = 0;
    cur->right = lastLeft;
    cur->rightThread = true;
    return true;
  }

  if (value == cur->key){
    return false; // key exitsts already, don't insert
  }
  // insert at left
  if (value < cur->key)
    return insert( cur->left, key, value, cur);

  // insert at right
  if (!cur->rightThread){
    return insert(cur->right, key, value, lastLeft);
  } else {  // current's right is a thread; add a new node
    cur->rightThread = false;
    cur->right = new Map<KEY, T>::Elem;
    cur->right->data = value;
    cur->right->left = 0;
    cur->right->right = lastLeft;
      cur->right->rightThread = true;
    return true;
  }

  if (height(cur->left) - height(cur->right) == 2) { // calculate load factor
    if(key < cur->left->key) // outside case
      rotateRight(cur);
    else  // inside case
      doubleRotateRight(cur);
  }

  if (height(cur->left) - height(cur->right) == -2) { // calculate load factor
      if (key > cur->right->key) // outside case
        rotateLeft(cur);
      else  // inside case
        doubleRotateLeft(cur);
  }
}

template <typename KEY, typename T>
typename Map<KEY, T>::Elem& Map<KEY, T>::Iterator::operator*(){
    // fill in here
    return *_cur;
}

template <typename KEY, typename T>
typename Map<KEY, T>::Elem* Map<KEY, T>::Iterator::operator->(){
    // fill in here
    return _cur;
}

template <typename KEY, typename T>
int Map<KEY, T>::size() const{
    return _size;
}

template <typename KEY, typename T>
typename Map<KEY, T>::Iterator Map<KEY, T>::Iterator::operator++(int){
    // fill in here
    // in-order traversal
  Elem* p;
  p = this->_cur;
  while (!p->rightThread) {
    p = p->right;
  }
  while(p->right != _root) { /////Error Here/////
     if (!p->rightThread) {
       p = p->right;
             this._cur = p;
             return Map<KEY, T>::Iterator(p);
       while (p->left) {
         p = p->left;
       }
    } else {
       p = p->right;
             this->_cur = p;
             return Map<KEY, T>::Iterator(p);
    }
  }
  this._cur = _root; /////Error Here/////
  return _root;

    Elem *current, *parent;
    current = this._cur;

    return *this;
}
// output the structure of tree. The tree is output as "lying down"
// in which _root is the LEFT most Elem.
template <typename KEY, typename T>
void Map<KEY, T>::printTree(ostream& out, int level, Elem *p) const{
    int i;
    if (p) {
        if (p->right && !p->rightThread)
            printTree(out, level+1,p->right);
        for(i=0;i<level;i++) {
            out << "\t";
        }
        out << p->key << " " << p->data << '\n';
        printTree(out, level+1,p->left);
    }
}

// outputs information in tree in inorder traversal order
template <typename KEY, typename T>
ostream& Map<KEY, T>::dump(ostream& out) const{
    if ( _root == _root->left) {// tree empty
        return out;
    }
    printTree(out, 0, _root->left);   // print tree structure
    return out;
}


// outputs using overloaded << operator
template<typename KEY, typename T>
ostream& operator<< (ostream& out, const Map<KEY, T>& v){
    v.dump(out);
    return out;
}

map.h

#ifndef MAP_H
#define MAP_H
#include <iostream>
#include <map>
// #include "map.cpp"
using namespace std;

template <typename KEY, typename T>
class Map{
private:
    struct Elem {
        KEY key;
        T data;
        Elem *left;
        Elem *right;
        bool rightThread;  // normal right child link or a thread link
        int height;
    };
    Elem *_root;  // a dummy root sentinel /////Error Here/////
    int _size;
public:
    // insert starter for other code and tests to use
    bool insert(KEY k, T t);
    // helper method for inserting into tree. takes care of insertion and balancing, returns true if successful
    bool insert(Elem *& root, const KEY &key, const T &data, Elem* lastLeft);

    // find height of node in the tree
    int height(Elem* node);

    // methods to do rotations
    Elem* rotateRight(Elem* n);
    Elem* rotateLeft(Elem* n);
    Elem* doubleRotateRight(Elem* n);
    Elem* doubleRotateLeft(Elem* n);

    // helper method for print tree
    void printTree(ostream& out, int level, Elem *p) const;

    // common code for deallocation
    void destructCode(Elem *& p);

    // common code for copy tree; not required.
    void copyCode(Elem* &newRoot, Elem* origRoot);

    // common code for deep copying threaded tree
    void addToMap(Elem* root, map<KEY, Elem*> &keyElemMap);
    void copyThread(Elem* &newRoot, Elem* origRoot);

public:
    // a simple Iterator, traverse the collection in one direction
    class Iterator{
    public:
        Iterator(){}
        explicit Iterator(Elem *cur):_cur(cur) {}
        Elem& operator*();
        Elem* operator->();
        Iterator operator++(int);
        bool operator==(Iterator it);
        bool operator!=(Iterator it);
    private:
        Elem* _cur;
    };
    Iterator begin() const;
    Iterator end() const;

    // constructs empty Map
    Map();

    // copy constructor
    Map(const Map &rhs);

    // destructor
    ~Map();

    // assignment operator
    Map& operator=(const Map &rhs);

    // return size of the Map
    int size() const;

    // return an iterator pointing to the end if the element is not found,
    // otherwise, return an iterator to the element
    Iterator find(KEY) const;

    // overloaded subscript operator
    T& operator[](KEY);

    // output the underlying BST
    ostream& dump(ostream& out) const;
};

template<typename KEY, typename T>
ostream& operator<< (ostream&, const Map<KEY, T>&);

#include "map.cpp"  // must include source file for template compilation
#endif

标签： c++syntaxavl-tree