实现我自己的二叉树

Question

作为作业，我必须实现一个二叉树（不使用 STL 二叉树）容器。我有所有的树功能，除了一个。

Link 到我的代码： https://github.com/matthamil/BinaryTree

在 bt_class.h 中，我有我的 binary_tree 模板 class 和模板实现。

在 bintree.h 中，我的 binary_tree_node class 带有模板实现。

在 main.cpp 中，我进行了一系列测试以确保功能正常工作。

我的问题在这里：

template <class Item>
Item binary_tree<Item>::retrieve( ) const
{
    return current_ptr->data();
}

我需要此函数的 return 类型是存储在 binary_tree_node 中的任何数据类型。我不确定如何完成此操作。

对于当前的实现，它return是指向当前节点的指针。

我应该会写

cout << test->retrieve();

in main.cpp 并且输出将是当前节点的数据。但是，由于它是 returning 一个指针，我必须添加一个额外的步骤：

*first = test->retrieve();
cout << first->data() << endl;
//"first"

有人可以提供帮助吗？

Answer 1

我认为问题出在此处 add_left、add_right。

template <class Item>
void binary_tree<Item>::create_first_node(const Item& entry)
{
    if (count == 0)
    {
        root_ptr = new Item(entry);
        current_ptr = root_ptr;
        count++;
    } else {
        std::cout << "Can't create first node for tree that has a first node already." << std::endl;
    }
}

这里发生的是你正在传递一个节点的指针并调用 new。所以基本上你正在做的是创建一个 binary_tree_node(&binary_tree_node)。

binary_tree_node<string> *first = new binary_tree_node<string> ("first");
binary_tree_node<string> *second = new binary_tree_node<string> ("second");
binary_tree_node<string> *third = new binary_tree_node<string> ("third");

test->create_first_node(*first);
test->add_right(*second);
test->add_left(*third);

因此在你的 binary_tree_node 里面还有另一个 binary_tree_node。有不同的方法来修复它。修复它的最佳方法只是将指针分配给 current_ptr 或者简单地在 binary_tree_node 中实现一个适当的复制构造函数。然而，正如评论已经解释的那样，这是一个糟糕的设计选择。 class binary_tree 应在内部生成 binary_tree_node classes，而无需用户手动实例化 classes 并处理这些指针。

实现我自己的二叉树

Implementing my own binary tree

c++

tree

templates

binary-tree