为BinaryTree类创建迭代器的算法
Mr.*_*bis 2 c++ binary-tree iterator data-structures
我想在我的Parametrized BinaryTree类中添加Bi-Directional Iterator(就像std :: set导出的Iterator),但是我无法想出任何算法.
简单的二叉树节点结构是,它包含三个指针,左,右,父:
使用给定的结构,您希望如下进行:
- 要开始迭代,您将找到最左侧的节点.
- 要转到下一个节点,操作取决于您当前的位置:
- 如果您的节点有一个正确的孩子,您将转到此孩子并找到其最左侧的后继者(如果没有左子女,则您所在的节点是下一个节点).
- 如果您的节点没有正确的子节点,则向上移动父节点链,直到找到您使用了左节点链接的父节点:下一个节点将成为此节点.
- 要向另一个方向移动,您可以反转左右角色.
实际上,这实现了树的无堆栈顺序遍历.如果在迭代时没有更改树(不太可能的情况),或者您没有到父节点的链接,则可以在迭代器中显式维护堆栈.
- @ Mr.Anubis:我的意思是:从当前节点看你的父节点.如果当前节点是父节点的正确子节点,则将父节点设为当前节点并检查其专利.如果当前节点是父节点的左子节点,则父节点就是您停止的位置.看到这个的最好方法是使用二叉树的绘图(悬挂直线上下颠倒):从子树中最右边的节点,你需要一直向上走,直到有一个节点有另一个子树挂起它正确的孩子或没有正确的孩子.当然,最终还有进一步的节点. (2认同)