c++ - 为二叉树重载++ 运算符

Question

在我的程序中，我的二叉树有一个 preOrder Iterator 类。在其中，我试图在++ 运算符上实现运算符重载，以便从头到尾遍历树。但是我感到困惑，因为二叉树可以同时具有左侧和右侧。我怎么知道起点在哪里？它总是最左边的节点吗？

这是我的代码结构:

父二叉树:

/* Binary Tree */
class bin_tree
{
public:
    int data;
    bin_tree *left;
    bin_tree *right;
    bin_tree *parent;

    class preOrder_iterator; //child iterator class 
};

子迭代器类:

/* Iterator class -- inherits from parent */
class bin_tree::preOrder_iterator : public bin_tree
{
        preOrder_iterator& operator ++ () //++ prefix operator overload
        {

        }
        preOrder_iterator begin();
        preOrder_iterator end();
};

如果我弄清楚开始和结束使用什么，我将如何实现这个重载？

Answer 1

如果此节点有右子树，则后继者将是右子树中的第一个节点。所以转到右子树，从那里继续向左走，直到你不能再向左走。该节点是后继节点。

如果节点没有右子树，我们检查它的父节点。如果它没有父节点也没有右子树，那么它就是树中的最后一个节点。当我们到达父级时，有两种子情况:

1. 我们是左节点。在这种情况下，我们的 parent 就是我们的继任者。

2. 我们是正确的节点。在这种情况下，我们遍历父节点链，直到找到在我们之后的节点或找到没有父节点的节点。在前一种情况下，该节点是我们的继任者。在后一种情况下，我们是最后一个节点，没有后继者。