实现我自己的二叉树

对于作业，我必须实现一个二叉树（不使用STL二叉树）容器。除了一个以外，我拥有所有的树功能。实现我自己的二叉树

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

在bt_class.h，我有一个模板，实现我的binary_tree模板类。

在bintree.h中，我有我的binary_tree_node类与模板实现。

在main.cpp中，我有一堆测试以确保函数的工作。

我的问题是在这里：

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

我需要这个函数的返回类型为的任何存储binary_tree_node中的数据类型。我不知道如何完成这一点。

在当前的实现中，它返回一个指向当前节点的指针。

我应该能够编写

cout << test->retrieve();

在main.cpp中

，输出将是任何当前节点的数据。然而，因为它返回一个指针，我必须添加额外的步骤：

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

任何人都可以提供任何帮助吗？

来源

2015-12-03 Matt Hamil

没有人会在链接上查看您的代码。请发布[MCVE]（http://stackoverflow.com/help/mcve）。 –

如果你的树有当前节点，你已经犯了一个重大的设计问题。 –

您将'Item'（'binary_tree'的模板参数）作为节点类型，而不是值类型。这是一个不寻常的选择，也许应该修复。如果你没有解决这个问题，你的检索定义可以使用C++ 11的'auto'功能来推导出值类型，或者更复杂的模板编码可以使值类型显式化。 – JSF

我认为问题在这里，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中实现适当的拷贝构造函数。然而正如评论已经解释的那样，这是一个糟糕的设计选择。类binary_tree应该在内部生成binary_tree_node类，而用户不必手动实例化类并处理这些指针。

来源

2015-12-03 18:06:08

实现我自己的二叉树

回答

相关问题