数据结构_树_线索二叉树

github地址：
https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%91_%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91.md

线索二叉树

产品分类是树型结构，如果要频繁的按照一定的次序访问产品分类（遍历）

1. 有效的利用了二叉链表中的空指针
2. 对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化
3. 一棵有n个节点的二叉树，左右孩子用到的指针是n-1,留给线索的空指针是n+1

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/xiansuo_binaryTree.png" width="600" />

创建

按照中序遍历访问每一个节点，访问的过程中，用线索取代空指针。

1. 若上次访问的节点的右指针为空，则将当前访问的节点地址填入，并置右标识位为1（后序）
2. 若当前访问的节点的左指针为空，则将上次访问的节点地址填入，并置做标识位为1（前序）

注：从图2的H节点开始中序遍历，按照上述两条规则就可建立线索二叉树了

查询

访问前驱后继的方法是相同的，下面介绍后继，前驱反过来就行了

1. 如果当前节点P的右标识位为0，则P->rchild为线索，指向P的后继
2. 如果节点P的右标识位为1，则P的后继节点是右子树中序遍历的第一个节点。也就是沿着P的右孩子开始，按照左链（左孩子）往下查，直至找到一个没有左孩子的节点为止。

注：图3中A节点就是比较特殊的节点，他的前驱后继就得通过左右子树确定