在我的程序中,我的二进制树有一个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();
};
我弄清楚在开始和结束时使用什么,我将如何实现这个重载?
1 回答
如果此节点具有右子树,则后继将是右子树中的第一个节点 . 所以去右边的子树,从那里继续往左走,直到你不能再离开 . 那个节点是继承者 .
如果节点没有正确的子树,我们检查其父节点 . 如果它没有父树而没有右子树,则它是树中的最后一个节点 . 当我们到达父母时,有两个子案例:
我们是左边的节点 . 在这种情况下,我们的父母是我们的继任者 .
我们是正确的节点 . 在这种情况下,我们遍历父节点链,直到找到我们之后的节点或找到没有父节点的节点 . 在前一种情况下,该节点是我们的继任者 . 在后一种情况下,我们是最后一个节点,没有后继者 .