Ошибка сегментации (ядро сброшено) - резьбовое дерево двоичного поиска

Question

Я получаю следующую ошибку: Ошибка сегментации (ядро сброшено).Я обнаружил строку кода, которая вызывает проблему (помечена комментарием внутри программы).Пожалуйста, скажите мне, почему происходит эта ошибка и как ее исправить.

Я попытался запустить мой код (на бумаге) и не вижу логических ошибок (насколько я понимаю).
Я только недавно вошел в кодирование и стекопоток, пожалуйста, объясните мне, как я могу улучшить свой вопрос, а также мой код.Спасибо!

class tree
{
struct node    // Creates a node for a tree
{
    int data;
    bool rbit,lbit;  // rbit/lbit= defines if right/left child of root is present or not
    node *left,*right;
};
public:
    node *head,*root;
    tree() // constructor initializes root and head  
    {
        root=NULL;
        head=createnode(10000);
    }
    node *createnode(int value)  
    {// Allocates memory for a node then initializes node with given value and returns that node
        node *temp=new node ;
        temp->data=value;
        temp->lbit=0;
        temp->rbit=0;
        temp->left=NULL;
        temp->right=NULL;
        return temp;
    }
    void insert(node *temp,int value) // Creates binary search tree node by node
    {
        if(root==NULL)  // Checking if tree is empty
        {
            root=createnode(value);  //Root now points to new memory location 
            head->left=root;
            head->lbit=1;
            root->left=head;//this line gives the segmentation fault (what i thought before correction) 
        }   

    }
    void inorder(node *root) // Inorder traversal of tree (this function is logically incorrect) 
    {
        if(root==NULL)
            return;
        inorder(root->left);
        cout<<root->data<<"\t";
        inorder(root->right);
    }
    void getdata()//Accepts data , creates a node through insert() , displays result through inorder()
    {
        int data;
        cout<<"Enter data"<<endl;
        cin>>data;  
        insert(root,data);
        inorder(root);
    }
 /*void inorder(node *root) // Working inorder code
{
    if(root->lbit==1)
    inorder(root->left);
    cout<<root->data<<"\t";
    if(root->rbit==1)
    inorder(root->right);
}*/
};
int main()
{

    tree t; // Tree Object 
    t.getdata();  // Calling getdata
    return 0;
}

Answer 1

Я думаю, что раздел комментариев в значительной степени отражает недопонимание.Легко поверить, что вы испытываете сбой ON этой конкретной линии.

На самом деле это не так.Вместо этого вы создали в своем дереве цикл, который приводит к бесконечной рекурсии с помощью функции inorder.Это приводит к переполнению стека, которое приводит к segfaults - это было бы очень легко обнаружить, если бы вы только что запустили свою программу с подключенным отладчиком (таким как gdb).

temp = createnode(value);
if(root == NULL)
{
    root = temp;
    head->left = root;
    head->lbit = 1;
    temp->left = head;
}   

Посмотрите на цикл, который вы только чтосоздал:

head->left points to root
root->left == temp->left, which points to head

Теперь будет проходить обход:

root
  head
    root
      head
        root
          head
            ...

Так как он никогда не достигает конца левой ветви, функция никогда ничего не выводит до переполнения стека исбой.

Так что нет, ваш код не является логически правильным.В этом есть фундаментальный недостаток дизайна.Вам нужно переосмыслить, что вы храните в своем дереве и почему.

Answer 2

Из кода

    root=temp;  //Root now points to temp
    head->left=root;
    head->lbit=1;
    temp->left=head;// this line gives the segmentation fault 

root не указывает на темп.temp (указатель) присваивается root (указатель).указатель на левый заголовок - это корень, а левый темп - это голова (это означает, что левый корень - это голова).поэтому в функции "inorder"

    void inorder(node *root) // Inorder traversal of tree
    {
        if(root==NULL)             <<<<<<
            return;
        inorder(root->left);
        cout<<root->data<<"\t";
        inorder(root->right);
    }

аргумент узла * root (слева) никогда не равен NULL, а функция никогда не возвращается.

Answer 3

Недостаточно информации о том, как именно это должно работать (например, node.lbit).

Функция insert() вопроса не будет работать.Он передает значение, которое немедленно перезаписывается (среди других вопросов).Там нет объяснения того, для чего tree.head, поэтому он игнорируется.Поля node.lbit и node.rbit выглядят как лишние флаги node.left != NULL (аналогично справа).Они тоже опущены.insert() также не создает дерево должным образом.

void insert(int value) // Insert a value into the tree (at branch)
{
    // Create a new node to insert
    struct node *temp = createnode(value);

    if (root == NULL)  // Checking if tree is empty
    {
        root = temp;  //Root now points to temp
    }  
    else 
    {
        insertAtBranch(root, temp);
    }
}

// recursively find the leaf-node at which to insert the new node
void insertAtBranch(node *branch, node *new_node)
{
    // to create a BST, less-than go left
    if (new_node->value <= branch->value)
    {
        if (branch->left == NULL)
            branch->left = new_node;  // There's no left-branch, so it's the node
        else
            insertAtBranch(branch->left, new_node);  // go deeper to find insertion point
    }
    else // greater-than go right
    {
        if (branch->right == NULL)
            branch->right = new_node;
        else
            insertAtBranch(branch->right, new_node);
    }
}         

Представьте, как работает двоичное дерево.Новые узлы вставляются только по краям.Итак, вы смотрите на данный узел и решаете, является ли этот новый узел меньше или больше, чем тот, на который вы смотрите (конечно, если дерево не пусто).

Скажите, что new-node.valueменьше, чем branch-node.value, вы хотите перейти влево.Тем не менее, с тем же узлом, если у него нет левой ветви (node.left == NULL), новый узел будет левой веткой.В противном случае вам нужно пройти вниз по левой ветви и проверить еще раз.

Я бы сделал node классом и использовал бы конструктор, чтобы хотя бы установить свойства по умолчанию и value.Но это не имеет большого значения.