无法显示二叉搜索树C++

Question

我尝试创建一个二叉搜索树，使用 youtube 和我教授的示例来提供帮助，但是 Driver.cpp 中的显示不显示树的任何节点，除了“null”（旨在表示空指针）。我认为这是因为我的“root”仍然是 nullptr，即使我插入了一个新节点。输出应为“23 null null”。对不起，如果代码不够短和优化，我想在以后重读时自己弄清楚。

P.S.: 我已经删除了这里发布的代码中一些未完成的功能，所以可能会有一些小错误

//Driver.cpp
#include <iostream>
#include "Overall Tree.h";
using namespace std;

int main()
{
    BinaryTree tree_1;

    tree_1.insertNode(23);

    tree_1.display();

    return 0;
}

//Overall Tree.h
#include <iostream>
using namespace std;

class BinaryTree
{
    struct Node
    {
        int data; 
        Node* left;
        Node* right;
    };

private:
    Node* root;

public:
    // Constructors and Destructors
    BinaryTree();

    //traversal functions
    void preOrder();
    void inOrder();
    void postOrder();
    void preOrderTraverse(Node*);
    void inOrderTraverse(Node*);
    void postOrderTraverse(Node*);

    //display function
    void display();

    //insert functions
    void insertNode(int);
    void insert(Node*, Node*);
};

BinaryTree::BinaryTree()
{
    root = nullptr;
}

//display traversals
void BinaryTree::display()
{
    cout << "Pre-order traversal: " << endl;
    preOrder();
    cout << endl << endl;

    cout << "In-order traversal: " << endl;
    inOrder();
    cout << endl << endl;

    cout << "Post-order traversal: " << endl;
    postOrder();
}

// traversals
void BinaryTree::preOrder()
{
    preOrderTraverse(root);
}

void BinaryTree::inOrder()
{
    inOrderTraverse(root);
}

void BinaryTree::postOrder()
{
    postOrderTraverse(root);
}

void BinaryTree::preOrderTraverse(Node* root)
{
    if (root != nullptr)
    {
        cout << root->data << " ";
        preOrderTraverse(root->left);
        preOrderTraverse(root->right);
    }
    else
        cout << "null ";
}

void BinaryTree::inOrderTraverse(Node* root)
{
    if (root != nullptr)
    {
        preOrderTraverse(root->left);
        cout << root->data << " ";
        preOrderTraverse(root->right);
    }
    else
        cout << "null ";
}

void BinaryTree::postOrderTraverse(Node* root)
{
    if (root != nullptr)
    {
        preOrderTraverse(root->left);
        preOrderTraverse(root->right);
        cout << root->data << " ";
    }
    else
        cout << "null ";
}

//insert
void BinaryTree::insertNode(int x)
{
    Node* newNode = new Node;
    newNode->data = x;
    newNode->left = nullptr;
    newNode->right = nullptr;

    insert(newNode, this->root);
}

void BinaryTree::insert(Node* newNode, Node* p)
{
    if (p == nullptr)
        p = newNode;
    else
        if (newNode->data < p->data)
            insert(newNode, p->left);
        else if (newNode->data > p->data)
            insert(newNode, p->right);
        else
            cout << "Value already existed in the tree.";
}

Answer 1

你应该在你的 insert 函数中传递指向 root 的指针，如：

void BinaryTree::insert(Node* newNode, Node** p)
{
    if (*p == nullptr) {
        *p = newNode;
    } else {
        if (newNode->data < (*p)->data) {
            insert(newNode, &(*p)->left);
        } else if (newNode->data > (*p)->data) {
            insert(newNode, &(*p)->right);
        } else {
            cout << "Value already existed in the tree.";
        }
    }
}

然后像这样使用这个函数：

insert(newNode, &this->root);

为什么指针指向指针？

因为您想要修改 insert 函数中的参数（在本例中为 p 参数），以影响调用者传入的参数。

编辑

您也可以为此目的使用参考资料：

void BinaryTree::insert(Node* newNode, Node*& p)
{
    if (p == nullptr) {
        p = newNode;
    } else {
        if (newNode->data < p->data) {
            insert(newNode, p->left);
        } else if (newNode->data > p->data) {
            insert(newNode, p->right);
        } else {
            cout << "Value already existed in the tree.";
        }
    }
}

然后像这样使用它：

insert(newNode, this->root);

我建议使用参考，因为 IMO 的语法更清晰。

无法显示二叉搜索树C++

Can't display binary search tree C++

c++

binary-search-tree