数据结构与算法——第6章-树-双向线索二叉树(6.11.1)

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

一 概述

1
2
3
1.双向线索链表
2.双向线索二叉树的实现过程
3.示例代码

二 双向线索链表

1
2
3
4
5
6
7
8
9
通过前一节对线索二叉树的学习，其中，在遍历使用中序序列创建的线索二叉树时，对于其中的每个结点，
即使没有线索的帮助下，也可以通过中序遍历的规律找到直接前趋和直接后继结点的位置。


也就是说，建立的线索二叉链表可以从两个方向对结点进行中序遍历。
通过前一节的学习，线索二叉链表可以从第一个结点往后逐个遍历。
但是起初由于没有记录中序序列中最后一个结点的位置，所以不能实现从最后一个结点往前逐个遍历。

双向线索链表的作用就是可以让线索二叉树从两个方向实现遍历。

三 双向线索二叉树的实现过程

3.1 说明

1
2
3
4
5
6
7
8
在线索二叉树的基础上，额外添加一个结点。此结点的作用类似于链表中的头指针，数据域不起作用，
只利用两个指针域（由于都是指针，标志域都为 0 ）。

左指针域指向二叉树的树根，确保可以正方向对二叉树进行遍历；
同时，右指针指向线索二叉树形成的线性序列中的最后一个结点。

这样，二叉树中的线索链表就变成了双向线索链表，既可以从第一个结点通过不断地找后继结点进行遍历，
也可以从最后一个结点通过不断找前趋结点进行遍历。

3.2 图示

四 示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//建立双向线索链表
void InOrderThread_Head(BiThrTree *h, BiThrTree t) {
	//初始化头结点
	(*h) = (BiThrTree)malloc(sizeof(BiThrNode));
	if((*h) == NULL) {
		printf("申请内存失败");
		return ;
	}
	(*h)->rchild = *h;
	(*h)->Rtag = Link;
	//如果树本身是空树
	if(!t) {
		(*h)->lchild = *h;
		(*h)->Ltag = Link;
	} else {
		pre = *h;//pre 指向头结点
		(*h)->lchild = t;//头结点左孩子设为树根结点
		(*h)->Ltag = Link;
		InThreading(t);//线索化二叉树，pre 结点作为全局变量，线索化结束后，pre 结点指向中序序列中最后一个结点
		pre->rchild = *h;
		pre->Rtag = Thread;
		(*h)->rchild = pre;
	}
}

五 参考

  • C语言中文网—双向线索二叉树详解