线索二叉树

// 中序遍历对二叉树线索化的递归算法
void InThread(ThreadTree &p, ThreadTree &pre) {
	if (p != NULL) {
    	InThread(p->lchild, pre);	// 一直递归到最左子树  
        
        /* 中序遍历 */
        if(p->lchild == NULL) {		// 没有左孩子就指向前驱
        	p->lchild = pre;		// 建立当前节点的前驱线索
            p->ltag = 1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
        	pre->rchild = p;	// 建立前驱节点的后继线索
            pre->rtag = 1;
        }
        pre = p;
        /* 中序遍历 */
        
        InThread(p->rchild, pre);	// 递归线索化右子树
    }
}

// 中序遍历建立中序线索二叉树
void CreateInThread(ThreadTree T) {
	ThreadTree pre = NULL;
    if (T != NULL) {
    	pre->rchild = NULL;
    	pre->rtag = 1;
    }
}

算法的思想很简单：算法整体思路与中序遍历一致，按照“左根右”的顺序编排代码。

• 首先InThread一直递归到最左子树；
• 其次我们要帮助p节点寻找前驱节点，建立前驱线索；
• 之后我们要帮助pre节点寻找后继节点，建立后继线索；
• 最后InThread向右递归；

总结：找到某个状态，完整状态的转变，最后递归解决问题。