在 c++ 中搜索二叉搜索树中的元素时出现分段错误

Question

node ** BST :: searchElement(node **tree, int item)
{
    if( ((*tree)->data == item) || ( (*tree) == NULL) )
        return tree;
    else if( item < (*tree)->data)
        return searchElement( &(*tree)->left, item);
    else
       return searchElement( &(*tree)->right, item);
}

int main(){
    BST obj;
    int choice;
    int height=0,total=0,n,item;
    node **tmp;
    system("cls");

    while(1){
        //clrscr();
        cout<<"*****BINARY SEARCH TREE OPERATIONS*****\n\n";
        cout<<"1) Create Tree\n";
        cout<<"2) Traversal\n";
        cout<<"3)  Insert Node\n";
        cout<<"4)  Search Node\n";
        cout<<"5 Find Smallest Node\n";
        cout<<"6) Find Largest Node\n";
        cout<<"7) Exit\n";
        cout<<"Enter your choice : ";
        cin>>choice;
        switch(choice){
            case 1 : //Create Tree
                cout<<"\n\n--Creating Tree--";
                cout<<"\nHow many nodes u want to enter : ";
                cin>>n;
                for(int i=0;i<n;i++){
                    cout<<"Enter value : ";
                    cin>>item;
                    obj.createTree(&obj.tree,item);
                }
                break;

            case 2 : //All Traversals
                cout<<"\n\nInorder Traversal : ";
                obj.inOrder(obj.tree);

                cout<<"\n\nPre-order Traversal : ";
                obj.preOrder(obj.tree);

                cout<<"\n\nPost-order Traversal : ";
                obj.postOrder(obj.tree);
                getch();
                break;

            case 3 : //Inserting a node in a tree
                cout<<"\n\n--Inserting Node in a tree--\n";
                cout<<"Enter value : ";
                cin>>item;
                obj.createTree(&obj.tree,item);
                cout<<"\nItem is inserted\n";
                getch();
                break;

            case 4 : //Search element
                cout<<"\n\n--Search Element--\n";
                cout<<"Enter item to searched : ";
                cin>>item;
                &(*tmp) = obj.searchElement(&obj.tree,item);
                if( (*tmp) == NULL)
                cout<<"\nSearch Element was not Found";
                else
                    cout<<"\nSearch Element was Found";
                getch();
                break;
            case 5 : //Find Smallest Node
                cout<<"\n\nSmallest Node is :  ";
                obj.findSmallestNode(obj.tree);
                getch();
                break;

            case 6 : //Find Largest Node
                cout<<"\n\nLargest Node is :  ";
                obj.findLargestNode(obj.tree);
                getch();
                break;



            case 7: exit(1);
        }//end of switch
    }
}

在上面的程序中，当我尝试在树中查找特定元素时，只有情况 4 无法正常工作。我在主程序的顶部包含了搜索元素成员函数。当我调试程序时，我在搜索元素成员函数中遇到分段错误，尤其是在 if 条件中。我真的不知道我需要做什么才能摆脱这个问题。谁能帮我找出搜索元素成员函数内部发生分段错误的原因。如果您对此计划有任何疑问，请告诉我。

Answer 1

if( ((*tree)->data == item) || ( (*tree) == NULL) )

应该是

if ( ( (*tree) == NULL) || ((*tree)->data == item) )

如果*tree实际上为 null，则您在第一次检查中取消引用空指针。交换它们将确保当您检查 (*tree)->data 时 *tree 不为 NULL - 由于 短路评估

此外，&(*tmp) 应写为 tmp

Answer 2

您正在取消引用未初始化的指针（tmp）。你应该为它分配内存或者跳过它的使用（我真的不明白为什么你需要一个临时节点**。）

Answer 3

以下是一些批评：
由于您只搜索节点，因此不需要指针到指针。唯一需要指向指针的指针是当您实际需要修改参数时。另外，由于您使用的是 C++，因此您应该传递引用：node * &tree，而不是传递 pp。这使得您可以使用树变量而无需取消引用它，因为编译器会为您处理这个问题。

在 if 语句中，您不会检查左指针或右指针是否为空指针。我不确定你是否有这方面的哨兵节点，但我假设你没有。这样，我会将您的方法更改为：

node * BST :: searchElement(node *tree, int item)
{
    if(tree->data == item)
        return tree;
    //short circuit if statements
    else if( (tree->left != NULL) && (item < tree->data) )
        return searchElement( tree->left, item );
    else if( (tree->right != NULL) && (item > tree->data) ) //>= for duplicates
        return searchElement( tree->right, item );

    return NULL; //if it isn't found
}

Answer 4

是的。事实上，正如 Erik 已经发布的那样，您必须编写

if ( ( (*tree) == NULL) || ((*tree)->data == item) )

而不是

if( ((*tree)->data == item) || ( (*tree) == NULL) )

因为如果 item 尚未在树中，那么在尝试取消引用 NULL 指针时，您的代码肯定会导致段错误。

还有另一个（不那么明显）问题——绝对不必要的递归。如果在插入或删除树节点时没有进行仔细的平衡，那么您最多只能拥有线性树高度，因此最多只能拥有线性递归深度，这可能很容易导致堆栈溢出。所以你应该将 searchElement 函数转换为

node** BST::searchElement( node** tree, int item )
{
    while(  ( (*tree) != NULL)  &&  ( (*tree)->data != item )  )
    {
        if( item < (*tree)->data )
        {
            tree = &(*tree)->left;
        }
        else
        {
            tree = &(*tree)->right;
        }
    }

    return tree;
}