线索二叉树的创建及遍历(C语言实现)

通过前面对二叉树的学习，了解到二叉树本身是一种非线性结构，采用任何一种遍历二叉树的方法，都可以得到树中所有结点的一个线性序列。在这个序列中，除第一个结点外，每个结点都有自己的直接前趋；除最后一个结点外，每个结点都有一个直接后继。

图1 满二叉树

例如，图 1 采用先序遍历的方法得到的结点序列为：1 2 4 5 3 6 7，在这个序列中，结点 2 的直接前趋结点为 1，直接后继结点为 4。什么是线索二叉树如果算法中多次涉及到对二叉树的遍历，普通的二叉树就需要使用栈结构做重复性的操作。

}不难分析，上述算法的时间复杂度同样为 o(n) 7．6．3 二叉树的线索化算法对--x 树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程， 因此， 二叉树的线索化过程只能在对二叉树的遍历过程中进行。如果二叉树需要经常遍历或查找结点是需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二叉树的一些统计和操作(比如结点数统计、左右子树对换等等)，判断某棵二叉树是否二叉排序树，以上这些都要求能用递归的和非递归的算法解决，特别要重视非递归的算法，线索化后二叉树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出huffman编码等等。

但是这种方式会降低树存储结构的存储密度。而对于二叉树来讲，其本身还有很多未利用的空间。

存储密度指的是数据本身所占的存储空间和整个结点结构所占的存储量之比。

1．在具有 n 个叶子结点的严格二叉树中，结点总数为（ ） a．2n+1 b．2n c．2n-1 2．除根结点外，树上每个结点（ ） a．可有任意多个孩子、任意多个双亲 b．可有任意多个孩子、一个双亲 c．可有一个孩子、任意多个双亲 d．只有一个孩子、一个双亲 3．具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。双向链表的每个结点除含有数据域外，还有两个指针域，分别指向直接前驱结点和直接后继结点。所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。

规律：在有 n 个结点的二叉链表中必定存在 n+1 个空指针域。

线索二叉树实际上就是使用这些空指针域来存储结点之间前趋和后继关系的一种特殊的二叉树。

线索二叉树中，如果结点有左子树，则 lchild 指针域指向左孩子，否则 lchild 指针域指向该结点的直接前趋；同样，如果结点有右子树，则 rchild 指针域指向右孩子，否则 rchild 指针域指向该结点的直接后继。

为了避免指针域指向的结点的意义混淆，需要改变结点本身的结构，增加两个标志域，如图 2 所示。

图2 线索二叉树中的结点结构

LTag 和 RTag 为标志域。实际上就是两个布尔类型的变量：

结点结构代码实现：

#define TElemType int//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum PointerTag{
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode{
    TElemType data;//数据域
    struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
   
    PointerTag Ltag,Rtag;//标志域，枚举类型
}BiThrNode,*BiThrTree;

表示二叉树时，使用图 2 所示的结点结构构成的二叉链表，被称为线索链表；构建的二叉树称为线索二叉树。

线索链表中的“线索”，指的是链表中指向结点前趋和后继的指针。二叉树经过某种遍历方法转化为线索二叉树的过程称为线索化。

对二叉树进行线索化将二叉树转化为线索二叉树，实质上是在遍历二叉树的过程中，将二叉链表中的空指针改为指向直接前趋或者直接后继的线索。

线索化的过程即为在遍历的过程中修改空指针的过程。

在遍历过程中，如果当前结点没有左孩子，需要将该结点的 lchild 指针指向遍历过程中的前一个结点，所以在遍历过程中，设置一个指针（名为 pre ），时刻指向当前访问结点的前一个结点。

代码实现（拿中序遍历为例）：

//中序对二叉树进行线索化
void InThreading(BiThrTree p){
    //如果当前结点存在
    if (p) {
        InThreading(p->lchild);//递归当前结点的左子树，进行线索化
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre
        if (!p->lchild) {
            p->Ltag=Thread;
            p->lchild=pre;
        }
        //如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
        if (!pre->rchild) {
            pre->Rtag=Thread;
            pre->rchild=p;
        }
        pre=p;//线索化完左子树后，让pre指针指向当前结点
        InThreading(p->rchild);//递归右子树进行线索化
    }
}

利用先序递归遍历算法创建二叉树并输出该二叉树的层次遍历序列。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。考查的重点有：链表，二叉树前序、中序、后序遍历（递归，非递归），二叉树结点、层次的计算，树转二叉树，各种排序算法（冒泡排序。

将中间函数移动到两个递归函数之前，就变成了前序对二叉树进行线索化的过程；后序线索化同样如此。使用线索二叉树遍历图 3 中是一个按照中序遍历建立的线索二叉树。其中，实线表示指针，指向的是左孩子或者右孩子。虚线表示线索，指向的是该结点的直接前趋或者直接后继画出先序线索二叉树。

图 3 线索二叉树

zigbee_buffer类型的缓冲区是报文缓冲区，其内部结构如图2所示，该结构包括两个指针，两个长度域，其中next 域指针指向下一个zigbee_buffer的缓冲块，pdata域指向...。假设返回的第i-1个结点为*p，然后令新结，点*s的指针域指向*p的后继结点，再令结点*p的指针域指向新插入的结点*s。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。

(16)在某二叉树中，若结点 a 有左孩子 y 和右孩子 x，则在结点的前序序列、中序序 列和后序序列中，结点&mdash。1.若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、&hellip。对于深度遍历，先序序列就是“根左右”，中序序列就是“左根右”，后序序列就是“左右根”。

4、层序遍历：从根节点出发，依次访问左右孩子结点，再从左右孩子出发，依次它们的孩子结点，直到节点访问完毕。树{树的基本概念(结点(结点的度)、层次、深度(高)、有序树与无序树、森林)、树的存储结构(双亲表示法、孩子表示法、孩子兄弟表示法)、二叉树(二叉树的类型(特殊二叉树、满二叉树、完全二叉树)、二叉树的存储结构、二叉树的遍历(前序遍历、中序遍历、后序遍历、层序遍历)、二叉树的建立(树、森林、二叉树的转换、赫夫曼树、赫夫曼编码(压缩算法))、查找二叉树、(平衡树、红黑树))}。第4章 树：树和森林的概念及其表示，二叉树，二叉树性质，二叉树表示，二叉树遍历与树游标， lvr, lrv, vlr，中序游标，按层次遍历，线索二叉树，线索，中序遍历线索二叉树，将结点插入线索二叉树，选择树，胜者树，败者树，森林的二叉树表示及遍历。

后序遍历中找后继结点需要分为 3 种情况：

如果该结点是二叉树的根，后继结点为空；

如果该结点是父结点的右孩子（或者是左孩子，但是父结点没有右孩子），后继结点是父结点；

如果该结点是父结点的左孩子，且父结点有右子树，后继结点为父结点的右子树在后序遍历列出的第一个结点。

二叉树的三种遍历方法：先序，中序和后序，线索二叉树，线索化后二叉树的遍历方法。树{树的基本概念(结点(结点的度)、层次、深度(高)、有序树与无序树、森林)、树的存储结构(双亲表示法、孩子表示法、孩子兄弟表示法)、二叉树(二叉树的类型(特殊二叉树、满二叉树、完全二叉树)、二叉树的存储结构、二叉树的遍历(前序遍历、中序遍历、后序遍历、层序遍历)、二叉树的建立(树、森林、二叉树的转换、赫夫曼树、赫夫曼编码(压缩算法))、查找二叉树、(平衡树、红黑树))}。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二叉树的一些统计和操作(比如结点数统计、左右子树对换等等)，判断某棵二叉树是否二叉排序树，以上这些都要求能用递归的和非递归的算法解决，特别要重视非递归的算法，线索化后二叉树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出huffman编码等等。

遍历线索二叉树非递归代码实现：

//中序遍历线索二叉树
void InOrderThraverse_Thr(BiThrTree p)
{
    while(p)
    {
        //一直找左孩子，最后一个为中序序列中排第一的
        while(p->Ltag == Link){
            p = p->lchild;
        }
        printf("%c ", p->data);  //操作结点数据
        //当结点右标志位为1时，直接找到其后继结点
        while(p->Rtag == Thread && p->rchild !=NULL){
            p = p->rchild;
            printf("%c ", p->data);
        }
        //否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
        p = p->rchild;
    }
}

整节完整代码（可运行）

#include <stdio.h>
#include <stdlib.h>
#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum {
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode{
    TElemType data;//数据域
    struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
    PointerTag Ltag,Rtag;//标志域，枚举类型
}BiThrNode,*BiThrTree;
BiThrTree pre=NULL;
//采用前序初始化二叉树
//中序和后序只需改变赋值语句的位置即可
void CreateTree(BiThrTree * tree){
    char data;
    scanf("%c",&data);
    if (data!='#'){
        if (!((*tree)=(BiThrNode*)malloc(sizeof(BiThrNode)))){
            printf("申请结点空间失败");
            return;
        }else{
            (*tree)->data=data;//采用前序遍历方式初始化二叉树
            CreateTree(&((*tree)->lchild));//初始化左子树
            CreateTree(&((*tree)->rchild));//初始化右子树
        }
    }else{
        *tree=NULL;
    }
}
//中序对二叉树进行线索化
void InThreading(BiThrTree p){
    //如果当前结点存在
    if (p) {
        InThreading(p->lchild);//递归当前结点的左子树，进行线索化
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre
        if (!p->lchild) {
            p->Ltag=Thread;
            p->lchild=pre;
        }
        //如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
        if (pre&&!pre->rchild) {
            pre->Rtag=Thread;
            pre->rchild=p;
        }
        pre=p;//pre指向当前结点
        InThreading(p->rchild);//递归右子树进行线索化
    }
}
//中序遍历线索二叉树
void InOrderThraverse_Thr(BiThrTree p)
{
    while(p)
    {
        //一直找左孩子，最后一个为中序序列中排第一的
        while(p->Ltag == Link){
            p = p->lchild;
        }
        printf("%c ", p->data);  //操作结点数据
        //当结点右标志位为1时，直接找到其后继结点
        while(p->Rtag == Thread && p->rchild !=NULL)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        //否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
        p = p->rchild;
    }
}
int main() {
    BiThrTree t;
    printf("输入前序二叉树:\n");
    CreateTree(&t);
    InThreading(t);
    printf("输出中序序列:\n");
    InOrderThraverse_Thr(t);
    return 0;
}

运行结果

输入前序二叉树:

124###35##6##

输出中序序列:

4 2 1 5 3 6

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-101439-1.html