#include "tree.h"
#include <iostream>
#include <fstream>

using namespace std;

int counter;

tree::tree()
{
    root = NULL;
}


int tree::height(node *temp)
{
    int h = 0;
    if (temp != NULL)
    {
        int l_height = height (temp->left);
        int r_height = height (temp->right);
        int max_height = max (l_height, r_height);
        h = max_height + 1;
    }
    return h;
}



int tree::difference(node *temp)
{
    int l_height = height (temp->left);
    int r_height = height (temp->right);
    int sum= l_height - r_height;
    return sum;
}

void tree::READ_DATA()
{
    ifstream f;
    f.open("input.txt", ios::in);
    while(true)
    {
        int a;
        int b;
        f >> a;
        f >> b;
        root = insert(root,a,b);
        if (f.eof())
        {
            break;
        }
    }
    f.close();
}

node *tree::insert(node *root,int x,int b)
{
    if (root == NULL)
    {
        root = new node;
        root->data = x;
        root->left = NULL;
        root->right = NULL;
        root->linked = NULL;
        cout<<root->data<<endl;
        root = link(b,root);
        return root;
    }
    else if(x < root->data)
    {
        root->left = insert(root->left,x,b);
        root = balance(root);
    }
    else if(x > root->data)
    {
        root->right = insert(root->right,x,b);
        root = balance(root);
    }
    else if (x == root->data)
    {
        root = link(b,root);
    }
    return root;
}

void inorder(node *root)
{
    if (root==NULL)
    {
        return;
    }
    inorder(root->left);
    ofstream k;
    k.open("output.txt",ios::app);
    k<<root->data<<" ";
    while (true)
    {
        if (root->linked != NULL)
        {
            root = root->linked->left;
        }
        else
        {
            while (root->linked->right != NULL)
            {
                cout << root->linked->data;
                root = root->linked->right;
            }
            break;
        }
    }
    cout << endl;
    k.close();
    inorder(root->right);
}

void tree::WRITE_INDEX()
{
    inorder(root);
}

//left rotate
node *tree::l_rotation(node *parent)
{
    //cout << "tost"<<endl;
    node *temp;
    temp = parent->left;
    parent->left = temp->right;
    temp->right = parent;
    return temp;
}

//right rotate
node *tree::r_rotation(node *parent)
{
    //cout << "krepa"<<endl;
    node *temp;
    temp = parent->right;
    parent->right = temp->left;
    temp->left = parent;
    return temp;
}

//right-left rotate
node *tree::rl_rotation(node *parent)
{
    //cout << "rl"<<endl;
    node *temp;
    temp = parent->right;
    parent->right = l_rotation(temp);
    return r_rotation(parent);
}

//left-right rotate
node *tree::lr_rotation(node *parent)
{
    //cout << "lr"<<endl;
    node *temp;
    temp = parent->left;
    parent->left = r_rotation(temp);
    return l_rotation(parent);
}

//balancing the tree
node *tree::balance(node *temp)
{
    int diff = difference(temp);
    if (diff > 1)
    {
        if (difference(temp->left)>0)
            temp = l_rotation(temp);
        else
            temp = lr_rotation(temp);
    }
    else if (diff < -1)
    {
        if (difference(temp->right) > 0)
            temp = rl_rotation(temp);
        else
            temp = r_rotation(temp);
    }
    return temp;
}

node *tree::link(int b,node *temp)
{
    if (temp->linked == NULL)
    {
        temp->linked = new node;
        temp->linked->left = NULL;
        temp->linked->right = NULL;
        temp->linked->data = b;
        return temp;
    }
    else
    {
        cout << "tost";
        link2(b,temp->linked);
    }
}

node *tree::link2(int b,node *temp)
{
    cout << b;
    if (b > temp->data)
    {
        link2(b,temp->right);
    }
    else if (b < temp->data)
    {
        link2(b,temp->left);
    }
    else
    {
        temp = new node;
        temp->left = NULL;
        temp->right = NULL;
        temp->data = b;
        return temp;
    }
}


我有应该在AVL树上存储信息的此功能。
在主我叫READ_DATA和WRITE_INDEX
当link2执行时,我在“ if(b> temp-> data)”中遇到分段错误
有什么帮助吗?

最佳答案

我认为用NULL值调用temp-> right或temp-> left来调用link2函数。然后立即在递归级别1进行段错误。

您可以尝试类似的方法吗?

node *tree::link2(int b,node *temp)
{
    cout << b;
    if (temp == NULL)
    {
       temp = new node;
       temp->left = NULL;
       temp->right = NULL;
       temp->data = b;
       return temp;
    }

    if (b > temp->data)
    {
        temp->linked = link2(b,temp->right);
    }
    else if (b < temp->data)
    {
        temp->linked = link2(b,temp->left);
    }
    return temp->linked;
}

07-24 09:45
查看更多