push_back() 二叉树转化为向量

Question

我正在尝试将二叉搜索树中的所有元素按顺序放入向量中。这是函数：

编辑：为清楚起见添加说明。写一个 class 来实现一个简单的能够存储数字的二叉搜索树。 class 应该有成员函数：

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

插入函数不应直接使用递归或通过调用递归函数间接使用。搜索函数应该通过调用私有递归成员函数来工作

bool search(double x, <double> & v )

向inorder函数传递了一个初始为空的向量v； if 用存储在二叉搜索树中的数字的中序列表填充 v。使用合适的驱动程序演示 class 的操作。

编辑：为清晰起见添加了完整代码。

#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(std::vector <double> & v) {

    {
        if (left)
            left->inOrder(v);
        v.push_back(value);
        if (right)
            right->inOrder(v);
    }
}
TreeNode* left = nullptr;
TreeNode* right = nullptr;
double 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

您通常会递归地执行此操作：

#include <vector>    

class TreeNode {
    void inOrder(std::vector<double>& v) const
    {
        if (left)
            left->inOrder(v);
        v.push_back(value);
        if (right)
            right->inOrder(v);
    }

    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    double value;
};

编辑： 添加了#include

Edit2: 我就是这样做的。欢迎提问：

#include <iostream>
#include <vector>

class BinaryTree {
private:
    struct TreeNode {

        double value;
        TreeNode *left = nullptr;
        TreeNode *right = nullptr;

        TreeNode(double value1)
            : value(value1)
        {}

        void inOrder(std::vector <double> & v) {
            if (left)
                left->inOrder(v);
            v.push_back(value);
            if (right)
                right->inOrder(v);
        }
    };

    TreeNode *root = nullptr;    //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;
                return search(x, t->left);
            }
            else {
                std::cout << "wasn't found, moving right." << std::endl;
                return search(x, t->right);
            }
        }
        std::cout << "wasn't found." << std::endl;
        return false;
    }
public:


    BinaryTree() {}

    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) {
                if (!tree->left)
                {
                    tree->left = new TreeNode(x);
                    return;
                }
                tree = tree->left;
            }
            else {
                if (!tree->right)
                {
                    tree->right = new TreeNode(x);
                    return;
                }
                tree = tree->right;
            }
        }
    }
    bool search(double x) {
        return search(x, root);
    }
    void inOrder(std::vector<double>& v)
    {
        root->inOrder(v);
    }
};



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;
    std::vector<double> v;

    t.inOrder(v);
    std::cout << "values in order:";
    for (double val : v)
    {
        std::cout << " " << val;
    }
    std::cout << std::endl;

    return 0;
}

push_back() 二叉树转化为向量

push_back() binary tree into vector

c++11

vector

binary-tree

inorder