分段错误（核心已转储）- 线程二进制搜索树

Question

我不断收到以下错误：分段错误（核心已转储）。我找出了导致问题的代码行（在程序中标有注释）。请告诉我为什么会出现此错误以及如何解决它。

我已经尝试干燥运行我的代码（在纸上）并且没有发现任何逻辑错误（根据我的理解）。
我最近才开始接触编码和 Whosebug，请指导我如何进一步改进我的问题以及我的代码。谢谢！

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

没有足够的信息来确切说明它应该如何工作（例如 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 设为 class，并使用构造函数至少设置默认属性和 value。但这没什么大不了的。

Answer 2

我认为评论部分在很大程度上反映了沟通不畅。很容易相信您正在经历 ON 特定线路的崩溃。

实际情况并非如此。相反，您所做的是在树中创建一个循环，该循环导致 inorder 函数无限递归。这会导致出现段错误的堆栈溢出——如果您的程序只是运行附加了调试器（例如 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 3

来自代码，

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

root 没有指向 temp。 temp(pointer) 被分配给 root(pointer)。 head的左指针是root，temp的左指针是head（也就是说root的左指针是head）。所以在函数 "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，并且函数永远不会 return。

分段错误（核心已转储）- 线程二进制搜索树

Segmentation fault (core dumped) - Threaded Binary Search Tree

c++

binary-tree

binary-search-tree