1

所以我在这里的程序会编译但是如果我创建一个类对象它会立即崩溃。我的意思是，在我的 main.cpp 中，如果我创建说“AVLTree obj;” 程序崩溃......如果我把它排除在外，那么一切都很好......任何帮助将不胜感激。

谢谢你。// 下面主要

using namespace std;

int main()
{
    cout << "******************************" << endl;
    cout << "  Self Balancing AVL Tree    " << endl;
    cout << "******************************" << endl;
   /** AVLtree obj;
    obj.insert(100);
    obj.insert(20);
    obj.insert(25);
    obj.insert(200);
    assert isEmpty();
    obj.preOrderPrint(*root);
    obj.inOrderPint(*root);
    obj.postOrderPrint(*root);
    obj.remove(20);

*/
    return 0;
}

标题

#ifndef AVLTREE_H
#define AVLTREE_H

//Moved this outside of the class trying to get things running
struct TreeNode
{
    int key;
    int data;
    TreeNode *parent;
    TreeNode *right;
    TreeNode *left;

    char factor; //byte
};
//-------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------- s
class AVLtree
{
   private:
   protected:
    //neccessary tree nodes
    TreeNode *root;
    TreeNode *tmp, *node;
    TreeNode *holder1, *holder2, *holder3, *newnode;
    int tmpdata;
    bool h;

    int height(TreeNode * pos) const;
    int max(int a, int b) const;

    //Rotate functions broken up individually and used within the
    //insert function. Was having pointer issues when insert was
    //all one function
    TreeNode * singleRotateLeft(TreeNode *holder2);
    TreeNode * singleRotateRight(TreeNode *holder2);

    TreeNode * doubleRotateLeft(TreeNode *holder2);
    TreeNode * doubleRotateRight(TreeNode *holder2);

    TreeNode * _insert(int key, TreeNode * node);
    TreeNode * _remove(int key, TreeNode * node);

    public:
    AVLtree();
    void insert(int key, int data);
    bool isEmpty();
    void remove(int key);
    int retrieve(int key);
    void preOrderPrint(TreeNode *root)const;
    void inOrderPrint(TreeNode *root)const;
    void postOrderPrint(TreeNode *root)const;
    int size;
};
#endif // AVLTREE_H

标题的 CPP

#include "avltree.h"
#include <cstdio>
#include <iostream>

using namespace std;
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
AVLtree::AVLtree()
{
    size = 0;
    //Initialize values
    root = NULL;
    root->left = NULL;
    root->right = NULL;
    root->parent = NULL;
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
int AVLtree::retrieve(int key)
{
    //height of 0 means the tree must be empty
    if(size == 0)
    {
        return NULL;
    }
    tmp = root;
    //While not empty search both sides of tree for key
    while(tmp != NULL)
    {
        if(key < tmp->key)
            tmp = tmp->left;
        else if(key > tmp->key)
            tmp = tmp->right;
        else
            return tmp->data;
    }
    return NULL;
}

//Simple bool determining if the tree is empty via the root
bool AVLtree::isEmpty()
{
    if(root == NULL)
    {
        cout << "The Tree Is Empty!! " << endl;
        return true;
    }
    else
    {
        cout << "The Tree Is NOT Empty" << endl;
        return false;
    }
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------


int AVLtree::height( TreeNode * pos ) const
{
        if( pos == NULL )
            return -1;
        else
            return pos->factor;
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
int AVLtree::max( int a, int b ) const
{
    return a > b ? a : b;
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
TreeNode * AVLtree::singleRotateLeft(TreeNode *holder2)
{
    holder1 = holder2->left;
    holder2->left = holder1->right;
    holder1->right = holder2;

    holder2->factor = max(height(holder2->left), height(holder2->right))+1;
    holder1->factor = max(height(holder1->left), holder2->factor)+1;


    return holder1;  // new root
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
TreeNode * AVLtree::singleRotateRight(TreeNode *holder1)
{
    holder2 = holder1->right;
    holder1->right = holder2->left;
    holder2->left = holder1;

    holder1->factor = max(height(holder1->left), height(holder1->right))+1;
    holder2->factor = max(height(holder2->right), holder1->factor)+1;


    return holder2;  // new root
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
TreeNode * AVLtree::doubleRotateLeft(TreeNode *holder3)
{
    holder3->left = singleRotateRight(holder3->left);

    return singleRotateLeft(holder3);
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
TreeNode * AVLtree::doubleRotateRight(TreeNode *holder1)
{
    holder1->right = singleRotateLeft(holder1->right);

    return singleRotateRight(holder1);
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
void AVLtree::insert(int key, int data)
{
    size++;
    tmpdata = data;
    root =_insert(key,root);
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
TreeNode * AVLtree::_insert(int key, TreeNode * node)
{
    //Empty case, create a new tree
    if (node == NULL)
    {
        node = new TreeNode;
        node->factor = 0;
        node->key = key;
        node->data = tmpdata;
        node->left = NULL;
        node->right = NULL;
//      if(size==1)
//          root=node;

    }
    //Key is less than, move down the left child
    else if(key < node->key)
    {
        node->left= _insert(key,node->left);
        if(height(node->left) - height(node->right) == 2)
        {
            if(key < node->left->key)
                node = singleRotateLeft(node);
            else
                node = doubleRotateLeft(node);
        }
    }
    //Key is greater than move down the right child
    else if(key > node->key)
    {
        node->right= _insert(key,node->right);
        if(height(node->right) - height(node->left) == 2)
        {
            if(key > node->right->key)
                node = singleRotateRight(node);
            else
                node = doubleRotateRight(node);
        }
    }



//  node->factor=-1;
//  if(node->left!=NULL)
//      node->factor=node->left->factor;
//  if(node->right!=NULL)
//      node->factor=max(node->factor, node->right->factor);

    node->factor = max(height(node->left ),height(node->right))+1;
    return node;

}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
void AVLtree::preOrderPrint(TreeNode *node) const
{
    //Empty node returns out
    if(node == NULL) return;
    //print the contents of the node specified
    cout << node->data << " ";
    //Navigate and display left subtree
    preOrderPrint(node->left);
    //Followed by the right subtree
    preOrderPrint(node->right);
}

void AVLtree::inOrderPrint(TreeNode *node) const
{
    if(node == NULL) return;
    inOrderPrint(node->left);
    // Root middle value is displayed in the middle of the printing
    //operation
    cout << node->data << " ";
    inOrderPrint(node->right); // Left childeren last to be printed
}

void AVLtree::postOrderPrint(TreeNode *node) const
{
    if(node == NULL) return; // Empty tree returns

    postOrderPrint(node->left); //Display left side subtree
    postOrderPrint(node->right); // Followed by right side subtree
    cout << node->data << " "; //Finish with root
}

void AVLtree::remove(int key)
{
    root =_remove(key,root);
}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
TreeNode * AVLtree::_remove(int key, TreeNode * node)
{
    //temp bool determining state of removal
    bool done = false;
    //Empty case there is nothing to do, return done immediately
    if (node == NULL)
    {
        h = false;
        done = true;
    }
    else
    //If key data is less than the current node
    if (key < node->key) //delete from left subtree
    {
        newnode =_remove(key,node->left);
        node->left = newnode;
        if(h)
        {
            //Check for height imbalance
            if(height(node->right) - height(node->left) == 2)
            {
                if(height(node->right) > height(node->left))
                    node = singleRotateLeft(node);
                else
                    node = singleRotateRight(node);
            }

            node->factor = max(height(node->left ),height(node->right))+1;


            if (node->factor >= 0)
                {
                   node->factor = root->factor -1;
                   if (node->factor == -1)
                        h = false;
                }
                else if (node->right->factor == -1)
                    singleRotateRight(node);
                else
                    singleRotateLeft(node);

                done = true;
                return node;
        }


    }
    else if (key == node->key) //del node
    {
        if (node->left == NULL || node->right == NULL)  // one or no children
        {
            if (node->left == NULL)
                holder1 = node->right;
            else
                holder1 = node->left;

            delete node;

            h = true; done = true;

            return(holder1);

        }
        else // both of children
        {
            holder2 = node->right;
                while (holder2->left != NULL)
                    holder2 = holder2->left;

                node->key = holder2->key;
                key = node->key;
        }
    }

    if (!done && key >= node->key) // delete from right subtree
    {
            newnode=_remove(key, node->right);
            node->right = newnode;
        if (h)
        {
                if(height(node->right) - height(node->left) == 2)
            {
                if(height(node->right) > height(node->left))
                    node = singleRotateLeft(node);
                else
                    node = singleRotateRight(node);
            }
            node->factor = max(height(node->left ),height(node->right))+1;
                //
/*              if (node->factor <= 0)
                {
                    node->factor=node->factor+1;
                    if (node->factor ==1)
                        h=false;
                }
                else if (node->right->factor==1)
                    singleRotateLeft(node);
                else
                    singleRotateRight(node);*/
                 return node;
            }
    }


}
//-------------------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------------------
4

1 回答 1

8

你不觉得这段代码有问题吗？

root = NULL;
root->left = NULL;
root->right = NULL;
root->parent = NULL;

具体来说，您将根节点初始化为 null，然后尝试将值分配给根的属性。您不能取消引用/为空指针赋值。

于 2012-05-06T21:30:44.073 回答