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 に初期化し、ルートのプロパティに値を割り当てようとしています。null ポインターに値を逆参照/代入することはできません。

于 2012-05-06T21:30:44.073 に答える