线索二叉树

一、线索二叉树的相关概念

1、由于二叉树链表中空指针域的数量较多:具有n个结点的二叉链表中,一共有2n个指针域;因为n个结点中有n-1个孩子,即2n个指针域中,有n-1个用来指示结点的左右孩子,其余n+1个指针域为空。

2、线索二叉树的定义:如果某个结点的左孩子为空,则将空的左孩子指针域改为指向其前驱;如果某结点的右孩子为空,则将空的右孩子指针域改为指向其后继——这种改变指向的指针称为 “线索"。加上了线索的二叉树称为线索二叉树,对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。

3、研究线索二叉树的原因:当用二叉链表作为二叉树的存储结构时,可以很方便地找到某个结点的左右孩子;但一般情况下,无法直接找到该结点在某种遍历序列中的(因为在不同的遍历序列中,树结点的排列是不同的)前驱和后继结点。然而线索二叉树可以解决该问题。

二、线索二叉树的结构

1、为区分Irchid和rchild指针到底是指向孩子的指针,还是指向前驱或后继的指针,对二叉链表中每个结点增设两个标志域Itag和rtag,并约定:

Itag = 0                Ichild指向该结点的左孩子

Itag = 1                Ichild指向该结点的前驱

rtag = 0                rchild指向该结点的右孩子

rtag = 1                rchild指向该结点的后继

2、因此,结点的结构为:

3、因此线索二叉树的存储结构表示如下代码所示

typedef struct BiThrNode(

int data;

int ltag, rtag;

struct BiThrNode *lchild,rchild;) BiThrNode,*BiThrTree ;

三、先序线索二叉树

1、一个简单的例子,有助于理解,如下图所示:

四、实际构建线索二叉树

1、增设了一个头结点:

Itag=0, lchild指向根结点,

rtag=1, rchild指向遍历序列中最后一个结点,

遍历序列中第一个结点的Ic域和最后一 个结点的rc域都指向头结点。如下图所示: