c++ - 插入函数不断重新创建根节点

Question

我正在尝试创建一个非递归 insert() 函数。我在书中唯一的例子是一个递归的例子，我正在尝试转换它。只是为了让您了解我要完成的工作以及我为什么要包含这些说明。

编写一个类来实现一个能够存储数字的简单二叉搜索树。该类应具有成员函数:

void insert(double x)
bool search(double x)
void inorder(vector <double> & v)

插入函数不应直接使用递归或通过调用递归函数间接使用。

还有更多，但我认为这给出了我所问问题背后的想法。到目前为止，该函数只是不断地重新创建根节点。这是我的。

编辑:为清楚起见添加完整代码。

#include "stdafx.h"
#include <iostream>
#include <vector>

class BinaryTree {

private:
struct TreeNode {

    double value;
    TreeNode *left;
    TreeNode *right;
    TreeNode(double value1,
        TreeNode *left1 = nullptr,
        TreeNode *right1 = nullptr) {

        value = value1;
        left = left1;
        right = right1;
    }
};

TreeNode *root;    //pointer to the root of the tree
bool search(double x, TreeNode *t) {

    while (t) {
        std::cout << "running through t." << std::endl;
        if (t->value == x) {
            return true;
        }
        else if (x < t->value) {
            std::cout << "wasn't found, moving left." << std::endl;
            search(x, t->left);
        }
        else {
            std::cout << "wasn't found, moving right." << std::endl;
            search(x, t->right);
        }
    }
    std::cout << "wasn't found." << std::endl;
    return false;
}


public:

std::vector<TreeNode> v;

BinaryTree() {
    root = nullptr;
}

void insert(double x) {
    TreeNode *tree = root;

    if (!tree) {
        std::cout << "Creating tree." << x << std::endl;
        root = new TreeNode(x);
        return;
    }

    while (tree) {

        std::cout << "Adding next value." << std::endl;
        if (tree->value == x) return;

        if (x < tree->value) {
            tree = tree->left;
            tree->value = x;
        }
        else {
            tree = tree->right;
            tree->value = x;
        }
    }

}
bool search(double x) {

    return search(x, root);
}

/*void inOrder(TreeNode *v) const {

    while (root != nullptr) {

        inOrder(root->left);
        v.push_back(root->value);
        inOrder(root->right);
        v.push_back(root->value);
    }
}*/
};

int main() {

    BinaryTree t;

    std::cout << "Inserting the numbers 5, 8, 3, 12, and 9." << std::endl;
    t.insert(5);
    t.insert(8);
    t.insert(3);
    t.insert(12);
    t.insert(9);

    std::cout << "Looking for 12 in tree." << std::endl;
    if (t.search(12)) {
        std::cout << "12 was found." << std::endl;
    }

    std::cout << "Here are the numbers in order." << std::endl;


    return 0;
}

Answer 1

在您的 insert() 方法中，您将传递的每个节点的值设置为新值。这可能不是您想要的。

如果你想插入它，你需要弄清楚它的去向，创建一个具有适当值的新节点，并将新节点插入到树中，注意处理之前存在的节点。