C++ : Binary Search Tree getHeight() access violation

Question

首先，我已经阅读了C++ Binary Search Tree status access violation error with adding nodes和 Inserting in a binary search tree access violation error但我仍然无法完全实现我的二叉树。我目前在我的 get height 类中遇到访问冲突，但无法弄清楚原因。

template <typename Item, typename Key>
std::size_t BinarySearchTree<Item, Key>::height(TreeNode* node) const{
    if (node == NULL)
        return 0;
    //Debug     
    if(node == NULL)
        std::cout<< "node = Null"<< endl;
    else
        std::cout<< "node != Null"<< endl;

    if(node->left == NULL)
        std::cout<< "left = Null"<< endl;
    else
        std::cout<< "left != Null"<< endl;

    if(node->right == NULL)
        std::cout<< "right = Null"<< endl;
    else
        std::cout<< "right != Null"<< endl;


    //This will go through the list adding 1 at each layer it passes through
    std::size_t left = height(node->left);
    std::size_t right = height(node->right);
    //This will return the branch with the greatest height
    return 1 + std::max(left, right);
}

这就是我向树中添加元素的方式

template <typename Item, typename Key>
void BinarySearchTree<Item, Key>::insert(const Item& value){
    insert(root, value);//start at the root node
}//end insert

template <typename Item, typename Key>
void BinarySearchTree<Item, Key>::insert(TreeNode* node, const Item& value){
    //if item == tree->data then stop the method 
    if (node == NULL){
        //Populate the null leaf node
        TreeNode* target = new TreeNode(value);//create a new node for the inserted parameter
        target->data = value;//the data is stored in the target node
        //increment the size counter
        treeSize++;
    }else if (value < node->data)
        //If the item is less than the current nodes data then insert again
        insert(node->left, value);
    else
        //If the item is greater than the current nodes data then insert again
        insert(node->right, value);     
}

我不知道我怎么会遇到访问冲突，因为我在调用左节点或右节点之前检查空指针。任何见解将不胜感激。

编辑:我还应该注意到节点的左右叶子被初始化为 NULL。

完整代码:

#pragma once
#include <cstdlib>

namespace MySpace{

template <typename Item, typename Key = Item>
class BinarySearchTree{
    // private node class (only visible inside the BinarySearchTree class)
    struct TreeNode {
        TreeNode(const Item& data = Item()) :
            data(data), left(NULL), right(NULL) { }
        ~TreeNode(){
            delete left; delete right;
            left = NULL; right = NULL;
        }
        Item data;//This is the object
        TreeNode* left;   // left child
        TreeNode* right;  // right child
    };

public:
    //==========================Constructor=============================
    // creates an empty tree
    BinarySearchTree(){root = NULL; treeSize = 0;}
    // Postcondition: A copy of the binary search tree
    BinarySearchTree(BinarySearchTree<Item, Key>& source);

    //==========================Destructor================================      
    ~BinarySearchTree(){delete root; root = NULL;}//will delete all branches recursively
    //=========================Public Methods============================
    // Postcondition: the current tree has been replaced with a copy of
    // the source binary serch tree. The return value is the calling object
    BinarySearchTree<Item, Key>& operator =(BinarySearchTree<Item, Key>& source);
    // returns the number of nodes in the tree
    std::size_t size() const{return treeSize;}
    // returns the height of the tree
    std::size_t height() const;
    // returns the minimum value in the tree
    const Item& min() const;
    // returns the maximum value in the tree
    const Item& max() const;
    // inserts a copy of the given value into the tree, unless one already exists
    void insert(const Item& value);
    // removes an entry with the given key, if present in the tree
    bool remove(const Key& key);
    // returns a pointer to an entry with the given key (if it exists), or NULL
    Item* search(const Key& key) const;
    // if an entry with the key exists, applies the function
    template <typename Function>
    bool apply(const Key& key, Function f);
    // applies a function to each value in the tree, via preorder traversal
    template <typename Function>
    void preorder(Function f);
    // applies a function to each value in the tree, via inorder traversal
    template <typename Function>
    void inorder(Function f);
    // applies a function to each value in the tree, via postorder traversal
    template <typename Function>
    void postorder(Function f);
    //Copy the nodes of a BST
    TreeNode* copy(const TreeNode *node){           
        //If the passed node is Null then return null
        if (node == NULL)
            return NULL;
        Item nodeData = node->data;
        TreeNode* copyNode = new TreeNode(nodeData);//create a new node with the data from the last one 
        copyNode->data = node->data;
        copyNode->left = copy(node->left);
        copyNode->right = copy(node->right);
        return copyNode;
    }

    //=========================Accessor============================
    TreeNode* getRoot(){return root;}

private:
    //This is the root node for the binary tree
    TreeNode* root;
    std::size_t treeSize;

    //Checks the size of the BST to see if it is empty or not
    bool isEmpty() const{return(treeSize == 0)?true:false;}

    //These methods are used for recursion
    Item* search(TreeNode* node, const Key& key) const;
    void insert(TreeNode* node, const Item& value);
    bool remove(TreeNode* node, const Key& key);
    std::size_t height(TreeNode* node) const;
    const Item& min(TreeNode* node) const;
    const Item& max(TreeNode* node) const;
    template <typename Function>
    void preorder(TreeNode* node, Function f);
    template <typename Function>
    void inorder(TreeNode* node, Function f);
    template <typename Function>
    void postorder(TreeNode* node, Function f);

};

//------------------------This is where the methods will get implemented------------------------
//Copy constructor
template <typename Item, typename Key>
BinarySearchTree<Item, Key>::BinarySearchTree(BinarySearchTree<Item, Key>& source){
    treeSize = source.size();
    TreeNode* tempNode = source.getRoot();
    //copy(tempNode);
}

template <typename Item, typename Key>
BinarySearchTree<Item, Key>& BinarySearchTree<Item, Key>::operator =(BinarySearchTree<Item, Key>& source){
    if(&source == this)
        return *this;
    treeSize = source.size();
    TreeNode* tempNode = source.getRoot();
    //copy(tempNode);
    return *this;
}

template <typename Item, typename Key>
std::size_t BinarySearchTree<Item, Key>::height() const{
    if(root == NULL)
        std::cout<< "AAAAAAHHHHHHH!"<< endl;
    else
        std::cout<< "okay!"<< endl;
    return height(root);//start at the root
}

template <typename Item, typename Key>
std::size_t BinarySearchTree<Item, Key>::height(TreeNode* node) const{
    if (node == NULL)
        return 0;
    //Debug     
    if(node == NULL)
        std::cout<< "node = Null"<< endl;
    else
        std::cout<< "node != Null"<< endl;

    if(node->left == NULL)
        std::cout<< "left = Null"<< endl;
    else
        std::cout<< "left != Null"<< endl;

    if(node->right == NULL)
        std::cout<< "right = Null"<< endl;
    else
        std::cout<< "right != Null"<< endl;


    //This will go through the list adding 1 at each layer it passes through
    std::size_t left = height(node->left);
    std::size_t right = height(node->right);
    //This will return the branch with the greatest height
    return 1 + std::max(left, right);

}

template <typename Item, typename Key>
const Item& BinarySearchTree<Item, Key>::min() const{
    return min(root);//start at the root
}

template <typename Item, typename Key>
const Item& BinarySearchTree<Item, Key>::min(TreeNode* node) const{
    if(!isEmpty()){
        //goes recursively until the left most leaf is found
        if(node->left == NULL)
            return node->data;
        else
            min(node->left);
    }

    return Item();
}

template <typename Item, typename Key>
const Item& BinarySearchTree<Item, Key>::max() const{
    return max(root);//start at the root
}

template <typename Item, typename Key>
const Item& BinarySearchTree<Item, Key>::max(TreeNode* node) const{
    if(!isEmpty()){
        //goes recursively until the right most leaf is found
        if(node->right == NULL)
            return node->data;
        else
            max(node->right);
    }
    return Item();
}

template <typename Item, typename Key>
void BinarySearchTree<Item, Key>::insert(const Item& value){
   insert(root, value);//start at the root node
}//end insert

template <typename Item, typename Key>
void BinarySearchTree<Item, Key>::insert(TreeNode* node, const Item& value){
    //if item == tree->data then stop the method 
    if (node == NULL){
        //Populate the null leaf node
        TreeNode* target = new TreeNode(value);//create a new node for the inserted parameter
        target->data = value;//the data is stored in the target node
        node = target;
        //increment the size counter
        treeSize++;
    }else if (value < node->data)
        //If the item is less than the current nodes data then insert again
        insert(node->left, value);
    else
        //If the item is greater than the current nodes data then insert again
        insert(node->right, value);     
}

template <typename Item, typename Key>
bool BinarySearchTree<Item, Key>::remove(const Key& key){
    return remove(root, key);//default is to return false
}

template <typename Item, typename Key>
bool BinarySearchTree<Item, Key>::remove(TreeNode* node, const Key& key){
    //If the tree is not empty
    if(!isEmpty()){
        if (key < node->data)
            //If the key is less than the Item than go to the left branch
            remove(node->left, key);
        else if (key > node->data)
            //If the key is less than the Item than go to the right branch
            remove(node->right, key);
        else{
            //If the key is equal to the Item then...
            //decrement size
            treeSize--;

            // There are several cases I have to deal with
            // 1) a leaf node - easy
            // 2) a node with 1 child - left or right
            // 3) a node with 2 children - left and right

            if(node->left == NULL && node->right == NULL){
                delete node;//If the node was a leaf then just delete it
                node = NULL;
            }else if(node->left != NULL || node->right != NULL){
                TreeNode* tempNode = node;
                //If either branch is empty, then delete the node
                delete node;
                //now set the node to the non empty branch
                node = (tempNode->left != NULL)?tempNode->left:tempNode->right;
            }else{
                //if there are two branches then make the right branch the node
                TreeNode* switchNode = node->right;

                //gets the left most node on the right branch
                while(switchNode->left != NULL){
                       switchNode = switchNode->left;
                }
                //This puts the data into the passed node, but does not delete it!
                node->data = switchNode->data;
                //I don't know how many children the switch node has(Either 0 or 1), so I have to run the 
                //method again on the switch node to remove it properly
                remove(switchNode, switchNode->data);
            }           
            return true;//return true since the item was deleted
        }//end if
    }//end if not empty
    return false;
}

template <typename Item, typename Key>
Item* BinarySearchTree<Item, Key>::search(const Key& key) const{
    return search(root, key);
}

template <typename Item, typename Key>
Item* BinarySearchTree<Item, Key>::search(TreeNode* node, const Key& key) const{
    if (node == NULL){
        //If there is no node at this location return null
        return NULL;
    }else if (key < node->data)
        //If the key is less than the Item than go to the left branch
        search(node->left, key);
    else if (key > node->data)
        //If the key is less than the Item than go to the right branch
        search(node->right, key);
    else
        //If the key is equal to the Item than return the item
        return &node->data;
}

template <typename Item, typename Key>
template <typename Function>
bool BinarySearchTree<Item, Key>::apply(const Key& key, Function f){
    Item* data = search(key);
    if(data != NULL){
        f(*data);//do the function on the selected item
        return true;
    }
    return false;
}

template <typename Item, typename Key>
template <typename Function>
void BinarySearchTree<Item, Key>::preorder(Function f){
    preorder(root, f);//start at the root
}

template <typename Item, typename Key = Item>
template <typename Function>
void BinarySearchTree<Item, Key>::preorder(TreeNode* node, Function f){
    //If the node is not null then do the method
    if(node != NULL){
        //Then apply the function to the data
        f(node->data);
        //Do the branches last
        if(node->left) preorder(node->left, f);
        if(node->right) preorder(node->right, f);
    }else
        return;
}

template <typename Item, typename Key>
template <typename Function>
void BinarySearchTree<Item, Key>::inorder(Function f){
    inorder(root, f);//start at the root
}

template <typename Item, typename Key = Item>
template <typename Function>
void BinarySearchTree<Item, Key>::inorder(TreeNode* node, Function f){
    //If the node is not null then do the method
    if(node != NULL){
        //Do the function in between the two branches
        if(node->left) inorder(node->left, f);
        //Then apply the function to the data
        f(node->data);
        if(node->right) inorder(node->right, f);
    }else
        return;
}

template <typename Item, typename Key = Item>
template <typename Function>
void BinarySearchTree<Item, Key>::postorder(Function f){
    postorder(root, f);//start at the root
}

template <typename Item, typename Key = Item>
template <typename Function>
void BinarySearchTree<Item, Key>::postorder(TreeNode* node, Function f){
    //If the node is not null then do the method
    if(node != NULL){
        //Do the function in between the two branches
        if(node->left) postorder(node->left, f);
        if(node->right) postorder(node->right, f);
        //Then apply the function to the data
        f(node->data);
    }else
        return;
}

}

这里是main函数所在的地方

#include "BinarySearchTree.h" 
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <utility>
#include <cmath>
#include <sstream>
using namespace std;
using namespace MySpace;
using namespace rel_ops;



#define TreeType BinarySearchTree

#define BALANCED false

// #define ITERATORS


// returns the ideal height of a tree with n nodes
size_t balanced_height(size_t n) { 
    return (n < 2) ? n : 1 + (size_t) (log10((double) n) / log10(2.0));
}


// a simple compound data type
struct Person {
    string name;
    int age;

    bool operator <(const Person& other) const { return (name < other.name); }
    bool operator ==(const Person& other) const { return (name == other.name); }

    operator string() const { return name; }
};


// operators for comparing a string to a Person (a Key to an Item)
bool operator <(const string& L, const Person& R) { return L < R.name; }
bool operator >(const string& L, const Person& R) { return L > R.name; }
bool operator ==(const string& L, const Person& R) { return L == R.name; }
bool operator !=(const string& L, const Person& R) { return L != R.name; }
bool operator <=(const string& L, const Person& R) { return L <= R.name; }
bool operator >=(const string& L, const Person& R) { return L >= R.name; }


// output operator for Person class
ostream& operator <<(ostream& out, const Person& p) { return out << p.name; }


template <typename Item, typename Key>
void test_tree(TreeType<Item, Key>, const vector<Item>&);


int main() {
    const size_t NUM_VALUES = 15;

    // create vectors containing the values to use
    vector<int> nums(NUM_VALUES);
    vector<Person> people(NUM_VALUES);

    // populate them with values
    for (size_t i = 0; i < NUM_VALUES; i++) {
        nums[i] = people[i].age = i;
        people[i].name = char('A' + i);
    }

    // create the empty trees
    TreeType<int> t1;
    TreeType<Person, string> t2;

    // testing when the data type is also the key
    cout << "Testing case when Item type is also the Key type... " << endl;
    test_tree(t1, nums);
    cout << "Passed!\n\n";

    // testing when the Item type has a different Key type
    cout << "Testing case with different Item and Key types... " << endl;
    test_tree(t2, people);
    cout << "Passed!\n\n";

    // all tests passed
    cout << "Nicely done!" << endl;
    return EXIT_SUCCESS;
}


// simple stringstreams for testing purposes
stringstream s1, s2;


// outputs a value to the stringstream for testing
template <typename Item>
void output_value(Item& data) {
    s1 << data;
}


// inserts the contents of the vector in way that yields a balanced tree
template <typename Item, typename Key>
void balanced_insert(TreeType<Item, Key>& tree, const vector<Item> values, int beg, int end) {
    if (beg > end) return;

    size_t mid = ceil((beg + end) / 2.0);
    tree.insert(values[mid]);

    if (beg != end) {
        balanced_insert(tree, values, beg, mid - 1);
        balanced_insert(tree, values, mid + 1, end);
    }
}


// fills ss with data in preorder fashion
template <typename Item>
void vector_preorder(stringstream& ss, const vector<Item> values, int beg, int end) {
    if (beg > end) return;

    size_t mid = ceil((beg + end) / 2.0);
    ss << values[mid];

    if (beg != end) {
        vector_preorder(ss, values, beg, mid - 1);
        vector_preorder(ss, values, mid + 1, end);
    }
}


// fills ss with data in inorder fashion
template <typename Item>
void vector_inorder(stringstream& ss, const vector<Item> values, int beg, int end) {
    if (beg > end) return;

    size_t mid = ceil((beg + end) / 2.0);

    if (beg != end) vector_inorder(ss, values, beg, mid - 1);

    ss << values[mid];

    if (beg != end) vector_inorder(ss, values, mid + 1, end);
}


// fills ss with data in postorder fashion
template <typename Item>
void vector_postorder(stringstream& ss, const vector<Item> values, int beg, int end) {
    if (beg > end) return;

    size_t mid = ceil((beg + end) / 2.0);

    if (beg != end) {
        vector_postorder(ss, values, beg, mid - 1);
        vector_postorder(ss, values, mid + 1, end);
    }

    ss << values[mid];
}


template <typename Item, typename Key>
void test_tree(TreeType<Item, Key> tree, const vector<Item>& values) {
    // tree should initially be empty
    assert(tree.size() == 0);
    assert(tree.height() == 0);

    std::cout<<"DIM TEST 1 COMPLETE!"<<endl;

    // insert a single value (becomes root of tree)
    tree.insert(values[0]);

    // ensure that the tree has a size and height of 1...
    assert(tree.size() == 1);
    assert(tree.height() == 1);

    std::cout<<"DIM TEST 2 COMPLETE!"<<endl;

    // ensure the value appears in the tree...
    assert(tree.search(values[0]));

    // and that your function correctly returns a pointer to the value
    assert(*tree.search(values[0]) == values[0]);

    std::cout<<"SEARCH 1 COMPLETE!"<<endl;

    // testing removing the root node (resulting in an empty tree)
    assert(tree.remove(values[0]));

    std::cout<<"REMOVE 1 COMPLETE!"<<endl;

    // ensure that the tree is once again empty...
    assert(tree.size() == 0);
    assert(tree.height() == 0);

    std::cout<<"DIM TEST 3 COMPLETE!"<<endl;

    // ensure that removing a non-existent value doesn't fail (should return false)
    assert(!tree.remove(values[0]));

    std::cout<<"REMOVE 2 COMPLETE!"<<endl;

    // ensure that the value no longer appears in the tree...
    assert(!tree.search(values[0]));

    std::cout<<"SEARCH 2 COMPLETE!"<<endl;

    // insert all the values this time in sorted order...
    for (size_t i = 0; i < values.size(); i++) {
        tree.insert(values[i]);

        // ensure the value appears in the tree...
        assert(tree.search(values[i]));

        // ensure that the size is correct...
        assert(tree.size() == i + 1);

        // height of tree depends on whether you're balancing as you go or not
        assert(tree.height() == (BALANCED ? balanced_height(tree.size()) : tree.size()));
    }

    std::cout<<"INSERT 1 COMPLETE!"<<endl;

    // ensure min and max work
    assert(tree.min() == *min_element(values.begin(), values.end()));
    assert(tree.max() == *max_element(values.begin(), values.end()));

    // remove all the values, starting with the root
    for (size_t i = 0; i < values.size(); i++) {
        // remove the value
        tree.remove(values[i]);

        // ensure the value no longer appears in the tree...
        assert(!tree.search(values[i]));

        // ensure that the size is correct...
        assert(tree.size() == values.size() - i - 1);

        // height of tree depends on whether you're balancing as you go or not
        assert(tree.height() == (BALANCED ? balanced_height(tree.size()) : tree.size()));
    }

    std::cout<<"REMOVE 3 COMPLETE!"<<endl;

    // insert all the values this time in balanced order...
    balanced_insert(tree, values, 0, values.size() - 1);

    std::cout<<"INSERT 2 COMPLETE!"<<endl;

    // make sure the size is still right...
    assert(tree.size() == values.size());

    // height of tree should be ceil(log2(n))
    assert(tree.height() == balanced_height(tree.size()));

    std::cout<<"DIM TEST 4 COMPLETE!"<<endl;

    // can't insert duplicate values (size & height shouldn't increase)
    // operation should simply fail silently (do nothing)
    tree.insert(values[0]);
    assert(tree.size() == values.size());
    assert(tree.height() == balanced_height(values.size()));

    // ensure min and max (still) work
    assert(tree.min() == *min_element(values.begin(), values.end()));
    assert(tree.max() == *max_element(values.begin(), values.end()));

    std::cout<<"MIN MAX 1 COMPLETE!"<<endl;

    // testing copy constructor
    TreeType<Item, Key>* copy = new TreeType<Item, Key>(tree);
    assert(copy->size() == tree.size());
    assert(copy->height() == tree.height());

    std::cout<<"DIM TEST 5 COMPLETE!"<<endl;

    // original should remain unchanged after copy modification
    copy->remove(values[1]);
    copy->remove(values[values.size() - 2]);
    assert(copy->size() == tree.size() - 2);
    assert(tree.search(values[1]));
    assert(tree.search(values[values.size() - 2]));

    std::cout<<"REMOVE 4 COMPLETE!"<<endl;

    // testing destructor
    delete copy;

    // the original should remain unchanged
    for (size_t i = 0; i < values.size(); i++) {
        assert(tree.search(values[i]));
    }

    // testing assignment operator
    copy = new TreeType<Item, Key>;
    *copy = tree;

    // original should remain unchanged after copy modification
    copy->remove(values[1]);
    copy->remove(values[values.size() - 2]);
    assert(copy->size() == tree.size() - 2);
    assert(tree.search(values[1]));
    assert(tree.search(values[values.size() - 2]));

    // testing destructor
    delete copy;

    // the original should remain unchanged
    for (size_t i = 0; i < values.size(); i++) {
        assert(tree.search(values[i]));
    }

    // testing preorder traversal
    s1.str(""); s2.str("");
    vector_preorder(s2, values, 0, values.size() - 1);
    tree.preorder(output_value<Item>);
    assert(s1.str() == s2.str());

    // testing inorder traversal
    s1.str(""); s2.str("");
    vector_inorder(s2, values, 0, values.size() - 1);
    tree.inorder(output_value<Item>);
    assert(s1.str() == s2.str());

    // testing postorder traversal
    s1.str(""); s2.str("");
    vector_postorder(s2, values, 0, values.size() - 1);
    tree.postorder(output_value<Item>);
    assert(s1.str() == s2.str());

    // testing apply
    s1.str(""); s2.str("");
    s2 << values[0];
    tree.apply(values[0], output_value<Item>);
    assert(s1.str() == s2.str());

#ifdef ITERATORS
    // testing iterators (smallest-to-largest order)
    typename TreeType<Item, Key>::iterator t = tree.begin();
    typename vector<Item>::const_iterator v = values.begin();

    while (t != tree.end()) {
        assert(*t == *v);
        ++t;
        ++v;
    }

    assert(v == values.end());
#endif
}

Answer 1

分配和初始化后需要将节点设置为目标。