AVL 트리 자식 프로젝트의 분할 오류

Question

#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)"세그먼트 화 오류가 발생한다. 도움이 되었습니까?

Answer 1

link2 함수는 NULL 값을 사용하여 temp-> right 또는 temp-> left와 함께 호출된다고 생각합니다. 그런 다음 재귀 수준 1에서 곧바로 segfaults가 발생합니다.

그럴 수도 있습니다.

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; 
} 

Answer 2

이것이 세분화 오류의 원인인지는 모르겠지만 오류이며 관련성이있는 것으로 판단됩니다.

는

while(true) 
{ 
    int a; 
    int b; 
    f >> a; 
    f >> b; 
    root = insert(root,a,b); 
    if (f.eof()) 
    { 
     break; 
    } 
} 

잘못된 할 "input.txt를"읽으려면!

파일의 마지막 줄을 읽었을 때 f.eof()은 true입니다. 그래서 마지막 값인 f >> a;과 f >> b;을주고 다른 값을 읽으려고하면 테스트를하지 않고 두 번째로 insert(root,a,b)을 마지막 값으로 호출합니다.

난 당신에게

int a, b; 
while (f >> a >> b) 
    root = insert(root,a,b); 

이런 식으로

, 당신은 파일의 끝을지나 읽을 때, 당신은 전화 insert() 한 번 더없이 while에서 오류 종료를 얻을 수 같은 것을 제안한다.

또 다른 점 : temp이 NULL 또는 경우 당신이 확인하지 않는 경우가 link2(b,temp->left);와 link2(b,temp->right);으로 반복적으로 호출하기 때문에 당신의 link2() 위험, 그리고 : Tezirg의 솔루션은 당신이 원하는 게 무엇 아니라 자신의 관찰이 올바른지 아닙니다 ... 세분화 오류를 생성하는 훌륭한 방법입니다.

p.s .: 죄송합니다.