线索二叉树

线索二叉树简介

线索化二叉树是为了充分利用各个节点的左右指针，含有 n 个节点的二叉树有 n+1 个空指针域，利用这些空指针域存放指向该节点在某种遍历次序下的前驱和后继节点的指针，这种附加的指针称为“线索”

加上了线索的二叉链表称为线索链表，相应的，二叉树称为线索二叉树（Thread BinaryTree）

根据线索性质的不同，线索二叉树可分为

• 前序线索二叉树
• 中序线索二叉树
• 后序线索二叉树

此外，一个节点的前一个节点称为前驱节点，后一个节点称为后继节点，这里的前后指的是遍历过程中的前后

比如下图中左边这颗二叉树的中序遍历序列为 {8, 3, 10, 1, 14, 6}，加上中序遍历线索之后如右图所示：