数据结构与算法——第6章-树-对二叉树进行线索化(6.10.2)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
1.二叉树转化为线索二叉树
2.示例代码

二 二叉树转化为线索二叉树

1
2
3
4
5
6
将二叉树转化为线索二叉树，实质上是在遍历二叉树的过程中，将二叉链表中的空指针改为指向直接前趋或者直接后继的线索。

线索化的过程即为在遍历的过程中修改空指针的过程。

在遍历过程中，如果当前结点没有左孩子，需要将该结点的 lchild 指针指向遍历过程中的前一个结点，
所以在遍历过程中，设置一个指针（名为 pre ），时刻指向当前访问结点的前一个结点。

三 示例代码

3.1 代码实现（拿中序遍历为例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//中序对二叉树进行线索化
void InThreading(BiThrTree p) {
	//如果当前结点存在
	if (p) {
		InThreading(p->lchild);//递归当前结点的左子树，进行线索化
		//如果当前结点没有左孩子，左标志位设为 1，左指针域指向上一结点 pre
		if (!p->lchild) {
			p->Ltag=Thread;
			p->lchild=pre;
		}
		//如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
		if (!pre->rchild) {
			pre->Rtag=Thread;
			pre->rchild=p;
		}
		pre=p;//线索化完左子树后，让 pre 指针指向当前结点
		InThreading(p->rchild);//递归右子树进行线索化
	}
}

3.2 说明

1
2
注意：中序对二叉树进行线索化的过程中，在两个递归函数中间的运行程序，和之前介绍的中序遍历二叉树的输出函数的作用是相同的。
将中间函数移动到两个递归函数之前，就变成了前序对二叉树进行线索化的过程；后序线索化同样如此。

四 参考

  • C语言中文网—线索二叉树