C++ binarysearchtree insert

Question

我正在做一個項目，我必須做一個二叉搜索樹，存儲字符串並考慮到雙打。雖然我已經解決了具體問題，但我不能爲了我的生活而讓這個該死的插入功能起作用。它似乎只存儲根節點，即使實際上似乎將左指針和右指針分配給新節點，它仍然是「子」NULL。但是，當我嘗試輸出它時，只有主父（根）節點存在。我想這些更改不會因爲任何原因而被保存。

這裏的頭文件：

#ifndef BST_H 
#define BST_H 

#include <string> 
#include <vector> 
#include <iostream> 
using namespace std; 

typedef string ItemType; 

class Node 
{ 
public: 
Node(); // constructor 
ItemType data; // contains item 
Node* left; // points to left child 
Node* right;// points to right child 
int dataCount; // keeps track of repeats 
vector<int> lineNumber; // keeps track of line numbers 
}; 

class Tree 
{ 
public: 
Tree(); // constructor 
// ~Tree(); // destructor. not working. 
bool isEmpty(); // tests for empty tree 
Node* find(Node* root, ItemType item); // finds an item 
void insert(Node* root, ItemType item, int lineN, Tree tree); // inserts an item 
void outputTree(Node* root); // lists all items in tree 
void treeStats(Tree tree); // outputs tree stats 
void clearTree(); // erases the tree (restart) 
Node* getRoot(); // returns the root 
void setRoot(Node*& root); 
// void getHeight(Tree *root); // gets height of tree 

private: 
Node* root; // root of tree 
int nodeCount; // number of nodes 
}; 

#endif 

CPP：

#include "BST.h" 

bool setRootQ = true; 

/** Node constructor- creates a node, sets children 
* to NULL and ups the count. */ 
Node::Node() 
{ 
left = right = NULL; 
dataCount = 1; 
} 

/** Tree constructor- creates instance of tree 
* and sets parameters to NULL */ 
Tree::Tree() 
{ 
root = NULL; 
nodeCount = 0; 
} 

/** Destructor- deallocates tree/node data; 
* avoids heap leaks. SOMETHING WRONG. CAUSES SEGFAULT 
Tree::~Tree() 
{ 
if(this->root->left) // if a left child is present 
{ 
    delete this->root->left; //recursive call to destructor ("~Tree(->left)") 
    this->root->left = NULL; 
} 
if(this->root->right) // if a right child is present 
{ 
    delete this->root->right; //recursive call to destructor 
    this->root->right = NULL; 
} 
} */ 

/** Returns true if tree is empty. 
* Otherwise returns false (DUH). */ 
bool Tree::isEmpty() 
{ 
return root == NULL; 
} 

/** Searches tree for item; returns the node if found 
* @param root- tree node. 
* item- data to look for. */ 
Node* Tree::find(Node* root, ItemType item) 
{ 
if(root == NULL) // if empty node 
{ 
    return NULL; 
} 
else if(item == root->data) // if found 
{ 
    return root; 
} 
else if(item < root->data) // if item is less than node 
{ 
    find(root->left, item); 
} 
else if(item > root->data) // if item is more than node 
{ 
    find(root->right, item); 
} 

return NULL; 
} 

/** Adds a new node to the tree. If duplicate, increases count. 
* @param item- data to insert. 
* root- tree node/ */ 
void Tree::insert(Node* root, ItemType item, int lineN, Tree tree) 
{ 
Node* temp = find(tree.getRoot(), item); 
if(temp != NULL) // if item already exists 
{ 
    temp->dataCount += 1; 
    temp->lineNumber.push_back(lineN); 
    return; 
} 

if(root == NULL) // if there is an empty space 
{ 
    root = new Node; // insert new node 
    root->data = item; // w/ data value 
    root->lineNumber.push_back(lineN); 
    nodeCount++; 

    if(setRootQ) 
    { 
    setRoot(root); 
    setRootQ = false; 
    } 
    return; 
} 

if(item < root->data) 
{ 
    insert(root->left, item, lineN, tree); 
} 
if(item > root->data) 
{ 
    insert(root->right, item, lineN, tree); 
} 
} 

/** Outputs tree to console in inorder. 
* @param root- tree root. */ 
void Tree::outputTree(Node* root) 
{ 
if(isEmpty()) // if empty tree 
{ 
    cout << "Error: No items in tree" << endl; // error message 
} 
else 
{ 
    if(root->left != NULL) 
    { 
    outputTree(root->left); 
    } 

    cout << "- " << root->data << " (" << root->dataCount << ") line#s: "; 
    for(unsigned int i = 0; i < root->lineNumber.size(); i++) 
    { 
    cout << root->lineNumber[i] << ", "; 
    } 
    cout << endl; 

    if(root->right != NULL) 
    { 
    outputTree(root->right); 
    } 
} 
} 

/** Displays tree stats including number of nodes, 
* tree height, and more frequent item. 
* @param tree- tree instance. */ 
void Tree::treeStats(Tree tree) 
{ 
cout << "Number of entries: " << nodeCount << endl; 
// unfinished 
} 

/** Clears tree. 
void Tree::clearTree() 
{ 
this->~Tree(); 
} */ 

/** Returns the root of the tree. */ 
Node* Tree::getRoot() 
{ 
return root; 
} 

void Tree::setRoot(Node*& rootS) 
{ 
root = rootS; 
} 

我意識到我的析構函數不能正常工作，但我以後會解決我自己。我一直拉着我的頭髮，試圖找出我失蹤的東西，但無濟於事。如果任何人都可以給我任何幫助，並指向我的解決方案，我將不勝感激。

我認爲它威力有事情做與

void Tree::insert(Node* root, ItemType item, int lineN, Tree tree) 

，而是應該像

void Tree::insert(Node* &root, ItemType item, int lineN, Tree tree) 

但是當我嘗試，我得到一個「不匹配函數」的錯誤。 ：/

Answer 1

你建議你自己（與insert()採取Node *&根）的解決方案將正常工作。您必須對.h文件進行相應的更改，並在.h和.cc文件中更改getRoot()以返回Node *&。

這將工作。但是你的代碼有其他問題。例如，據我所知，setRoot和setRootQ沒有做任何有用的事情。 insert()的第四個參數只會混淆事物，並且不會檢測到重複項。它應該被刪除。要在insert()方法中執行if (item < root->data)之前簡單地執行if (item == root->data)（即，它將更類似於find()）。此外，如果除了你以外的任何人都會使用你的代碼，你不應該要求在getRoot()中傳遞方法find()和insert()。相反，創建私有幫助器方法，如find_helper(Node*, Item)和insert_helper(Node*&,Item)，並讓公共方法使用根節點作爲第一個參數來調用它們。例如： -

Node *find(Item item) { return find_helper(root, item); } 

這也使getRoot()不必要的怪異返回類型，你可以將其改回返回平原Node*，或擺脫訪問乾脆。

Answer 2

似乎有很多指針比較發生，但指針成員變量沒有被初始化。確保指針成員變量正確初始化，以便它們在if語句中正確評估。

變化來自：

class Node 
{ 
public: 
Node(); // constructor 
... 
}; 

to 

class Node 
{ 
public: 
Node() : left(0), right(0) {} 
... 
};