线索二叉树

一、线索二叉树的概念

在二叉树中经常会求解某结点在某种次序下的前驱或后继结点,各结点在每种次序下的前驱、后继的差异较大。例如,图1中的二叉树的结点 D 在先序次序中的前驱、后继分别是 C、E;在中序次序中的前驱、后继分别是 E、F;在后序次序中的前驱、后继分别是 F、B。这种差异使得求解较为麻烦。

图1:
二叉树

如何实现这一问题的快速求解?对此有以下几种方法。

  1. 遍历——通过指定次序的遍历发现结点的前驱或后继。例如,为求图1中结点 D 的先序前驱,则对整个二叉树先序遍历,看看哪个结点之后是结点 D,则该结点就是 D 的先序前驱。以同样的方式可求出各结点在各种次序下的前驱和后继。由于这类方法太费时间(因为对每个结点的求解都要从头开始遍历二叉树),因此不宜采用。

  2. 增设前驱和后继指针——在每个结点中增设两个指针,分别指示该结点在指定次序下的前驱或后继。这样,就可使前驱和后继的求解较为方便,但这是以空间开销为代价的。是否存在既能少花费时间,又不用花费多余空间的方法呢?下面要介绍的第三种方法就是一种尝试。

  3. 利用二叉链表中的空指针域,将二叉链表中的空的指针域改为指向其前驱和后继。具体地说,就是将二叉树各结点中的空的左孩子指针域改为指向其前驱,空的右孩子指针域改为指向其后继。称这种新的指针为(前驱或后继)线索,所得到的二叉树被称为线索二叉树,将二叉树转变成线索二叉树的过程称为线索化。线索二叉树根据所选择的次序可分为先序、中序和后序线索二叉树。

例如,图1中二叉树的先序线索二叉树的二叉链表结构如图(a)所示,其中线索用虚线表示。

然而,仅仅按照这种方式简单地修改指针的值还不行,因为这将导致难以区分二叉链表中各结点的孩子指针和线索(虽然由图中可以「直观」地区分出来,但在算法中却不行)。例如,图(a)中结点 C 的 lchild 指针域所指向的结点是其左孩子还是其前驱?为此,在每个结点中需再引入两个区分标志 ltag 和 rtag,并且约定如下:

  • ltag=0:lchild 指示该结点的左孩子。

  • ltag=1:lchild 指示该结点的前驱。

  • rtag=0:rchild 指示该结点的右孩子。

  • rtag=1:rchild 指示该结点的后继。

未加区分标志的先序线索二叉树的二叉链表示例
先序线索二叉树示例

这样一来,图(a)中的二叉链表就变成了图(b)。这就是线索二叉树的内部存储结构形式。

为简便起见,通常将线索二叉树画成如下图所示的形式:

线索二叉树

二、线索的描述

由于线索二叉树存在先序、中序和后序线索二叉树,对于不同的线索树,其后继结点查找情况各不相同。

这里仅以中序线索二叉树为重点讲解。其结点的存储结构如下:

class ThreadNode: public BinTreeNode {
  public:
    int ltag, rtag;       //左右标志
    ThreadNode() {    //默认构造函数
      ltag = 0;
      rtag = 0;
    }
};

class ThreadTree {
  public:
    ThreadNode *root;      //根结点指针

    ThreadTree(){    //构造函数
      root = NULL;
    };

    ~ThreadTree(){  //析构函数
      DeleteTree(root);
    };

    void DeleteTree(ThreadNode *root);  //删除线索化二叉树

    void InThread(ThreadNode *root);   //非递归中序线索化二叉树

    void InThread(ThreadNode *root, ThreadNode *pre);

    //递归中序线索化二叉树
    void Inorder(ThreadNode * root);   //中序遍历中序线索化二叉树
};

三、线索的算法实现

给定一棵二叉树,要将其按中序线索化,具体做法是按中序遍历算法遍历此二叉树,在遍历的过程中用线索化来代替空指针。与二叉树的中序遍历算法类似,二叉树的线索化过程可以按递归和非递归算法来实现。

下面以中序线索二叉树为例,讨论线索二叉树的建立和遍历的实现算法。

(一)建立中序线索二叉树

建立线索二叉树,或者说对二叉树线索化,实质上就是遍历一棵二叉树。在遍历过程中,访问结点的操作是检查当前结点的左、右指针域是否为空,如果为空,将它们改为指向前驱结点或后继结点的线索。为实现这一过程,设指针 pre 始终指向刚访问过的结点,即若指针 root 指向当前结点,则 pre 指向它的前驱,以便增设线索。

//递归中序线索化二叉树
void ThreadTree::InThread(TheadNode *root) {

  static TheadNode * pre = NULL;

  if(root != NULL) {
    InThread(root->leftchild, pre);   //中序线索化左子树

    if(root->leftchild == NULL) {   //建立前驱线索
      root->ltag = 1;
      root->leftchild = pre;
    }
    
    //建立后继线索
    if((pre) && (pre->rightchild == NULL) {
      pre->rtag = 1;
      pre->rightchild = root;
    }

    pre = root;
    InThread(root->rightchild, pre);   //中序线索化右子树
  }
}

文中下划线部分的程序是对当前遍历到的结点进行线索化。将此算法和中序遍历的递归算法进行比较,得出结论:二叉树中序线索化算法实质就是中序遍历算法。根据前面遍历二叉树的知识,读者应该很容易解决如下问题。

  1. 如何实现二叉树的先序线索化算法(或后序线索化算法)?
  2. 如何实现各种线索化的非递归算法?

(二)中序线索二叉树的遍历算法

对二叉树进行遍历,如采用递归方法,则系统会利用栈保存调用时的中间变量或返回地址等信息。如采用非递归算法,则设计者需要自定义一个或多个栈保存必要的信息。对链式存储的二叉树进行遍历能不能不用栈?通过对线索二叉树进行分析可以发现,在先序和中序线索二叉树中,任一结点的后继很容易找到,不需要其他信息,更不需要栈。例如,在中序线索二叉树中,先找到中序遍历到的第一个结点,然后找此结点的后继,再找后继的后继,以此类推,直到所有结点被遍历到。以下是该算法的描述。

//对中序线索二叉树进行中序遍历
void ThreadTree::InOrder(TheadNode *root) {
  Threadode *p;

  if(root==NULL)  return;    //是否为空树
  p = root;

  while(p->ltag == 0) p = p->leftchild; //找最左下角的结点

  while(p) {       //访问当前结点并找出当前结点的
    //中序后继
    visit(p->data);    //访问当前结点
    p = InPostNode(p);     //寻找 p 的后继,此函数后面有描述
  }
}

四、线索二叉树上的运算

(一)在中序线索二叉树上查找任意结点的中序前驱结点

对于中序线索二叉树上的任一结点,寻找其中序的前驱结点,有以下两种情况。

(1)如果该结点的左标志为 1,那么其左指针域所指向的结点便是它的前驱结点。

(2)如果该结点的左标志为 0,则表明该结点有左孩子。根据中序遍历的定义,它的前驱结点是以该结点的左孩子为根结点的子树的最右结点,即沿着其左孩子的右指针链向下查找,当某结点的右标志为 1 时,它就是所要找的前驱结点。

在中序线索二叉树上寻找结点 p 的中序前驱结点的算法如下:

//在中序线索二叉树上寻找结点 p 的中序前驱结点
ThreadNode *ThreadTree::InPreNode(ThreadNode *p) {
  ThreadNode *pre;
  pre = p->leftchild;

  if(p->ltag != 1)
    while(pre->rtag == 0) pre = pre->rightchild;

  return(pre);
}

(二)在中序线索二叉树上查找任意结点的中序后继结点

对于中序线索二叉树上的任一结点,寻找其中序的后继结点,有以下两种情况。

(1)如果该结点的右标志为 1,那么其右指针域所指向的结点便是它的后继结点。

(2)如果该结点的右标志为 0,则表明该结点有右孩子。根据中序遍历的定义,它的后继结点是以该结点的右孩子为根结点的子树的最左结点,即沿着其右孩子的左指针链向下查找,当某结点的左标志为 1 时,它就是所要找的后继结点。

在中序线索二叉树上寻找结点 p 的中序后继结点的算法如下:

//在中序线索二叉树上寻找结点 p 的中序后继结点
ThreadNode *ThreadTree::InPostNode(ThreadNode *p) {
  ThreadNode *post;
  post = p->rightchild;

  if(p->rtag != 1)
    while(post->ltag == 0) post = post->leftchild;

  return(post);
}

以上给出的仅是在中序线索二叉树中寻找某结点的前驱结点和后继结点的算法。在先序线索二叉树中寻找结点的后继结点,以及在后序线索二叉树中寻找结点的前驱结点,可以采用同样的方法分析和实现。

值得注意的是,在先序线索二叉树中寻找某结点的前驱结点及在后序线索二叉树中寻找某结点的后继结点不太方便,必须知道某结点的双亲才能求解。

(三)在中序线索二叉树上查找值为 x 的结点

利用在中序线索二叉树上寻找后继结点和前驱结点的算法,就可以遍历到二叉树的所有结点。例如,先找到按某序遍历的第一个结点,再依次查询其后继;或先找到按某序遍历的最后一个结点,再依次查询其前驱。这样,既不用栈也不用递归,就可以访问到二叉树的所有结点。

在中序线索二叉树上查找值为 x 的结点,实质上就是在线索二叉树上进行遍历,边编历边比较。下面给出其算法:

//在以 root 为头结点的中序线索二叉树中查找值为 x 的结点
ThreadNode *ThreadTree::Search(ThreadNode *root, DataType x) {
  ThreadNode *p;

  if (root == NULL) return NULL;

  p = root;

  while(p->ltag == 0) p = p->lchild;
  while(p && p->data != x) p = InPostNode(p);

  if(!p){
    cout << "Not Found the data!" <<endl;
    return NULL;
  }
  else return p;
}

(四)在中序线索二叉树上的更新

线索二叉树的更新,是指在线索二叉树中插入一个结点或者删除一个结点。一般情况下,这些操作有可能破坏原来已有的线索,因此,在修改指针时,还需要对线索做相应的修改。一般来说,这个过程的代价几乎与重新进行线索化相同。这里仅讨论一种比较简单的情况,即在中序线索二叉树中插入一个结点 p,使它成为结点 s 的右孩子。

下面分两种情况来分析。

  1. 若 s 的右子树为空,如图1(a)所示,则插入结点 p 之后成为图1(b)所示的情形。在这种情况下,s 的后继将成为 p 的中序后继,s 成为 p 的中序前驱,而 p 成为 s 的右孩子。二叉树中其他部分的指针和线索不发生变化。

  2. 若 s 的右子树非空,如图2(a)所示,插入结点 p 之后如图2(b)所示。s 原来的右子树变成 p 的右子树。由于 p 没有左子树,故 s 成为 p 的中序前驱,p 成为 s 的右孩子。又由于 s 原来的后继成为 p 的后继,因此还要将 s 原来的后继的左线索(原指向 s)改为指向 p。

图1:
中序线索二叉树更新位置右子树为空
图2:
中序线索二叉树更新位置右子树不为空

下面给出上述操作的算法:

//在中序线索二叉树中插入结点 p,使其成为结点 s 的右孩子
void ThreadTree::InsertThrRight(ThreadNode *s, ThreadNode *p) {
  ThreadNode w;
  p->rchild = s->rchild;
  p->rtag = s->rtag;
  p->lchild = s;
  p->ltag = 1;   //将 s 变为 p 的中序前驱

  s->rchild = p;

  s->rtag = 0;   //p 成为 s 的右孩子

  if(p->rtag == 0){
    //当 s 原来右子树不空时,找到 s 的后继 w,变 w 为 p 的后继,
    //p 为 w 的前驱
    w = InPostNode(p);
    w->lchild = p;
  }
}
用户头像
登录后发表评论