线索二叉树

树-线索二叉树

1. 定义：线索化了的二叉树称为线索二叉树。

2. 基本概念

   • 线索：在存储结构中，指向前驱和后继结点的指针叫做线索。

   • 线索链表:类似二叉树的链表存储结构中加上线索，组成的存储结构就是线索链表。

   • 线索化：对二叉树以某种次序进行遍历并且加上线索的过程。

3. 线索二叉树的存储结构

    typedef struct BiThrNode
    {
        TElemType data;		//数据域
        struct BiThrNode *LChild; //左孩子域
        int Ltag;  //左指针的标识域
        struct BiThrNode *RChild; //右孩子域
        int Rtag;  //右指针的标识域
    ｝BiThrTNode,*BiThrTree;  标识域解释如下:
   

   • Ltag = 0;LChild域指针指示结点的左孩子。
   • Ltag = 1;LChild域指针指示结点的遍历前驱。
   • Rtag = 0;RChild域指针指示结点的右孩子。
   • Rtag = 1;Rchild域指针指示结点的遍历后继。

4. 线索二叉树的作用

   • 对于经常需要遍历的二叉树，可以采用线索二叉树的存储结构，在常量阶上，线索二叉树的效率高于二叉树。

5. 线索二叉树的创建

6. 线索二叉树的线索化
   • DLR
   • LDR
   • LRD

7. 线索二叉树的遍历

   • DLR
   • LDR
   • LRD