添加节点时C ++二进制搜索树状态访问冲突错误 [英] C++ Binary Search Tree status access violation error with adding nodes

问题描述

我正在开发一个可用于二叉树的程序。将新节点添加到树中时出现错误。我可以添加一个节点，但是在添加另一个节点后，会收到STATUS_ACCESS_VIOLATION错误。我认为错误可能与处理搜索功能的功能参数有关。

I'm working on a program that works with a binary tree. I'm getting an error with adding new nodes into the tree. I can add one node, but after adding another, I get a STATUS_ACCESS_VIOLATION error. I think the error could be with the function arguments dealing with the search function. Please help me if you can.

这是我写的.h文件：

#ifndef P4_H
#define P4_H
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cctype>
#include <string>
using namespace std;

struct TreeNode //ListNode structure with components
{
   int acctNum;
   TreeNode *left;
   TreeNode *right;
};

typedef TreeNode* nodePtr;  //defines a pointer to a treenode struct

class Tree
{
   private:
            nodePtr root;
            int numElements;

   public:

   Tree()
   { root = NULL; numElements = 0; }

   bool treeEmpty()
   { return (numElements == 0); }

   void addNode()
   {
      int key;
      cout << "Enter account number to add: ";
      cin >> key;
      cout << endl << endl;

      nodePtr location = NULL, parent = NULL, p = NULL;

      bool found = searchTree(key, &location, &parent);

      cout << found << " " << location << " " << parent << endl << endl;

      if (found)
      {
         cout << "Error! Account number: " << key << " already exists within"
         << " the tree." << endl << endl;
      }
      else
      {
         if (parent == NULL)
         {
            root = new TreeNode;
            root->acctNum = key;
         }
         else
         {
            if (parent->acctNum > key)
            {
               parent->left = new TreeNode;
               p = parent->left;
               p->acctNum = key;
            }
            else
            {
               parent->right = new TreeNode;
               p = parent->right;
               p->acctNum = key;
            }
         }
      }
   }

   bool searchTree(int key, nodePtr *location, nodePtr *parent)
   {
      bool found = false;
      nodePtr p = root;
      *location = root;
      parent = NULL;

      while (p != NULL && !found)
      {
         *location = p;
         if (key == p->acctNum)
            found = true;
         else if (key < p->acctNum)
         {
            *parent = p;
            p = p->left;
         }
         else if (key > p->acctNum)
         {
            *parent = p;
            p = p->right;
         }
      }
      return found;
   }

   void deleteNode()
   {
      int key;
      nodePtr location = NULL, parent = NULL;

      cout << "Enter account number to delete: ";
      cin >> key;
      cout << endl << endl;

      bool found = searchTree(key, &location, &parent);

      if (!found)
      {
         cout << "Error! Account number: " << key << " was not found."
         << endl << endl;
      }
      else if (location->left != NULL && location->right != NULL)
      {  //delete node with left and right subtrees
         nodePtr leftmost = location->right, leftmostParent = NULL;

         while (leftmost->left != NULL)
         {
            leftmostParent = leftmost;
            leftmost = leftmost->left;
         }

         leftmost->left = location->left;
         leftmost->right = location->right;
         leftmostParent->left = NULL;

         if (parent->acctNum > location->acctNum)
            parent->left = leftmost;
         else
            parent->right = leftmost;

         delete location;
         location = NULL;
      }
      else if (location->left != NULL && location->right == NULL)
      {  //delete node with only a left subtree
         if (parent->acctNum > location->acctNum)
            parent->left = location->left;
         else
            parent->right = location->left;

         delete location;
         location = NULL;
      }
      else if (location->left == NULL && location->right != NULL)
      {  //delete node with only a right subtree
         nodePtr leftmost = location->right, leftmostParent = NULL;

         while (leftmost->left != NULL)
         {
            leftmostParent = leftmost;
            leftmost = leftmost->left;
         }

         leftmost->right = location->right;
         leftmostParent->left = NULL;

         if (parent->acctNum > location->acctNum)
            parent->left = leftmost;
         else
            parent->right = leftmost;

         delete location;
         location = NULL;
      }
      else
      {  //delete a leaf node
         if (location->acctNum > parent->acctNum)
            parent->right = NULL;
         else
            parent->left = NULL;

         delete location;
         location = NULL;
      }
   }

   void displayAscend(nodePtr p, int count)
   {
      if (p->left != NULL)
         displayAscend(p->left, count);
      cout << count << ". " << p->acctNum << endl;
      count ++;
      if (p->right != NULL)
         displayAscend(p->right, count);
   }

   void displayDescend(nodePtr p, int count)
   {
      if (p->right != NULL)
         displayAscend(p->right, count);
      cout << count << ". " << p->acctNum << endl;
      count ++;
      if (p->left != NULL)
         displayAscend(p->left, count);
   }

   void readFile()
   {
      char filename[50];

      cout << "Enter name of file to open: ";
      cin.getline(filename,51);
      cout << endl << endl;

      ifstream inFile;
      inFile.open(filename);

      while (!inFile)
      {
         cout << "Error opening file! Please try again." << endl << endl;
         cout << "Enter name of file: ";
         cin.getline(filename,51);
         cout << endl << endl;
      }

      int num;

      while (!inFile.eof())
      {
         inFile >> num;

         nodePtr location = NULL, parent = NULL, p = NULL;

         bool found = searchTree(num, &location, &parent);

         if (found)
         {
            cout << "Error! Account number: " << num << " already exists"
            << " within the tree." << endl << endl;
         }
         else
         {
            if (parent == NULL)
            {
               root = new TreeNode;
               root->acctNum = num;
            }
            else
            {
               if (parent->acctNum > num)
               {
                  parent->left = new TreeNode;
                  p = parent->left;
                  p->acctNum = num;
               }
               else
               {
                  parent->right = new TreeNode;
                  p = parent->right;
                  p->acctNum = num;
               }
            }
         }
      }



   }
};
#endif

推荐答案

在searchTree中，您设置了父在循环之前为NULL，然后在循环中取消引用。

In searchTree, you set parent to NULL before the loop, then dereference it in the loop.

这篇关于添加节点时C ++二进制搜索树状态访问冲突错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！