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