时间戳

首页 > 解决方案 > 增加二叉树的正确方法

c++ - 增加二叉树的正确方法

问题描述

这是我创建的课程

#include <memory>

template <typename T> 
class binary_tree {

private:
    T t_data;
    std::unique_ptr<binary_tree<T>> t_left, t_right;
    
    class binary_tree_iterator {                  // -----------------------
    private:
        T data;
    public:                                       
        binary_tree_iterator(T d) : data(d) {}    //     Iterator class
        T& operator*() {return data;}
        binary_tree_iterator& operator++() {} // <--------- ??????
    };                                            
                                                  // ------------------------
public:
    binary_tree(T d) : t_data(d), t_left(nullptr), t_right(nullptr)
    {}
    
    void insert(T data) {
        if(data <= t_data) {
            if(t_left == nullptr) {
                t_left = std::unique_ptr<binary_tree<T>>(new binary_tree<T>(data));
            } else {
                t_left->insert(data);
            }          
        } else {
            if(t_right == nullptr)
                t_right = std::unique_ptr<binary_tree<T>>(new binary_tree<T>(data));
            else
                t_right->insert(data);
        }
    }
    
    const T data() const {
        return t_data;
    }
    
    const std::unique_ptr<binary_tree<T>>& left() const {
        return t_left;
    }
    
    const std::unique_ptr<binary_tree<T>>& right() const {
        return t_right;
    }
    
    binary_tree_iterator begin() {      
        if(t_left == nullptr) {
            return binary_tree_iterator(t_data);
        } else {
            return t_left->begin();
        }
    }
    
    binary_tree_iterator end() {
        if(t_right == nullptr) {
            return binary_tree_iterator(t_data);
        } else {
            return t_right->end();
        }
    }
};

我已经在我的容器类中声明了我的迭代器类。这可能是一个错误，但无论哪种方式，我都不确定如何定义我的重载增量函数。一旦我找到了 begin() 我就迷路了。似乎 unique_ptr() 是为单向指向而设计的。假设我必须以这种方式使用 unique_ptr，这里有一些工作吗？我考虑过给 binary_tree 的每个实例一个头成员，该成员指向它的来源，但每个节点只能从它上面的节点访问。我做了某种索引，但这似乎完全违背了这种容器类型的目的。我正在解决练习，所以我仅限于使用 unique_ptr。

标签： c++classc++11iteratorunique-ptr

解决方案

您将迭代器定义为包含data树中的值。

这不是迭代器的全部内容。迭代器不包含它们所引用的值，而是对它的引用（在该词的通用含义中，而不是 C++ 术语中），通常是指针。

当然，你无法弄清楚该怎么做++。对于您的迭代器，很自然地期望++操作员将迭代器推进到树中的下一个节点，但是由于迭代器不包含指向任何东西的指针，所以您没有什么可推进的，并且遇到了心理障碍。

您将需要重新设计您的迭代器，使其包含指向您的binary_tree;的指针。它的*重载取消引用；并++前进到二叉树中的下一个元素，然后它将能够使用它的指针来执行此操作。

在这一点上，你会遇到另一个心理障碍。遍历整个二叉树有时需要备份到树中的父节点。毕竟，在递归到left二叉树的一部分之后，在某个时刻，在遍历二叉树之后，您将需要以某种方式以某种方式结束right二叉树的一部分。但是，按照设计，您binary_tree无法导航到任何节点的父节点。这是您需要以某种方式解决的另一个设计缺陷。

我想，有可能在迭代器本身中实现整个回溯，让迭代器记录它访问的每个节点，以便它可以在需要时备份到它。但是迭代器应该是轻量级的对象，它们本身只不过是一个指针，而不是实现复杂操作的完整数据结构。

总之，二叉树的设计中有几个漏洞需要解决，然后才能为其实现有效的迭代器。

推荐阅读