线索二叉树

简介 通过考察各种二叉链表,不管二叉树的形态如何,空链域的个数总是多过非空链域的个数。准确的说,n各结点的二叉链表共有2n个链域,非空链域为n-1个,但其中的空链域却有n+1个。如下图所示。     因此,提出了一种方法,利用原来的空链域存放指针,指向树中其他结点。这种指针称为线索。     记ptr指向二叉链表中的一个结点,以下是建立线索的规则:  &nbs

 通过考察各种二叉链表,不管二叉树的形态如何,空链域的个数总是多过非空链域的个数。准确的说,n各结点的二叉链表共有2n个链域,非空链域为n-1个,但其中的空链域却有n+1个。如下图所示。

    因此,提出了一种方法,利用原来的空链域存放指针,指向树中其他结点。这种指针称为线索。

    记ptr指向二叉链表中的一个结点,以下是建立线索的规则:

    (1)如果ptr->lchild为空,则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱;

    (2)如果ptr->rchild为空,则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继;

    显然,在决定lchild是指向左孩子还是前驱,rchild是指向右孩子还是后继,需要一个区分标志的。因此,我们在每个结点再增设两个标志域ltag和rtag,注意ltag和rtag只是区分0或1数字的布尔型变量,其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。

    其中:

    (1)ltag为0时指向该结点的左孩子,为1时指向该结点的前驱;

    (2)rtag为0时指向该结点的右孩子,为1时指向该结点的后继;

    (3)因此对于上图的二叉链表图可以修改为下图的样子。

上一篇:B-树、B+树、B*树介绍

下一篇:KMP

本文转自:https://www.cnblogs.com/lishanlei/p/10707834.html
新加评论 评论标题: