三种遍历

因为线索化后, 各个结点指向有变化, 因此原来的遍历方式不能使用, 需要使用新的方式遍历线索化二叉树。

中序线索二叉树的结点中隐含了线索二叉树的前驱和后继信息

在对其遍历时,需要找到第一个具有前驱结点的左结点,然后依次找结点的后继。

在中序线索二叉树中找结点后继的规律是:

  • 若其右标志为1,则右链为线索,指示其后继;
  • 否则遍历右子树中第一个访问的结点(右子树中最左下的结点)为其后继。
void InOrderTraverse(BiThrTree T){ // 中序输出
    if(T)
    {
        InOrderTraverse(T->lchild); //中序遍历左子树
        cout<< T->data;
        InOrderTraverse(T->rchild); //中序遍历右子树
    }
}
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《三种遍历》
文章链接:https://zhuji.vsping.com/4514.html
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。