C++ 二叉搜索树和指针

Question

你能告诉我为什么方法binaryTree.Exists(5);的调用说“二叉树中不存在5”吗？调试时，就像尝试访问插入 5 的节点不再存在一样。我不明白为什么。谢谢！！！

#include <iostream>

using namespace std;


class Node
{
    private:
        int _value;
        Node* left;
        Node* right;

    public:
        Node(int value):_value(value), left(NULL), right(NULL)
        {
        }
        Node* returnLeftChild()
        {
            return left;
        }
        Node* returnRightChild()
        {
            return right;
        }
        void setLeftChild(Node* l)
        {
            left=l;
        }
        void setRightChild(Node* r)
        {
            right=r;
        }
        int getValue()
        {
            return _value;
        }
};

class BinaryTree
{
    private:
        Node parent;
        void AddToOneTree(Node* parent, int value)
        {
            if (value==parent->getValue())
            {
                return;
            }
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()==NULL)
                {
                    Node newNode(value);
                    parent->setRightChild(&newNode);
                    return;
                }
                else
                {
                    AddToOneTree(parent->returnRightChild(), value);
                }
            }
            if (value<parent->getValue())
            {
                if (parent->returnLeftChild()==NULL)
                {
                    Node newNode(value);
                    parent->setLeftChild(&newNode);
                    return;
                }
                else
                {
                    AddToOneTree(parent->returnLeftChild(), value);
                }
            }           
        }

        void LookForValue(Node* parent, int value, bool found)
        {
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()!=NULL)
                {
                    if (parent->returnRightChild()->getValue()==value)
                    {
                        found= true;
                        goto HERE;
                    }
                    else
                    {
                        LookForValue(parent->returnRightChild(), value, found);
                    }
                }
            }
            else if (value<parent->getValue())
            {
                if (parent->returnLeftChild()!=NULL)
                {
                    if (parent->returnLeftChild()->getValue()==value)
                    {
                        found= true;
                        goto HERE;
                    }
                    else
                    {
                        LookForValue(parent->returnLeftChild(), value, found);
                    }
                }
            }
            HERE:;
        }

    public:
        BinaryTree(int parentValue):parent(parentValue)
        {   
        }

        void Add(int value)
        {
            AddToOneTree(&parent, value);
        }

        void Exists(int value)
        {
            bool found = false;
            if (parent.getValue()==value)
            {
                cout << value << " exists in the Binary Tree." << endl;
            }
            else{
                LookForValue(&parent, value, found);
                if (found)
                {
                    cout << value << " exists in the Binary Tree." << endl;
                }else
                {
                    cout << value << " doesn't exist in the Binary Tree." << endl;
                }
            }
        }

};

int main()
{
    BinaryTree binaryTree(9);
    binaryTree.Add(5);
    binaryTree.Add(5);

    binaryTree.Exists(9);
    binaryTree.Exists(5);
}

Answer 1

您应该替换此字符串：

void LookForValue(Node* parent, int value, bool found)

对此：

void LookForValue(Node* parent, int value, bool &found)

或者在 LookForValue 函数中将 return 值设置为 bool 并编写如下内容：

found = LookForValue(&parent, value, found);

Answer 2

您的代码中有几个问题。

第一个是 LookForValue 函数从未 return 编辑找到的布尔值。您可以将 bool found 更改为 bool & found 这样您就不必 return 任何东西或将 LookForValue 的 return 类型更改为 bool 在这种情况下您将需要将您的代码更改为如下内容：

bool LookForValue(Node* parent, int value, bool found)
{
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()!=NULL)
                {
                    if (parent->returnRightChild()->getValue()==value)
                    {
                        return true ;
                    }
                    else
                    {
                        LookForValue(parent->returnRightChild(), value, found);
                    }
                }
            }
            else if (value<parent->getValue())
            {
                if (parent->returnLeftChild()!=NULL)
                {
                    if (parent->returnLeftChild()->getValue()==value)
                    {
                        return true ;
                    }
                    else
                    {
                        LookForValue(parent->returnLeftChild(), value, found);
                    }
                }
            }
}

如果您更改 return 类型，请考虑在 Exists 函数中更改 else:

之后的一行

found = LookForValue(&parent, value, found);

我还没有测试代码，所以可能还有其他问题。

下次您遇到此类问题时，我建议您尝试使用 gdb，因为它可能有助于检测您的代码实际在做什么，以便您找出可能存在的问题。例如在这里，你可以看到 found 从未在你的 Exists 函数中设置为 true 只是通过 "printing" 逐步设置你的 found 变量的值。

此外，我认为您类的设计方式不是很好。 Parent 应该是一个指针，指向树的根。我建议完全重新设计您的代码。您可以在网上找到一些很好的实现，您可以在上面编写代码。

最后，goto 绝对不是一个好主意......我也会摆脱它。

Answer 3

至少函数 AddToOneTree 是错误的，这是程序 未定义行为 的原因

例如在这个代码块

if (parent->returnRightChild()==NULL)
{
    Node newNode(value);
    parent->setRightChild(&newNode);
    return;
}

你创建了一个局部变量newNode并将它的地址赋值给右边的指针child。然而，由于变量是本地变量，它在控件离开代码块后被销毁，树中相应的指针将无效。

您需要动态分配节点并将它们添加到树中。

更好的设计是 class BinaryTree 包含指向树头的指针。声明数据成员 parent like

class BinaryTree
{
    private:
        Node *parent;
             ^^^^^^^^
    //...

并相应地重写 class.:)

Answer 4

void LookForValue(Node* parent, int value, bool found)

您正在按值传递 found。这意味着该值将被复制。当您在方法 LookForValue 中更改 found 时，您只是在更改此副本。

void LookForValue(Node* parent, int value, bool& found)

这将通过引用找到，因此如果您在 LookForValue 中更改它，Exists 方法中的原始内容也会更改。

您也可以只 return 像这样的 bool 值：

bool LookForValue(Node* parent, int value, bool &found)

然后只写 return true; 而不是

found= true;
goto HERE;

这样你也摆脱了 goto。

Answer 5

谢谢大家。我已经更改了通过引用找到的传递，并使用 "new" 为新的 nods.This 分配了内存，现在可以使用了！

#include <iostream>

using namespace std;


class Node
{
    private:
        int _value;
        Node* left;
        Node* right;

    public:
        Node(int value):_value(value), left(NULL), right(NULL)
        {
        }
        Node* returnLeftChild()
        {
            return left;
        }
        Node* returnRightChild()
        {
            return right;
        }
        void setLeftChild(Node* l)
        {
            left=l;
        }
        void setRightChild(Node* r)
        {
            right=r;
        }
        int getValue()
        {
            return _value;
        }
};

class BinaryTree
{
    private:
        Node parent;
        void AddToOneTree(Node* parent, int value)
        {
            if (value==parent->getValue())
            {
                return;
            }
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()==NULL)
                {
                    Node* newNode=new Node(value);
                    parent->setRightChild(newNode);
                    return;
                }
                else
                {
                    AddToOneTree(parent->returnRightChild(), value);
                }
            }
            if (value<parent->getValue())
            {
                if (parent->returnLeftChild()==NULL)
                {
                    Node* newNode=new Node(value);
                    parent->setLeftChild(newNode);
                    return;
                }
                else
                {
                    AddToOneTree(parent->returnLeftChild(), value);
                }
            }           
        }


        void LookForValue(Node* parent, int value, bool &found)
        {
            if (value>parent->getValue())
            {
                if (parent->returnRightChild()!=NULL)
                {
                    if (parent->returnRightChild()->getValue()==value)
                    {
                        found= true;
                        goto HERE;
                    }
                    else
                    {
                        LookForValue(parent->returnRightChild(), value, found);
                    }
                }
            }
            else if (value<parent->getValue())
            {
                if (parent->returnLeftChild()!=NULL)
                {
                    if (parent->returnLeftChild()->getValue()==value)
                    {
                        found= true;
                        goto HERE;
                    }
                    else
                    {
                        LookForValue(parent->returnLeftChild(), value, found);
                    }
                }
            }
            HERE:;
        }

    public:
        BinaryTree(int parentValue):parent(parentValue)
        {   
        }

        void Add(int value)
        {
            AddToOneTree(&parent, value);
        }

            void Exists(int value)
        {
            bool found = false;
            if (parent.getValue()==value)
            {
                cout << value << " exists in the Binary Tree." << endl;
            }
            else{
                LookForValue(&parent, value, found);
                if (found)
                {
                    cout << value << " exists in the Binary Tree." << endl;
                }else
                {
                    cout << value << " doesn't exist in the Binary Tree." << endl;
                }
            }
        }

};

int main()
{
    BinaryTree binaryTree(9);
    binaryTree.Add(5);
    binaryTree.Add(6);
    binaryTree.Add(1);
    binaryTree.Add(15);
    binaryTree.Add(13);
    binaryTree.Add(2);
    binaryTree.Add(2);
    binaryTree.Add(0);
    binaryTree.Add(4);

    binaryTree.Exists(9);
    binaryTree.Exists(5);
    binaryTree.Exists(6);
    binaryTree.Exists(1);
    binaryTree.Exists(15);
    binaryTree.Exists(13);
    binaryTree.Exists(2);
    binaryTree.Exists(2);
    binaryTree.Exists(0);
    binaryTree.Exists(4);
    binaryTree.Exists(11);

    binaryTree.Exists(412);

    binaryTree.Exists(40);


}

C++ 二叉搜索树和指针

C++ Binary Search Tree and Pointers

c++

binary-search-tree