|
线索二叉树概念 定义 n个结点的二叉链表中含有n+个空指针域利用二叉链表中的空指针域存放指向结点在某种遍历次序下的前趋和后继结点的指 针(这种附加的指针称为 线索 ) 这种加上了线索的二叉链表称为 线索链表 相应的二叉树称为 线索二叉树 (Threaded BinaryTree)根据线索性质的不同 线索二叉树可分为前序线索二叉树中序线索二叉树和后序线索二叉树三种 注意 线索链表解决了二叉链表找左右孩子困难的问题出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题 线索链表的结点结构 线索链表中的结点结构为 其中: ltag和rtag是增加的两个标志域用来区分结点的左右指针域是指向其左右孩子的指针还是指向其前趋或后继的线索 线索二叉树的表示 【例】下面(a)图所示的中序线索二叉树其线索链表如下面(b)图所示 注意 图中的实线表示指针虚线表示线索 结点C的左线索为空表示C是中序序列的开始结点无前趋; 结点E的右线索为空表示E是中序序列的终端结点无后继 线索二叉树中一个结点是叶结点的充要条件为左右标志均是 |
