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

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

例如在这个代码块中

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

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

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

更好的设计是 BinaryTree 类包含指向树头的指针。像这样声明数据成员父级

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

并相应地重写类。:)