将数据（将对推送到对列表）添加到 AVL 树中的节点无法正常工作
Adding data (pushing pair to list of pairs) to nodes in AVL tree is not working as I expect it to
我需要从文本文件中读取单词并存储它们出现的频率、它们在文档中的位置以及它们出现的文档名称。这需要存储在一个 AVL 树中，单词为钥匙。我有一些工作，但我们需要将文档的位置和名称成对存储。这是我遇到问题的部分。我花了几个小时尝试不同的事情，但我不明白为什么它会这样做。基本上它似乎对文本文件中的前几个单词有点作用，但它读取的每个新单词都会将之前的单词位置和文档对添加到新单词上。对不起，我的代码混乱，解释不力，我还是新手。这是我的输出的屏幕截图。
https://i.imgur.com/Be1EBKM.png
main.cpp代码
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include <sstream>
#include <queue>
#include <cstdlib>
#include <utility>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;
#include "AVL_ADT.h"
struct DATA
{
string key;
int info;
list<pair<string, int> > index;
bool operator<(const DATA& d) const {
return info < d.info;
}
};
string trim(string input) {
stringstream ss;
for (int x = 0; x < (int) input.size(); x++) {
if (isalpha(input[x])) {
ss << input[x];
}
}
if (ss.str().length() > 0)
return ss.str();
else
return "";
}
priority_queue<DATA> dataQueue;
void addQueue(DATA ss) {
dataQueue.push(ss);
}
void print(DATA ss) {
cout << ss.key << "," << ss.info << endl;
list<pair<string, int> > :: iterator it;
for(it = ss.index.begin(); it != ss.index.end(); it++){
cout << it->first << ",";
cout << it->second << endl;
}
}
int main() {
AvlTree<DATA, string> tree;
if(tree.AVL_Empty())
cout << "Empty tree."<< endl;
string documentName;
ifstream file;
file.open("testfile.txt");
string word;
int location = 1;
documentName = "testfile.txt";
DATA newItem;
while(file>>word){
word = trim(word);
newItem.key = word;
newItem.info = 1;
if (tree.AVL_Retrieve(word, newItem)) {
tree.AVL_Delete(word);
newItem.info++;
newItem.index.push_front(make_pair(documentName, location));
tree.AVL_Insert(newItem);
}
else {
newItem.index.push_front(make_pair(documentName, location));
tree.AVL_Insert(newItem);
}
location ++;
}
file.close();
tree.AVL_Print();
cout<<endl;
tree.AVL_Traverse(addQueue);
while (!dataQueue.empty()) {
DATA d = dataQueue.top();
print(d);
dataQueue.pop();
}
return 0;
}
这里是头文件，如果有帮助的话。
// ==================== MACROS ====================
#define LH +1 // Left High
#define EH 0 // Even High
#define RH -1 // Right High
// NODE Definitions
template <class TYPE>
struct NODE
{
TYPE data;
NODE *left;
NODE *right;
int bal;
} ; // NODE
// Class Declaration
template <class TYPE, class KTYPE>
class AvlTree
{
private:
int count;
NODE<TYPE> *tree;
NODE<TYPE> *_insert (NODE<TYPE> *root,
NODE<TYPE> *newPtr,
bool& taller);
NODE<TYPE> *leftBalance (NODE<TYPE> *root,
bool& taller);
NODE<TYPE> *rotateLeft (NODE<TYPE> *root);
NODE<TYPE> *rightBalance (NODE<TYPE> *root,
bool& taller);
NODE<TYPE> *rotateRight (NODE<TYPE> *root);
NODE<TYPE> *_delete (NODE<TYPE> *root,
KTYPE dltKey,
bool& shorter,
bool& success);
NODE<TYPE> *dltLeftBalance (NODE<TYPE> *root,
bool& smaller);
NODE<TYPE> *dltRightBalance (NODE<TYPE> *root,
bool& shorter);
NODE<TYPE> *_retrieve (KTYPE key,
NODE<TYPE> *root);
NODE<TYPE> *_update (KTYPE key,
NODE<TYPE> *root);
void _traversal (void (*process)(TYPE dataProc),
NODE<TYPE> *root);
void _destroyAVL (NODE<TYPE> *root);
// The following function is used for debugging.
void _print (NODE<TYPE> *root, int level);
public:
AvlTree (void);
~AvlTree (void);
bool AVL_Insert (TYPE dataIn);
bool AVL_Delete (KTYPE dltKey);
bool AVL_Retrieve (KTYPE key, TYPE& dataOut);
bool AVL_Update (KTYPE key, TYPE dataIn);
void AVL_Traverse (void (*process)(TYPE dataProc)); //in-order
bool AVL_Empty (void);
bool AVL_Full (void);
int AVL_Count (void);
// The following function is used for debugging.
void AVL_Print (void);
} ; // class AvlTree
/* =================== Constructor ===================
Initializes private data.
Pre class is being defined
Post private data initialized
*/
template <class TYPE, class KTYPE>
AvlTree<TYPE, KTYPE> :: AvlTree (void)
{
// Statements
tree = NULL;
count = 0;
} // Constructor
/* ==================== AVL_Insert ====================
This function inserts new data into the tree.
Pre dataIn contains data to be inserted
Post data have been inserted or memory overflow
Return success (true) or overflow (false)
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Insert (TYPE dataIn)
{
// Local Definitions
NODE<TYPE> *newPtr;
bool taller;
// Statements
if (!(newPtr = new NODE<TYPE>))
return false;
newPtr->bal = EH;
newPtr->right = NULL;
newPtr->left = NULL;
newPtr->data = dataIn;
tree = _insert(tree, newPtr, taller);
count++;
return true;
} // Avl_Insert
/* ======================= _insert =======================
This function uses recursion to insert the new data into
a leaf node in the AVL tree.
Pre application has called AVL_Insert, which passes
root and data pointers
Post data have been inserted
Return pointer to [potentially] new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: _insert (NODE<TYPE> *root,
NODE<TYPE> *newPtr,
bool& taller)
{
// Statements
if (!root)
{
root = newPtr;
taller = true;
return root;
} // if NULL tree
if (newPtr->data.key < root->data.key)
{
root->left = _insert(root->left,
newPtr,
taller);
if (taller)
// Left subtree is taller
switch (root->bal)
{
case LH: // Was left high--rotate
root = leftBalance (root, taller);
break;
case EH: // Was balanced--now LH
root->bal = LH;
break;
case RH: // Was right high--now EH
root->bal = EH;
taller = false;
break;
} // switch
} // new < node
else
// new data >= root data
{
root->right = _insert (root->right,
newPtr,
taller);
if (taller)
// Right subtree is taller
switch (root->bal)
{
case LH: // Was left high--now EH
root->bal = EH;
taller = false;
break;
case EH: // Was balanced--now RH
root->bal = RH;
break;
case RH: // Was right high--rotate
root = rightBalance (root, taller);
break;
} // switch
} // else new data >= root data
return root;
} // _insert
/* ===================== leftBalance =====================
The tree is out of balance to the left. This function
rotates the tree to the right.
Pre the tree is left high
Post balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE> *AvlTree<TYPE, KTYPE>
:: leftBalance (NODE<TYPE> *root,
bool& taller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
leftTree = root->left;
switch (leftTree->bal)
{
case LH: // Left High--Rotate Right
root->bal = EH;
leftTree->bal = EH;
// Rotate Right
root = rotateRight (root);
taller = false;
break;
case EH: // This is an error
cout <<"\n\a\aError in leftBalance\n";
exit (100);
case RH: // Right High - Requires double rotation:
// first left, then right
rightTree = leftTree->right;
switch (rightTree->bal)
{
case LH: root->bal = RH;
leftTree->bal = EH;
break;
case EH: root->bal = EH;
leftTree->bal = EH;
break;
case RH: root->bal = EH;
leftTree->bal = LH;
break;
} // switch rightTree
rightTree->bal = EH;
// Rotate Left
root->left = rotateLeft (leftTree);
// Rotate Right
root = rotateRight (root);
taller = false;
} // switch leftTree
return root;
} // leftBalance
/* ===================== rotateLeft ======================
This function exchanges pointers so as to rotate the
tree to the left.
Pre root points to tree to be rotated
Post NODE rotated and new root returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: rotateLeft (NODE<TYPE> *root)
{
// Local Definitions
NODE<TYPE> *tempPtr;
// Statements
tempPtr = root->right;
root->right = tempPtr->left;
tempPtr->left = root;
return tempPtr;
} // rotateLeft
/* ===================== rotateRight =====================
This function exchanges pointers to rotate the tree
to the right.
Pre root points to tree to be rotated
Post NODE rotated and new root returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: rotateRight (NODE<TYPE> *root)
{
// Local Definitions
NODE<TYPE> *tempPtr;
// Statements
tempPtr = root->left;
root->left = tempPtr->right;
tempPtr->right = root;
return tempPtr;
} // rotateRight
/* ==================== rightBalance ===================
The tree is out-of-balance to the right. This function
rotates the tree to the left.
Pre The tree is right high
Post Balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: rightBalance (NODE<TYPE> *root, bool& taller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
rightTree = root->right;
switch (rightTree->bal)
{
case LH: // Left High - Requires double rotation:
// first right, then left
leftTree = rightTree-> left;
// First Rotation - Left
switch (leftTree->bal)
{
case RH: root->bal = LH;
rightTree->bal = EH;
break;
case EH: root->bal = EH;
rightTree->bal = EH;
break;
case LH: root->bal = EH;
rightTree->bal = RH;
break;
} // switch
leftTree->bal = EH;
root->right = rotateRight (rightTree);
root = rotateLeft (root);
taller = false;
break;
case EH: // Deleting from balanced node
root->bal = EH;
taller = false;
break;
case RH: // Right High - Rotate Left
root->bal = EH;
rightTree->bal = EH;
root = rotateLeft (root);
taller = false;
break;
} // switch
return root;
} // rightBalance
/* ====================== AVL_Delete ======================
This function deletes a node from the tree and rebalances
it if necessary.
Pre dltKey contains key to be deleted
Post the node is deleted and its space recycled
-or- an error code is returned
Return success (true) or not found (false)
*/
template <class TYPE, class KTYPE>
bool AvlTree <TYPE, KTYPE> :: AVL_Delete (KTYPE dltKey)
{
// Local Definitions
bool shorter;
bool success;
NODE<TYPE> *newRoot;
// Statements
newRoot = _delete (tree, dltKey, shorter, success);
if (success)
{
tree = newRoot;
count--;
} // if
return success;
} // AVL_Delete
/* ======================== _delete =======================
This function deletes a node from the tree and rebalances
it if necessary.
Pre dltKey contains key of node to be deleted
shorter is Boolean indicating tree is shorter
Post the node is deleted and its space recycled
-or- if key not found, tree is unchanged
Return true if deleted, false if not found
pointer to root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: _delete (NODE<TYPE> *root,
KTYPE dltKey,
bool& shorter,
bool& success)
{
// Local Definitions
NODE<TYPE> *dltPtr;
NODE<TYPE> *exchPtr;
NODE<TYPE> *newRoot;
// Statements
if (!root)
{
shorter = false;
success = false;
return NULL;
} // if -- base case
if (dltKey < root->data.key)
{
root->left = _delete (root->left, dltKey,
shorter, success);
if (shorter)
root = dltRightBalance (root, shorter);
} // if less
else if (dltKey > root->data.key)
{
root->right = _delete (root->right, dltKey,
shorter, success);
if (shorter)
root = dltLeftBalance (root, shorter);
} // if greater
else
// Found equal node
{
dltPtr = root;
if (!root->right)
// Only left subtree
{
newRoot = root->left;
success = true;
shorter = true;
delete (dltPtr);
return newRoot; // base case
} // if true
else
if (!root->left)
// Only right subtree
{
newRoot = root->right;
success = true;
shorter = true;
delete (dltPtr);
return newRoot; // base case
} // if
else
// Delete NODE has two subtrees
{
exchPtr = root->left;
while (exchPtr->right)
exchPtr = exchPtr->right;
root->data = exchPtr->data;
root->left = _delete (root->left,
exchPtr->data.key,
shorter,
success);
if (shorter)
root = dltRightBalance (root, shorter);
} // else
} // equal node
return root;
} // _delete
// ================== dltLeftBalance ==================
/* The tree is out-of-balance to the left (left high)--
rotates the tree to the right.
Pre The tree is left high
Post Balance has been restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: dltLeftBalance (NODE<TYPE> *root,
bool& smaller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
switch (root->bal)
{
case RH: root->bal = EH;
break;
case EH: // Delete occurred on right
root->bal = LH;
smaller = false;
break;
case LH: leftTree = root->left;
switch (leftTree->bal)
{
case LH:
case EH: // Rotate Single Left
if (leftTree->bal == EH)
{
root->bal = LH;
leftTree->bal = RH;
smaller = false;
} // if
else
{
root->bal = EH;
leftTree->bal = EH;
} // else
root = rotateRight (root);
break;
case RH: //Double Rotation
rightTree = leftTree->right;
switch (rightTree->bal)
{
case LH: root->bal = RH;
leftTree->bal = EH;
break;
case EH: root->bal = EH;
leftTree->bal = EH;
break;
case RH: root->bal = EH;
leftTree->bal = LH;
break;
} // switch
rightTree->bal = EH;
root->left = rotateLeft (leftTree);
root = rotateRight (root);
break;
} // switch : leftTree->bal
} // switch : root->bal
return root;
} // dltLeftBalance
/* =================== dltRightBalance ==================
The tree is shorter after a delete on the left.
Adjust the balance factors and rotate the tree
to the left if necessary.
Pre the tree is shorter
Post balance factors adjusted and balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: dltRightBalance (NODE<TYPE> *root,
bool& shorter)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
switch (root->bal)
{
case LH: // Deleted Left--Now balanced
root->bal = EH;
break;
case EH: // Now Right high
root->bal = RH;
shorter = false;
break;
case RH: // Right High - Rotate Left
rightTree = root->right;
if (rightTree->bal == LH)
// Double rotation required
{
leftTree = rightTree->left;
switch (leftTree->bal)
{
case LH: rightTree->bal = RH;
root->bal = EH;
break;
case EH: root->bal = EH;
rightTree->bal = EH;
break;
case RH: root->bal = LH;
rightTree->bal = EH;
break;
} // switch
leftTree->bal = EH;
// Rotate Right then Left
root->right = rotateRight (rightTree);
root = rotateLeft (root);
} // if rightTree->bal == LH
else
{
// Single Rotation Only
switch (rightTree->bal)
{
case LH:
case RH: root->bal = EH;
rightTree->bal = EH;
break;
case EH: root->bal = RH;
rightTree->bal = LH;
shorter = false;
break;
} // switch rightTree->bal
root = rotateLeft (root);
} // else
} // switch root bal
return root;
} // dltRightBalance
/* ==================== AVL_Retrieve ===================
Retrieve node searches the tree for the node containing
the requested key and returns pointer to its data.
Pre dataOut is variable to receive data
Post tree searched and data returned
Return true if found, false if not found
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE>
:: AVL_Retrieve (KTYPE key, TYPE& dataOut)
{
// Local Definitions
NODE<TYPE> *node;
// Statements
if (!tree)
return false;
node = _retrieve (key, tree);
if (node)
{
dataOut = node->data;
return true;
} // if found
else
return false;
} // AVL_Retrieve
/* ===================== _retrieve =====================
Retrieve searches tree for node containing requested
key and returns its data to the calling function.
Pre AVL_Retrieve called: passes key to be located
Post tree searched and data pointer returned
Return address of matching node returned
if not found, NULL returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: _retrieve (KTYPE key,
NODE<TYPE> *root)
{
// Statements
if (root)
{
if (key < root->data.key)
return _retrieve (key, root->left);
else if (key > root->data.key)
return _retrieve (key, root->right);
else
// Found equal key
return (root);
} // if root
else
//Data not in tree
return root;
} // _retrieve
/* ==================== AVL_Update ===================
Update node searches the tree for the node containing
the requested key and updates with new data.
Pre dataIn is new data
Post tree searched and node updated
Return true if found, false if not found
*/
/*
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE>
:: AVL_Update (KTYPE key, TYPE dataIn)
{
// Local Definitions
NODE<TYPE> *node;
// Statements
if (!tree)
return false;
node = _update (key, tree);
if (node)
{
node->data = dataIn;
return true;
} // if found
else
return false;
} // AVL_Retrieve*/
/* ===================== _update =====================
Retrieve searches tree for node containing requested
key and returns its data to the calling function.
Pre AVL_Retrieve called: passes key to be located
Post tree searched and data pointer returned
Return address of matching node returned
if not found, NULL returned
*/
/*template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: _update (KTYPE key,
NODE<TYPE> *root)
{
// Statements
if (root)
{
if (key < root->data.key)
return _update (key, root->left);
else if (key > root->data.key)
return _update (key, root->right);
else
// Found equal key
return (root);
} // if root
else
//Data not in tree
return root;
} // _retrieve*/
/* ==================== AVL_Traverse ====================
Process tree using inorder traversal.
Pre process used to "visit" nodes during traversal
Post all nodes processed in LNR (inorder) sequence
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>
:: AVL_Traverse (void (*process)(TYPE dataProc))
{
// Statements
_traversal (process, tree);
return;
} // end AVL_Traverse
/* ===================== _traversal =====================
Traverse tree using inorder traversal. To process a
node, we use the function passed when traversal is called.
Pre tree has been created (may be null)
Post all nodes processed
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>
:: _traversal (void(*process)(TYPE dataproc),
NODE<TYPE> *root)
{
// Statements
if (root)
{
_traversal (process, root->left);
process (root->data);
_traversal (process, root->right);
} // if
return;
} // _traversal
/* =================== AVL_Empty ==================
Returns true if tree is empty, false if any data.
Pre tree has been created; may be null
Returns true if tree empty, false if any data
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Empty (void)
{
// Statements
return (count == 0);
} // AVL_Empty
/* =================== AVL_Full ===================
If there is no room for another node, returns true.
Pre tree has been created
Returns true if no room, false if room
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Full (void)
{
// Local Definitions
NODE<TYPE> *newPtr;
// Statements
newPtr = new NODE<TYPE>;
if (newPtr)
{
delete newPtr;
return false;
} // if
else
return true;
} // AVL_Full
/* =================== AVL_Count ===================
Returns number of nodes in tree.
Pre tree has been created
Returns tree count
*/
template <class TYPE, class KTYPE>
int AvlTree<TYPE, KTYPE> :: AVL_Count (void)
{
// Statements
return (count);
} // AVL_Count
/* =================== Destructor ===================
Deletes all data in tree and recycles memory.
The nodes are deleted by calling a recursive
function to traverse the tree in inorder sequence.
Pre tree is a pointer to a valid tree
Post all data have been deleted
*/
template <class TYPE, class KTYPE>
AvlTree<TYPE, KTYPE> :: ~AvlTree (void)
{
// Statements
if (tree)
_destroyAVL (tree);
} // Destructor
/* =================== _destroyAVL ===================
Deletes all data in tree and recycles memory.
The nodes are deleted by calling a recursive
function to traverse the tree in postorder sequence.
Pre tree is being destroyed
Post all data have been deleted
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>
:: _destroyAVL (NODE<TYPE> *root)
{
// Statements
if (root)
{
_destroyAVL (root->left);
_destroyAVL (root->right);
delete root;
} // if
return;
} // _destroyAVL
/* ============================= AVL_Print =============================
This function prints the AVL tree by calling a recursive inorder
traversal. NOTE: THIS IS NOT AN APPLICATION ADT FUNCTION. IT IS
USED ONLY FOR DEBUGGING PURPOSES.
To correctly visualize the tree when turned sideways, the actual
traversal is RNL.
Pre Tree must be initialized. Null tree is OK.
Level is node level: root == 0
Post Tree has been printed.
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE> :: AVL_Print (void)
{
/* statements */
_print (tree, 0);
return;
} /* AVL_PRINT */
/* ============================= _print =============================
This function is not a part of the ADT. It is included to verify
that the tree has been properly built by printing out the tree
structure.
*/
/* This function uses recursion to print the tree. At each level, the
level number is printed along with the node contents (an integer).
Pre root is the root of a tree or subtree
level is the level of the tree: tree root is 0
Post Tree has been printed.
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE> :: _print (NODE<TYPE> *root,
int level)
{
/* Local Definitions */
int i;
/* Statements */
if (root)
{
_print ( root->right, level + 1 );
cout << "bal " << setw(3) << root->bal
<< ": Level " << setw(3) << level;
for (i = 0; i <= level; i++ )
cout << "....";
cout << setw(3) << root->data.key;
if (root->bal == LH)
cout << " (LH)\n";
else if (root->bal == RH)
cout << " (RH)\n";
else
cout << " (EH)\n";
_print ( root->left, level + 1 );
} /* if */
} /* AVL_Print */
我花了一些时间来理解您的问题并确定哪些是正确的（AVL 部分）哪些是未经测试的（实际上是 main 代码）。
问题是 newItem 是在 while 循环之外声明的，因此它在迭代之间保留其值，特别是 index 成员。所以对于一个微不足道的修复，只需在循环中声明它：
...
while(file>>word){
DATA newItem;
word = trim(word);
newItem.key = word;
...
这足以使其所有成员默认初始化，这将确保每次迭代都有一个 emply 列表。
我需要从文本文件中读取单词并存储它们出现的频率、它们在文档中的位置以及它们出现的文档名称。这需要存储在一个 AVL 树中，单词为钥匙。我有一些工作，但我们需要将文档的位置和名称成对存储。这是我遇到问题的部分。我花了几个小时尝试不同的事情，但我不明白为什么它会这样做。基本上它似乎对文本文件中的前几个单词有点作用，但它读取的每个新单词都会将之前的单词位置和文档对添加到新单词上。对不起，我的代码混乱，解释不力，我还是新手。这是我的输出的屏幕截图。
https://i.imgur.com/Be1EBKM.png
main.cpp代码
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include <sstream>
#include <queue>
#include <cstdlib>
#include <utility>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;
#include "AVL_ADT.h"
struct DATA
{
string key;
int info;
list<pair<string, int> > index;
bool operator<(const DATA& d) const {
return info < d.info;
}
};
string trim(string input) {
stringstream ss;
for (int x = 0; x < (int) input.size(); x++) {
if (isalpha(input[x])) {
ss << input[x];
}
}
if (ss.str().length() > 0)
return ss.str();
else
return "";
}
priority_queue<DATA> dataQueue;
void addQueue(DATA ss) {
dataQueue.push(ss);
}
void print(DATA ss) {
cout << ss.key << "," << ss.info << endl;
list<pair<string, int> > :: iterator it;
for(it = ss.index.begin(); it != ss.index.end(); it++){
cout << it->first << ",";
cout << it->second << endl;
}
}
int main() {
AvlTree<DATA, string> tree;
if(tree.AVL_Empty())
cout << "Empty tree."<< endl;
string documentName;
ifstream file;
file.open("testfile.txt");
string word;
int location = 1;
documentName = "testfile.txt";
DATA newItem;
while(file>>word){
word = trim(word);
newItem.key = word;
newItem.info = 1;
if (tree.AVL_Retrieve(word, newItem)) {
tree.AVL_Delete(word);
newItem.info++;
newItem.index.push_front(make_pair(documentName, location));
tree.AVL_Insert(newItem);
}
else {
newItem.index.push_front(make_pair(documentName, location));
tree.AVL_Insert(newItem);
}
location ++;
}
file.close();
tree.AVL_Print();
cout<<endl;
tree.AVL_Traverse(addQueue);
while (!dataQueue.empty()) {
DATA d = dataQueue.top();
print(d);
dataQueue.pop();
}
return 0;
}
这里是头文件，如果有帮助的话。
// ==================== MACROS ====================
#define LH +1 // Left High
#define EH 0 // Even High
#define RH -1 // Right High
// NODE Definitions
template <class TYPE>
struct NODE
{
TYPE data;
NODE *left;
NODE *right;
int bal;
} ; // NODE
// Class Declaration
template <class TYPE, class KTYPE>
class AvlTree
{
private:
int count;
NODE<TYPE> *tree;
NODE<TYPE> *_insert (NODE<TYPE> *root,
NODE<TYPE> *newPtr,
bool& taller);
NODE<TYPE> *leftBalance (NODE<TYPE> *root,
bool& taller);
NODE<TYPE> *rotateLeft (NODE<TYPE> *root);
NODE<TYPE> *rightBalance (NODE<TYPE> *root,
bool& taller);
NODE<TYPE> *rotateRight (NODE<TYPE> *root);
NODE<TYPE> *_delete (NODE<TYPE> *root,
KTYPE dltKey,
bool& shorter,
bool& success);
NODE<TYPE> *dltLeftBalance (NODE<TYPE> *root,
bool& smaller);
NODE<TYPE> *dltRightBalance (NODE<TYPE> *root,
bool& shorter);
NODE<TYPE> *_retrieve (KTYPE key,
NODE<TYPE> *root);
NODE<TYPE> *_update (KTYPE key,
NODE<TYPE> *root);
void _traversal (void (*process)(TYPE dataProc),
NODE<TYPE> *root);
void _destroyAVL (NODE<TYPE> *root);
// The following function is used for debugging.
void _print (NODE<TYPE> *root, int level);
public:
AvlTree (void);
~AvlTree (void);
bool AVL_Insert (TYPE dataIn);
bool AVL_Delete (KTYPE dltKey);
bool AVL_Retrieve (KTYPE key, TYPE& dataOut);
bool AVL_Update (KTYPE key, TYPE dataIn);
void AVL_Traverse (void (*process)(TYPE dataProc)); //in-order
bool AVL_Empty (void);
bool AVL_Full (void);
int AVL_Count (void);
// The following function is used for debugging.
void AVL_Print (void);
} ; // class AvlTree
/* =================== Constructor ===================
Initializes private data.
Pre class is being defined
Post private data initialized
*/
template <class TYPE, class KTYPE>
AvlTree<TYPE, KTYPE> :: AvlTree (void)
{
// Statements
tree = NULL;
count = 0;
} // Constructor
/* ==================== AVL_Insert ====================
This function inserts new data into the tree.
Pre dataIn contains data to be inserted
Post data have been inserted or memory overflow
Return success (true) or overflow (false)
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Insert (TYPE dataIn)
{
// Local Definitions
NODE<TYPE> *newPtr;
bool taller;
// Statements
if (!(newPtr = new NODE<TYPE>))
return false;
newPtr->bal = EH;
newPtr->right = NULL;
newPtr->left = NULL;
newPtr->data = dataIn;
tree = _insert(tree, newPtr, taller);
count++;
return true;
} // Avl_Insert
/* ======================= _insert =======================
This function uses recursion to insert the new data into
a leaf node in the AVL tree.
Pre application has called AVL_Insert, which passes
root and data pointers
Post data have been inserted
Return pointer to [potentially] new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: _insert (NODE<TYPE> *root,
NODE<TYPE> *newPtr,
bool& taller)
{
// Statements
if (!root)
{
root = newPtr;
taller = true;
return root;
} // if NULL tree
if (newPtr->data.key < root->data.key)
{
root->left = _insert(root->left,
newPtr,
taller);
if (taller)
// Left subtree is taller
switch (root->bal)
{
case LH: // Was left high--rotate
root = leftBalance (root, taller);
break;
case EH: // Was balanced--now LH
root->bal = LH;
break;
case RH: // Was right high--now EH
root->bal = EH;
taller = false;
break;
} // switch
} // new < node
else
// new data >= root data
{
root->right = _insert (root->right,
newPtr,
taller);
if (taller)
// Right subtree is taller
switch (root->bal)
{
case LH: // Was left high--now EH
root->bal = EH;
taller = false;
break;
case EH: // Was balanced--now RH
root->bal = RH;
break;
case RH: // Was right high--rotate
root = rightBalance (root, taller);
break;
} // switch
} // else new data >= root data
return root;
} // _insert
/* ===================== leftBalance =====================
The tree is out of balance to the left. This function
rotates the tree to the right.
Pre the tree is left high
Post balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE> *AvlTree<TYPE, KTYPE>
:: leftBalance (NODE<TYPE> *root,
bool& taller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
leftTree = root->left;
switch (leftTree->bal)
{
case LH: // Left High--Rotate Right
root->bal = EH;
leftTree->bal = EH;
// Rotate Right
root = rotateRight (root);
taller = false;
break;
case EH: // This is an error
cout <<"\n\a\aError in leftBalance\n";
exit (100);
case RH: // Right High - Requires double rotation:
// first left, then right
rightTree = leftTree->right;
switch (rightTree->bal)
{
case LH: root->bal = RH;
leftTree->bal = EH;
break;
case EH: root->bal = EH;
leftTree->bal = EH;
break;
case RH: root->bal = EH;
leftTree->bal = LH;
break;
} // switch rightTree
rightTree->bal = EH;
// Rotate Left
root->left = rotateLeft (leftTree);
// Rotate Right
root = rotateRight (root);
taller = false;
} // switch leftTree
return root;
} // leftBalance
/* ===================== rotateLeft ======================
This function exchanges pointers so as to rotate the
tree to the left.
Pre root points to tree to be rotated
Post NODE rotated and new root returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: rotateLeft (NODE<TYPE> *root)
{
// Local Definitions
NODE<TYPE> *tempPtr;
// Statements
tempPtr = root->right;
root->right = tempPtr->left;
tempPtr->left = root;
return tempPtr;
} // rotateLeft
/* ===================== rotateRight =====================
This function exchanges pointers to rotate the tree
to the right.
Pre root points to tree to be rotated
Post NODE rotated and new root returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: rotateRight (NODE<TYPE> *root)
{
// Local Definitions
NODE<TYPE> *tempPtr;
// Statements
tempPtr = root->left;
root->left = tempPtr->right;
tempPtr->right = root;
return tempPtr;
} // rotateRight
/* ==================== rightBalance ===================
The tree is out-of-balance to the right. This function
rotates the tree to the left.
Pre The tree is right high
Post Balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: rightBalance (NODE<TYPE> *root, bool& taller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
rightTree = root->right;
switch (rightTree->bal)
{
case LH: // Left High - Requires double rotation:
// first right, then left
leftTree = rightTree-> left;
// First Rotation - Left
switch (leftTree->bal)
{
case RH: root->bal = LH;
rightTree->bal = EH;
break;
case EH: root->bal = EH;
rightTree->bal = EH;
break;
case LH: root->bal = EH;
rightTree->bal = RH;
break;
} // switch
leftTree->bal = EH;
root->right = rotateRight (rightTree);
root = rotateLeft (root);
taller = false;
break;
case EH: // Deleting from balanced node
root->bal = EH;
taller = false;
break;
case RH: // Right High - Rotate Left
root->bal = EH;
rightTree->bal = EH;
root = rotateLeft (root);
taller = false;
break;
} // switch
return root;
} // rightBalance
/* ====================== AVL_Delete ======================
This function deletes a node from the tree and rebalances
it if necessary.
Pre dltKey contains key to be deleted
Post the node is deleted and its space recycled
-or- an error code is returned
Return success (true) or not found (false)
*/
template <class TYPE, class KTYPE>
bool AvlTree <TYPE, KTYPE> :: AVL_Delete (KTYPE dltKey)
{
// Local Definitions
bool shorter;
bool success;
NODE<TYPE> *newRoot;
// Statements
newRoot = _delete (tree, dltKey, shorter, success);
if (success)
{
tree = newRoot;
count--;
} // if
return success;
} // AVL_Delete
/* ======================== _delete =======================
This function deletes a node from the tree and rebalances
it if necessary.
Pre dltKey contains key of node to be deleted
shorter is Boolean indicating tree is shorter
Post the node is deleted and its space recycled
-or- if key not found, tree is unchanged
Return true if deleted, false if not found
pointer to root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: _delete (NODE<TYPE> *root,
KTYPE dltKey,
bool& shorter,
bool& success)
{
// Local Definitions
NODE<TYPE> *dltPtr;
NODE<TYPE> *exchPtr;
NODE<TYPE> *newRoot;
// Statements
if (!root)
{
shorter = false;
success = false;
return NULL;
} // if -- base case
if (dltKey < root->data.key)
{
root->left = _delete (root->left, dltKey,
shorter, success);
if (shorter)
root = dltRightBalance (root, shorter);
} // if less
else if (dltKey > root->data.key)
{
root->right = _delete (root->right, dltKey,
shorter, success);
if (shorter)
root = dltLeftBalance (root, shorter);
} // if greater
else
// Found equal node
{
dltPtr = root;
if (!root->right)
// Only left subtree
{
newRoot = root->left;
success = true;
shorter = true;
delete (dltPtr);
return newRoot; // base case
} // if true
else
if (!root->left)
// Only right subtree
{
newRoot = root->right;
success = true;
shorter = true;
delete (dltPtr);
return newRoot; // base case
} // if
else
// Delete NODE has two subtrees
{
exchPtr = root->left;
while (exchPtr->right)
exchPtr = exchPtr->right;
root->data = exchPtr->data;
root->left = _delete (root->left,
exchPtr->data.key,
shorter,
success);
if (shorter)
root = dltRightBalance (root, shorter);
} // else
} // equal node
return root;
} // _delete
// ================== dltLeftBalance ==================
/* The tree is out-of-balance to the left (left high)--
rotates the tree to the right.
Pre The tree is left high
Post Balance has been restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: dltLeftBalance (NODE<TYPE> *root,
bool& smaller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
switch (root->bal)
{
case RH: root->bal = EH;
break;
case EH: // Delete occurred on right
root->bal = LH;
smaller = false;
break;
case LH: leftTree = root->left;
switch (leftTree->bal)
{
case LH:
case EH: // Rotate Single Left
if (leftTree->bal == EH)
{
root->bal = LH;
leftTree->bal = RH;
smaller = false;
} // if
else
{
root->bal = EH;
leftTree->bal = EH;
} // else
root = rotateRight (root);
break;
case RH: //Double Rotation
rightTree = leftTree->right;
switch (rightTree->bal)
{
case LH: root->bal = RH;
leftTree->bal = EH;
break;
case EH: root->bal = EH;
leftTree->bal = EH;
break;
case RH: root->bal = EH;
leftTree->bal = LH;
break;
} // switch
rightTree->bal = EH;
root->left = rotateLeft (leftTree);
root = rotateRight (root);
break;
} // switch : leftTree->bal
} // switch : root->bal
return root;
} // dltLeftBalance
/* =================== dltRightBalance ==================
The tree is shorter after a delete on the left.
Adjust the balance factors and rotate the tree
to the left if necessary.
Pre the tree is shorter
Post balance factors adjusted and balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: dltRightBalance (NODE<TYPE> *root,
bool& shorter)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
switch (root->bal)
{
case LH: // Deleted Left--Now balanced
root->bal = EH;
break;
case EH: // Now Right high
root->bal = RH;
shorter = false;
break;
case RH: // Right High - Rotate Left
rightTree = root->right;
if (rightTree->bal == LH)
// Double rotation required
{
leftTree = rightTree->left;
switch (leftTree->bal)
{
case LH: rightTree->bal = RH;
root->bal = EH;
break;
case EH: root->bal = EH;
rightTree->bal = EH;
break;
case RH: root->bal = LH;
rightTree->bal = EH;
break;
} // switch
leftTree->bal = EH;
// Rotate Right then Left
root->right = rotateRight (rightTree);
root = rotateLeft (root);
} // if rightTree->bal == LH
else
{
// Single Rotation Only
switch (rightTree->bal)
{
case LH:
case RH: root->bal = EH;
rightTree->bal = EH;
break;
case EH: root->bal = RH;
rightTree->bal = LH;
shorter = false;
break;
} // switch rightTree->bal
root = rotateLeft (root);
} // else
} // switch root bal
return root;
} // dltRightBalance
/* ==================== AVL_Retrieve ===================
Retrieve node searches the tree for the node containing
the requested key and returns pointer to its data.
Pre dataOut is variable to receive data
Post tree searched and data returned
Return true if found, false if not found
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE>
:: AVL_Retrieve (KTYPE key, TYPE& dataOut)
{
// Local Definitions
NODE<TYPE> *node;
// Statements
if (!tree)
return false;
node = _retrieve (key, tree);
if (node)
{
dataOut = node->data;
return true;
} // if found
else
return false;
} // AVL_Retrieve
/* ===================== _retrieve =====================
Retrieve searches tree for node containing requested
key and returns its data to the calling function.
Pre AVL_Retrieve called: passes key to be located
Post tree searched and data pointer returned
Return address of matching node returned
if not found, NULL returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: _retrieve (KTYPE key,
NODE<TYPE> *root)
{
// Statements
if (root)
{
if (key < root->data.key)
return _retrieve (key, root->left);
else if (key > root->data.key)
return _retrieve (key, root->right);
else
// Found equal key
return (root);
} // if root
else
//Data not in tree
return root;
} // _retrieve
/* ==================== AVL_Update ===================
Update node searches the tree for the node containing
the requested key and updates with new data.
Pre dataIn is new data
Post tree searched and node updated
Return true if found, false if not found
*/
/*
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE>
:: AVL_Update (KTYPE key, TYPE dataIn)
{
// Local Definitions
NODE<TYPE> *node;
// Statements
if (!tree)
return false;
node = _update (key, tree);
if (node)
{
node->data = dataIn;
return true;
} // if found
else
return false;
} // AVL_Retrieve*/
/* ===================== _update =====================
Retrieve searches tree for node containing requested
key and returns its data to the calling function.
Pre AVL_Retrieve called: passes key to be located
Post tree searched and data pointer returned
Return address of matching node returned
if not found, NULL returned
*/
/*template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>
:: _update (KTYPE key,
NODE<TYPE> *root)
{
// Statements
if (root)
{
if (key < root->data.key)
return _update (key, root->left);
else if (key > root->data.key)
return _update (key, root->right);
else
// Found equal key
return (root);
} // if root
else
//Data not in tree
return root;
} // _retrieve*/
/* ==================== AVL_Traverse ====================
Process tree using inorder traversal.
Pre process used to "visit" nodes during traversal
Post all nodes processed in LNR (inorder) sequence
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>
:: AVL_Traverse (void (*process)(TYPE dataProc))
{
// Statements
_traversal (process, tree);
return;
} // end AVL_Traverse
/* ===================== _traversal =====================
Traverse tree using inorder traversal. To process a
node, we use the function passed when traversal is called.
Pre tree has been created (may be null)
Post all nodes processed
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>
:: _traversal (void(*process)(TYPE dataproc),
NODE<TYPE> *root)
{
// Statements
if (root)
{
_traversal (process, root->left);
process (root->data);
_traversal (process, root->right);
} // if
return;
} // _traversal
/* =================== AVL_Empty ==================
Returns true if tree is empty, false if any data.
Pre tree has been created; may be null
Returns true if tree empty, false if any data
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Empty (void)
{
// Statements
return (count == 0);
} // AVL_Empty
/* =================== AVL_Full ===================
If there is no room for another node, returns true.
Pre tree has been created
Returns true if no room, false if room
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Full (void)
{
// Local Definitions
NODE<TYPE> *newPtr;
// Statements
newPtr = new NODE<TYPE>;
if (newPtr)
{
delete newPtr;
return false;
} // if
else
return true;
} // AVL_Full
/* =================== AVL_Count ===================
Returns number of nodes in tree.
Pre tree has been created
Returns tree count
*/
template <class TYPE, class KTYPE>
int AvlTree<TYPE, KTYPE> :: AVL_Count (void)
{
// Statements
return (count);
} // AVL_Count
/* =================== Destructor ===================
Deletes all data in tree and recycles memory.
The nodes are deleted by calling a recursive
function to traverse the tree in inorder sequence.
Pre tree is a pointer to a valid tree
Post all data have been deleted
*/
template <class TYPE, class KTYPE>
AvlTree<TYPE, KTYPE> :: ~AvlTree (void)
{
// Statements
if (tree)
_destroyAVL (tree);
} // Destructor
/* =================== _destroyAVL ===================
Deletes all data in tree and recycles memory.
The nodes are deleted by calling a recursive
function to traverse the tree in postorder sequence.
Pre tree is being destroyed
Post all data have been deleted
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>
:: _destroyAVL (NODE<TYPE> *root)
{
// Statements
if (root)
{
_destroyAVL (root->left);
_destroyAVL (root->right);
delete root;
} // if
return;
} // _destroyAVL
/* ============================= AVL_Print =============================
This function prints the AVL tree by calling a recursive inorder
traversal. NOTE: THIS IS NOT AN APPLICATION ADT FUNCTION. IT IS
USED ONLY FOR DEBUGGING PURPOSES.
To correctly visualize the tree when turned sideways, the actual
traversal is RNL.
Pre Tree must be initialized. Null tree is OK.
Level is node level: root == 0
Post Tree has been printed.
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE> :: AVL_Print (void)
{
/* statements */
_print (tree, 0);
return;
} /* AVL_PRINT */
/* ============================= _print =============================
This function is not a part of the ADT. It is included to verify
that the tree has been properly built by printing out the tree
structure.
*/
/* This function uses recursion to print the tree. At each level, the
level number is printed along with the node contents (an integer).
Pre root is the root of a tree or subtree
level is the level of the tree: tree root is 0
Post Tree has been printed.
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE> :: _print (NODE<TYPE> *root,
int level)
{
/* Local Definitions */
int i;
/* Statements */
if (root)
{
_print ( root->right, level + 1 );
cout << "bal " << setw(3) << root->bal
<< ": Level " << setw(3) << level;
for (i = 0; i <= level; i++ )
cout << "....";
cout << setw(3) << root->data.key;
if (root->bal == LH)
cout << " (LH)\n";
else if (root->bal == RH)
cout << " (RH)\n";
else
cout << " (EH)\n";
_print ( root->left, level + 1 );
} /* if */
} /* AVL_Print */
我花了一些时间来理解您的问题并确定哪些是正确的（AVL 部分）哪些是未经测试的（实际上是 main 代码）。
问题是 newItem 是在 while 循环之外声明的，因此它在迭代之间保留其值，特别是 index 成员。所以对于一个微不足道的修复，只需在循环中声明它：
...
while(file>>word){
DATA newItem;
word = trim(word);
newItem.key = word;
...
这足以使其所有成员默认初始化，这将确保每次迭代都有一个 emply 列表。