二叉树线索化

1. 概念

普通遍历只能从 root 开始，加入线索化让其可以从中间开始遍历，规定无左子树指向前驱，无右子树指向后继。用 tag==0 表示有子树， tag==1 表示无子树

2. 线索化构造

2.1 利用中序线索树来寻找特定结点的前驱

朴素法(从头开始找)

void Inorder(BTree* root)
{
	if(root != NULL)
	{
		Inorder(root->left);
		visit(root);
		Inorder(root->right);
	}
}

void visit(BTree* q)
{
	 if(q == Findp)
	 {
		 ans = pre; // 当前等于 Findp时， pre会保留在前驱位置
	 }
	 else
	 {
		 pre = q;
	 }
}
Findp 是需要找前驱的结点 pre 存储前驱 ans存储最后答案

2.2 中序线索化

void Inorder(BTree* root)
{
	if(root != NULL)
	{
		Inorder(root->left);
		visit(root);
		Inorder(root->right);
	}
}
void visit(BTree* q)
{
	if(q->left == NULL) // 左子树为空指向前驱
	{
		q->left = pre;
		q->ltag = 1;
	}
	if(pre->right == NULL) // 前驱右子树为空指向后继即当前q
	{
		pre->right = q;
		pre->rtag = 1;
	}
	pre = q; // 往后
}

void CreateInThread(BTree* T) // 线索化主入口
{
	pre == NULL;
	if(T != NULL)
	{
		Inorder(T,pre);
		pre->right = NULL; // 处理最后一个结点表示无后续
		pre->rtag = 1;
	}
}

同理前序和后序遍历线索化只需改变递归处理顺序，但是注意前序遍历会出现转圈问题(如果当前左子树为空那么线索化成了 pre，而下一轮遍历左子树则又回到了 pre)

void Inorder(BTree* root)
{
	if(root != NULL)
	{
		visit(root);
		if(root->ltag == 0) // 注意只有有真左子树才进行遍历否则会导致循环
		Inorder(root->left);
		Inorder(root->right);
	}
}
void visit(BTree* q)
{
	if(q->left == NULL) // 左子树为空指向前驱
	{
		q->left = pre;
		q->ltag = 1;
	}
	if(pre->right == NULL) // 前驱右子树为空指向后继即当前q
	{
		pre->right = q;
		pre->rtag = 1;
	}
	pre = q; // 往后
}

后续遍历不会出现转圈问题

3. 寻找中序遍历前驱和后继

思路： 按照各种遍历顺序的特性去找，中左右，左中右，左右中，不断递归划分便可找到前驱后继的特性

3.1 找后继

一个结点的后继：

  1. 如果没有右子树，已经被线索化直接指向右结点
  2. 如果有右子树，那么它的后继结点就是右子树的最左下结点
Node* FirstNode(*p)
{
  while(p->ltag==0) p = p->left;
  return p;
}
// 找后继
Node* NextNode(p)
{
  if(p -> rtag == 0) return FirstNode(p->right);
  else return p->right
}
// 能找到后继结点就能继续中序遍历
void Inorder(root)
{
  for(p = FirstNode(root);p != NULL;p = NextNode(p)) // 找到中序第一个节点后开始遍历
  {
    visit(p);
  }
}

3.2 找前驱

一个结点的前驱：

  1. p->ltag == 1 之前有前驱
  2. p->ltag == 0 找左子树的最右下结点
Node* Lastnode(Node* p)
{
	while(p->rtag == 0) p = p->right; // 找到中序遍历最后一个访问结点
	return p;
}

4. 前序遍历前驱后继

4.1 后继

  1. 如果 rtag == 1 直接就是后继
  2. 如果 rtag == 0 必有右子树;但如果有左子树后继是左子树根，没有就是右子树根

4.2 前驱

  1. ltag == 1 直接就是前驱
  2. ltag == 0 没办法直接找到，只能从头开始

5. 后续遍历前驱后继

左右根，子树只可能是前驱

5.1 前驱

  1. p->ltag == 1 直接就是前驱
  2. p->ltag == 0 如果 p 有右子树，那么右子树根就是前驱；没有右子树只有左子树，左子树根就是前驱
    image.png

5.2 后继

  1. p->rtag == 1
  2. p->rtag == 0 无法直接找到.

image.png