基本概念

// 线索二叉树的存储结构
typedef struct ThreadNode{
    
	ElemType data;						// 数据元素
	struct ThreadNode *lchild, *rchild; // 左右孩子指针
	int ltag, rtag;						// 左右线索标志
}ThreadNode, *ThreadTree;

• In the traditional binary tree,若(某结点)无左子树,令 lchild 指向其前驱节点;若无右子树,令 rchild 指向其后继节点

• The meaning of the symbol domain

  1. ltag：为0Said in a node's left child,为1时表示结点的前驱
  2. rtag：为0That node's right child,为1时表示结点的后继

• 好处：引入线索二叉树是为了加快查找结点前驱和后继的速度,Using the spare n + 1 个指针

• 普通的二叉树(链表)Called binary list;Clues binary tree is called the list

中序线索二叉树

构造

• 实质：Binary tree traversal ordinary

// Sequence clues in the recursive algorithm
void InThread(ThreadTree &p, ThreadTree &pre) {
    
	if(p != NULL) {
    
		InThread(p -> lchild, pre); 	// 找左子树
		if(p -> lchild == NULL) {
    
			p -> lchild = pre;			// 左子树为空,建立前驱线索
			p -> tag = 1;				// 标志位
		}
		if(pre != NULL && pre -> rchild == NULL) {
    
			pre -> rchild = p;			// 右子树为空,建立前驱结点的后继线索
			pre -> rtag = 1;			// 标志位
		}
		pre = p;						// Mark the current nodes as just visit
		InThread(p -> rchild, pre);		// 找右子树
	}
}

// Sequence clues in binary tree to build
void CreateInThread(ThreadTree T) {
    
	ThreadTree pre = NULL;
	if(T != NULL) {
    
		InThread(T, pre);				// 中序线索化
		// The last node of the right subtree(可能为空)For the last node of the subsequent clues
		pre -> rchild = NULL;
		pre -> tag = 1;
	}
}

改进：增加一个headPointers as clues to the head of the linked list node,A two-way clues linked list

void CreateInThread(ThreadTree T) {
    
	ThreadTree head;
	ThreadTree pre = NULL;
	if(T != NULL) {
    
		head -> lchild = T;				// headHead left pointer pointing to the clues of the chain table
		InThread(T, pre);				// 中序线索化
		head -> rchild = pre;			// headPointer to the right clues tail chain table
		pre -> rchild = head;			// The last node pointer refers to the right turn head node
		pre -> tag = 1;					// 标志化
	}
}

其他版本的代码（对比参考）（You can use the second figure you go again）（动图解析）

遍历

// 中序线索二叉树的遍历(不含头结点)

// 第一个结点
ThreadNode *Firstnode(ThreadNode *p) {
    
	while(p -> ltag == 0) p = p -> lchild;
	return p;
}

// 结点p的后继 
ThreadNode *Nextnode(ThreadNode *p) {
    
	if(p -> rtag == 0) return Firstnode(p -> rchild);
	else return p -> rchild;
}

// 最后一个结点
ThreadNode *Lastnode(ThreadNode *p) {
    
	while(p -> rtag == 0) p = p -> rchild;
	return p;
}

// 结点p的前驱
ThreadNode *Prenode(ThreadNode *p){
    
	if(p -> ltag == 0) return Fristnode(p -> lchild);
	else return p -> lchild;
}