Trying to Adapt Binary Search Tree for Two Paramet

问题:

For an assignment, I need to implement several functions of a binary search tree. I've gotten what seems like logical code, however, whenever I try and implement the insert node function, I get a program crash. Here is my code for the insert function:

    void insert (K k, V v)
    {
        TreeNode<K,V> * treeNode = NULL;
        TreeNode<K,V> *temp=NULL;
        TreeNode<K,V> *prev=NULL;
        temp = root;

    while(temp)  //This is the loop that causes a crash, even if I remove the loop.
    {
        prev = temp;
        if (temp->key < treeNode->key)
            temp = temp->right;
        else
            temp = temp->left;
    }

    if (prev==NULL)
        root = treeNode;
    else
    {
        if (prev->key<treeNode->key)
            prev->right = treeNode;  
        else
            prev->left = treeNode;
    }





    }

I'll also include the TreeNode class:

template <class K, class V> class TreeNode
{
public:
TreeNode(K k, V v): key(k), value(v), left(0), right(0) {}

K       key;
V       value;
TreeNode<K,V>   *left;
TreeNode<K,V>   *right;
template <class X, class Y> friend std::ostream & operator 
<< (std::ostream &s,const TreeNode<X,Y> &t);    
};

And when I try and execute the command t.insert("bob", "bobdata"); bam, immediate crash. I've commented out various parameters and discovered that the indicated section is the issue, although beyond that I'm stuck. It happens even if I remove the loop and only execute once, so I'm not getting stuck in infinity. I feel like it may have something to do with the fact that I'm passing strings, but I don't know for sure, and am not knowledgeable enough to fix it if this is the problem. Is there anyone that can tell me what I'm doing wrong here? Thanks so much!

回答1:

Do you assign treeNode anywhere before the loop? It looks like treeNode is NULL so when you dereference it in the conditional it throws an exception:

if (temp->key < treeNode->key)  // This throws an exception if treeNode is not set
                ^^^^^^^^^^^^^

回答2:

Sample implementation below, you need c++11 support for it to compile (because of nullptr, just replace with NULL for c++ compatibility).

#include <iostream>

using namespace std;

template <template<class K, class V> class TreeNode, class K, class V>
std::ostream & operator<< (std::ostream &s,const TreeNode<K,V> &t);

template <class K, class V>
class TreeNode
{
public:
  typedef TreeNode<K,V> SelfType;
  TreeNode(K k, V v): key(k), value(v), left(nullptr), right(nullptr) {}

  K       key;
  V       value;
  SelfType   *left;
  SelfType   *right;
  friend std::ostream & operator<< <>(std::ostream &s,const SelfType &t);    
};

template <class K, class V>
struct Tree {

  typedef TreeNode<K,V> NodeType;

  NodeType *root;

  Tree() : root(nullptr){}

  void insert (K k, V v)
  {
    NodeType * treeNode = new NodeType(k,v);
    NodeType *temp = nullptr;
    NodeType *prev = nullptr;
    temp = root;

    while(temp) {
      prev = temp;
      if (temp->key < treeNode->key)
        temp = temp->right;
      else
        temp = temp->left;
    }

    if (prev==nullptr)
      root = treeNode;
    else {
      if (prev->key<treeNode->key)
        prev->right = treeNode;  
      else
        prev->left = treeNode;
    }
  }
};

int main(){

  Tree<int,int> t;
  t.insert(1,2);

}

I made a test using only int for K and V template params, as it avoid any issue related to copy constructors. You might want to have all your methods take references to K and V instead of pure values.

one issue was encountered:

• NULL initialized treeNode variable in insert

possible problem in your code:

• uninitialized root in the Tree class.