Блог

Я попытался создать двоичное дерево поиска, используя youtube и примеры от моего профессора, чтобы помочь, но отобразить в Driver.cpp не показывает ни одного узла дерева, кроме «null» (который должен был представлять nullptr). Я думаю, это потому, что мой «root» остается как nullptr, хотя я вставил новый узел. Вывод должен быть «23 null null». Извините, если коды не короткие и не оптимизированы, я хочу прояснить ситуацию для себя, когда я перечитаю их позже.

PS: я удалил некоторые незавершенные функции в коде, размещенном здесь, поэтому могут быть незначительные ошибки

 //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.";
}
  

Вы должны передать указатель на указатель на корень в вашей insert функции, например:

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

а затем используйте эту функцию, например:

 insert(newNode, amp;this->root);
  

Почему указатель на указатель?

Потому что вы хотите, чтобы изменения параметра (в данном случае p параметра), сделанные в insert функции, повлияли на аргумент, переданный вызывающим.

Редактировать

Вы также можете использовать reference для этой цели:

 void BinaryTree::insert(Node* newNode, Node*amp; 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);
  

Я бы предложил использовать reference из-за более чистого синтаксиса IMO.