【数据结构之线索二叉树】线索二叉树的原理及创建

来源:行小观 二十二画程序员 日期:2021-04-29

本文转载自微信公众号「二十二画程序员」,作者行小观。转载本文请联系二十二画程序员公众号。  

 1. 为什么要用到线索二叉树?

我们先来看看普通的二叉树有什么缺点。下面是一个普通二叉树(链式存储方式):

一颗普通二叉树

乍一看,会不会有一种违和感?整个结构一共有 7 个结点,总共 14 个指针域,其中却有 8 个指针域都是空的。对于一颗有 n 个结点的二叉树而言,总共会有 n+1 个空指针域,这个规律使用所有的二叉树。

这么多的空指针域是不是显得很浪费?我们学习数据结构和算法的重点就是在想法设法地提高时间效率和空间利用率。这么多的指针域就这么白白浪费了,太败家了!

所以我们要想法子好好利用它们,利用它们来帮助我们更好地使用二叉树这个数据结构。

那么如何利用呢?

前面已经强调过很多次了,遍历二叉树的实质是将二叉树中非线性结构的结点转化为线性的序列,然后才能方便我们遍历。

比如上图的中序遍历序列为:DBGEACF。

对于一个线性序列(线性表)来说,它有直接前驱和直接后继的概念(在【什么是线性表?】中介绍过)。比如在中序遍历序列中,B 的直接前驱为 D,直接后继为 G。

我们之所以能知道 B 的直接前驱和直接后继,是因为我们按照中序遍历的算法,把二叉树的中序遍历序列写出来了,然后根据这个顺序序列说谁的前驱是谁、后继是谁。

直接前驱和直接后继是不能完全直接通过二叉树得到的,因为二叉树中只有双亲和孩子结点之间的直接关系,即二叉树的结点指针域中只存储了其孩子结点的地址。

现在的需求是,我想能直接从二叉树上得到某结点在中序遍历方式下的直接前驱和直接后继。

这时候就需要用到线索二叉树了。

2. 什么是线索二叉树?

当然,我们肯定需要借助结点的指针域来保存直接前驱和直接后继的地址。

其实,在上图的普通二叉树中(以中序遍历得到的序列),部分结点(指针域不为空的结点)是可以找到其直接前驱或后继的,比如结点 E 的左孩子 G 就是结点 E 的直接前驱;结点 A 的右孩子 C 就是结点 A 的直接后继。

但部分结点(指针域为空)是行不通的,比如结点 G 的直接后继是 E,直接前驱是 B,但在二叉树中却不能得出这样的结论。怎么办呢?我们注意到,结点 G 的两个指针域都为 NULL,并未被利用,那么我们使用这两个指针,分别指向其前驱和后继不就好了吗?

中序遍历下结点G的指向情况

实在是两全其美,天作之合!但是问题并没有解决!

因为我们是利用空指针域来指向前驱或后继的,对于那些指针域不为空的结点,这样是矛盾的,比如结点 E 和结点 B。

既然有矛盾,那么我们就发现产生矛盾的根源,解决矛盾。

产生矛盾的根源是:结点的指针域为空和不为空时,指针的指向矛盾。即,指针不为空时指向孩子和指针为空时指向前驱或后继之间的矛盾。

那么我们对症下药,把指针域为空和不为空给区分出来,清晰地告诉指针:不为空时指向孩子,为空时指向前驱或后继。这就需要我们给两个指针各添加一个标志位。

线索二叉树的结点

并约定以下规则:

  • left_flag == 0 时,指针 left_child 指向左孩子
  • left_flag == 1 时,指针 left_child 指向直接前驱
  • right_flag == 0 时,指针 right_child 指向右孩子
  • right_flag == 1 时,指针 right_child 指向直接前驱

二叉树的结点要有所变化:

  1. /*线索二叉树的结点的结构体*/ 
  2. typedef struct Node { 
  3.     char data; //数据域 
  4.     struct Node *left_child; //左指针域 
  5.     int left_flag; //左指针标志位 
  6.     struct Node *right_child; //右指针域 
  7.     int right_flag; //右指针标志位 
  8. } TTreeNode; 
 1/4    1 2 3 4 下一页 尾页
    A+
声明:本文转载自其它媒体,转载目的在于传递更多信息,并不代表赞同其观点和对其真实性负责。