算法5--线索二叉树.ppt

6 4线索二叉树 2 线索二叉树 6 4 1线索二叉树的定义6 4 2线索二叉树的遍历算法 目的 利用二叉树的空指针保存遍历序列的前驱和后继 n个结点的二叉树 有2n个指针 只用了n 1个 有n 1个是空指针 用空的左指针指向某一遍历序列的前驱 用空的右指针指向某一遍历序列的后继 这两种指针称为线索 Thread 为了区分线索与真实指针 给结点增加两个域Ltag和Rtag 6 4 1线索二叉树的概念 Ltag 0 lchild指向结点的左子女 Ltag 1 lchild指向某一遍历序列前驱 Rtag 0 rchild指向结点的右子女 Rtag 1 rchild指向某一遍历序列后继 6 4 1线索二叉树的概念 二叉树的二叉线索存储表示typedefenum Link Thread PointerTag Link 0 指针 Thread 1 线索typedefstructBiThrNode TElemTypedata StructBiThrNode lchild rchild 左右孩子指针PointerTagLTag RTag 左右标志 BiThrNode BiThrTree 6 4 1线索二叉树的概念 4 1 2020 加了线索的二叉树是线索二叉树 给二叉树加线索的过程是线索化 穿线 按前序遍历序列穿线的二叉树是前序线索二叉树 按中序遍历序列穿线的二叉树是中序线索二叉树 按后序遍历序列穿线的二叉树是后序线索二叉树 中序线索二叉树简称线索二叉树 加了线索的二叉树是线索二叉树 二叉树加线索的过程是线索化 穿线 按前序遍历序列穿线的二叉树是前序线索二叉树 按中序遍历序列穿线的二叉树是中序线索二叉树 按后序遍历序列穿线的二叉树是后序线索二叉树 中序线索二叉树简称线索二叉树 6 4 1线索二叉树的概念 线索二叉树 ThreadedBinaryTree A G D B F c E a 二叉树 b 先序线索树 root ABDGCEF 线索二叉树 ThreadedBinaryTree A G D B F C E a 二叉树 c 中序线索树 root DGBAECF 线索二叉树 ThreadedBinaryTree A G D B F C E a 二叉树 d 后序线索树 root GDBEFCA D B F E A C NULL NULL 中序线索二叉树 线索二叉树 ThreadedBinaryTree 6 4 2线索二叉树的遍历算法 算法6 5 中序遍历二叉线索树T的非递归算法 对每个数据元素调用函数Visit T指向头结点 头结点的左链lchild指向根结点 可参见线索化算法 StatusInOrderTraverse Thr BiThrTreeT Status Visit TElemTypee p T lchild p指向根结点while p T 空树或遍历结束时 p Twhile p LTag Link p p lchild if Visit p data returnERROR 访问其左子树为空的结点while p RTag Thread InOrderTraverse Thr 6 4 2线索二叉树的遍历算法 算法6 6 中序遍历二叉树T 并将其中序线索化 Thrt指向头结点StatusInOrderThreading BiThrTree InOrderThreading 6 4 2线索二叉树的遍历算法 voidINThreading BiThrTreep if p InThreading p lchild 左子树线索化if p lchild p LTag Thread p lchild pre 前驱线索if pre rchild pre RTag Thread pre rchild p 后继线索pre p 保持pre指向p的前驱InThreading p rchild 右子树线索化 InThreading 非递归中序遍历二叉树的算法 复习 VoidlnorderTraverse BiTreeBT 采用二叉链表存储结构 中序遍历二叉树T的非递归算法 InitStack S p BT while p StackEmpty S if p push S p p p lchild 根指针进栈 遍历左子树else 根指针退栈 访问根结点 遍历右子树pop S p visit p p p rchild else InOrderTraverse 6 4 2线索二叉树的遍历算法 对以二叉链表存储的二叉树进行中序线索化 非递归的 voidInOrderThreading BiThrTreeBT InitStack S 建立栈p BT pre NULL p指向根 pre是p的前驱结点while p StackEmpty S if p push S p p入栈p p lchild p指向左子女else pop S p 弹出栈顶元素到p中if p lchild p lchild pre p ltag true if pre p指向右子女 endofwhile endofInOrderThreading BT visit p 中序 线索二叉树的线索给我们提供了足够的信息 对其进行遍历时 既不需要递归 使用了系统栈 也不需要栈 对 中序 线索二叉树进行非递归遍历且不需要设栈时需要主要解决的两个问题 找到某一次序下的第一个结点p 2 找出给定结点p在某一次序中的后继结点 关键问题1沿着根的左链走 直到无左子女的结点p 即中序序列中的第一个结点 p BT while p ltag p p lchild 关键问题2 有如下两种情况 P无右子女 则p rchild是p的后继 P有右子女 则p的右子树中最左的结点就是p的后继 方法同关键问题1 if p rtag p p rchild P无右子女else p p rchild P有右子女while p ltag p p lchild 中序遍历 中序 线索二叉树时如何解决这两个问题 前序遍历线索二叉树的算法voidPreOrderTraverse BiThrTreeBT p BT while p visit p if p ltag p p lchild P有左子女elseif p rtag p p rchild P有右子女else r p rchild p是叶子while r PreOrderTraverse 关键问题1根就是第一个结点 关键问题2 有如下3种情况 P有左子女