数据结构与算法-树与二叉树

一、树的一些术语

树的构成

  1. 结点：树中的一个独立单元。包含一个数据元素及若干指向其他子树的分支。例如，A, B, C, D 等都是结点.

  2. 结点的度：结点拥有的子树数量称谓结点的度，例如 A 的度是 3, C 的度为 1, D 的度为 3, F 的度为 0

  3. 树的度：数的度是树内各结点度的最大值，例如，上图中的应该是 3

  4. 叶子：度为 0 的结点称谓叶子或终端结点，例如，K, J, F, G, M,I,J 都是树的叶子

  5. 非终端结点：度不为 0 的结点称为非终端结点或分支结点。除了根结点以外，非终端结点也称为内部结点

  6. 双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲，例如，B 的双亲为 A, B的孩子有 E 和 F

  7. 兄弟：同一个双亲的孩子之间称为兄弟结点，例如 H，I 和 J 互为兄弟

  8. 祖先：从根到该结点所经历的分支上的所有结点，例如，M 的祖先为 A, D, H。

  9. 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。例如，B 的子孙为 E, F

  10. 层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一层次等于双亲结点的层次加 1

  11. 堂兄弟：双亲在同一层的节点互为堂兄弟。例如，结点 G 与 E, F, H,I, J 互为堂兄弟。

  12. 有序树和无序树：如果将树的结点的各子树看成从左到右是有次序的（即不能互换）则称为该树为有序树；否则是无序树，在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。什么叫有序树，就类似在家语中第一房太太，到第五房太太以及孩子是有顺序的。这样存在顺序关系叫有序树

  13. 节点的高度：节点到叶子节点的最长路径（边数）

  14. 节点的深度：根结点到这个结点所经历的边的个数

  15. 节点的层数：节点的深度-1

  16. 树的高度：根结点的高度

二、二叉树

简单地理解，满足以下两个条件的树就是二叉树：

  • 1.本身是有序树；

  • 2.树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；


    树的五种形态

    斜树

二叉树（Binary Tree）是 n (n>=0) 个结点所构成的集合。它或为空树（n=0) 或为非空树 T

    1. 有且仅有一个称之为根结点
    1. 除了根结点以外的其余结点分为 2 个互不相交的子集 T1, T2. 分别称为 T 的左子树和右子树，且 T1 和 T2 本身都是二叉树

二叉树的特性

    1. 二叉树每个结点至多只有 2 颗子树（二叉树中不存在度大于 2 的结点）。所以二叉树中不存在大于 2 的结点

注意：不是只有 2 个子树，而是最多只有，如果二又树中没有子树或者只有一颖树是可以的

    1. 二叉树的子树有左右之分，具次序不能任意倒类似：就像人的双手，双脚。有顺序之分
    1. 即使只有一棵树，也需要区分是左子树还是右子树。类似：就像你在生活中，摔伤了手。伤的是左手还是右手，对你的生活影响都是完全不同的，

二叉树的性质：

  • 1.二叉树中，第 i 层最多有 2i-1 个结点。
  • 2.如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
  • 3.二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

二叉树还可以继续分类，衍生出满二叉树和完全二叉树。

满二叉树

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

满二叉树除了满足普通二叉树的性质，还具有以下性质：

  • 1.满二叉树中第 i 层的节点数为 2i-1 个。

  • 2.深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。

  • 3.满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。

  • 4.具有 n 个节点的满二叉树的深度为 log2(n+1)。[图片上传失败...(image-e70804-1589734352458)]

    <figcaption></figcaption>

完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。

⌊log2n⌋ 表示取小于 log2n 的最大整数。例如，⌊log24⌋ = 2，而 ⌊log25⌋ 结果也是 2。

对于任意一个完全二叉树来说，如果将含有的结点按照从上至下和从左至右的顺序从1开始编号，对于任意一个结点 i ，完全二叉树还有以下几个结论成立：

  • 1.当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
  • 2.如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
  • 3.如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。

对一颗具有 n 个结点的二叉树按层序编号，如果编号为（1=< i <=n）的结点与同样深度的满二叉树中编号为 i 的结点二又树中位置完全相同。则这颖二又树称为完全二叉树

    1. 首先“完全”和“满“的差异，满二叉树一定是一个完全二叉树,完全二叉树不一定是满的。
    1. 完全二又树的所有结点和同样深度的满二又树，它们按照层序编号相同的结点一一对应。这里有一个关键词是按层序编号

完全二叉树的特点

    1. 叶子结点只能出现在最下两层
    1. 最下层的叶子一定集中在左部连接
    1. 倒数第二层，若有叶子节点，一定都在右部连续位置
    1. 如果结点度为 1, 则该结点只有左孩子，既不存在只有右子树的情况
    1. 同样结点数的二叉树，完全二又树的深度最小；

二叉树的4种遍历方法（根据根节点的遍历顺序命名）

  • 1.前序遍历（先序遍历）
前序遍历
  • 2.中序遍历
中序遍历

  • 3.后序遍历


    后序遍历

  • 4.层序遍历


    层序遍历

三、二叉树的顺序存储实现

#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */
#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */

typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int CElemType;      /* 树结点的数据类型，目前暂定为整型 */
typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点  */
CElemType Nil = 0;   /*设整型以0为空 或者以 INT_MAX(65535)*/

typedef struct {
    int level; //结点层
    int order; //本层的序号(按照满二叉树给定序号规则)
}Position;

#pragma mark -- 二叉树的基本操作
//6.1 visit
Status visit(CElemType c){
    printf("%d ",c);
    return OK;
}

//6.2 构造空二叉树T,因为T是固定数组,不会改变.
Status InitBiTree(SqBiTree T){

    for (int i = 0; i < MAX_TREE_SIZE; i++) {
        //将二叉树初始化值置空
        T[i] = Nil;
    }

    return OK;
}

//6.3 按层序次序输入二叉树中的结点值(字符型或整型),构造顺序存储的二叉树T
Status CreateBiTree(SqBiTree T){
    int i = 0;

    //printf("按层序输入结点的值(整型),0表示空结点, 输入999结束.结点数<=%d\n",MAX_TREE_SIZE);
    /*
     1      -->1
     2     3   -->2
     4  5  6   7 -->3
     8  9 10       -->4

     1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
     */

    while (i < 10) {
        T[i] = i+1;
        printf("%d ",T[i]);

        //结点不为空,且无双亲结点
        if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
            printf("出现无双亲的非根结点%d\n",T[i]);
            exit(ERROR);
        }

        i++;

    }

    //将空赋值给T的后面的结点
    while (i < MAX_TREE_SIZE) {
        T[i] = Nil;
        i++;
    }

    return OK;
}

//技巧:
//如果大家想要2个函数的结果一样,但是目的不同;
//在顺序存储结构中, 两个函数完全一样的结果
#define ClearBiTree InitBiTree

/*6.4 判断二叉树是否为空
 初始条件: 二叉树已存在
 操作结果: 若T为空二叉树,则返回TRUE,否则返回FALSE;
 */
Status BiTreeEmpty(SqBiTree T){
    //根结点为空,则二叉树为空
    if (T[0] == Nil)
        return TRUE;

    return FALSE;
}

/*6.5 获取二叉树的深度
 初始条件: 二叉树已存在
 操作结果: 返回二叉树T深度;
 */
int BiTreeDepth(SqBiTree T){

    int j = -1;
    int i;

    //找到最后一个结点
    //MAX_TREE_SIZE -> 100 -> 10 目的找到最后一个结点10的位置
    for (i = MAX_TREE_SIZE-1 ; i>=0; i--) {
        if (T[i] != Nil)
            break;
    }

    do {
        j++;
    } while ( powl(2, j) <= i); //计算2的次幂

    return j;
}

/*6.6 返回处于位置e(层,本层序号)的结点值
 初始条件: 二叉树T存在,e是T中某个结点(的位置)
 操作结构: 返回处于位置e(层,本层序号)的结点值
 */
CElemType Value(SqBiTree T,Position e){

    /*
     Position.level -> 结点层.表示第几层;
     Position.order -> 本层的序号(按照满二叉树给定序号规则)
     */

    //pow(2,e.level-1) 找到层序
    printf("%d\n",(int)pow(2,e.level-1));

    //e.order
    printf("%d\n",e.order);

    //4+2-2;
    return T[(int)pow(2, e.level-1)+e.order-2];

}

/*6.7 获取二叉树跟结点的值
 初始条件: 二叉树T存在
 操作结果: 当T不空,用e返回T的根, 返回OK; 否则返回ERROR
 */
Status Root(SqBiTree T,CElemType *e){
    if (BiTreeEmpty(T)) {
        return ERROR;
    }

    *e = T[0];
    return OK;
}

/*
 6.8 给处于位置e的结点赋值
 初始条件: 二叉树存在,e是T中某个结点的位置
 操作结果: 给处于位置e的结点赋值Value;
 */
Status Assign(SqBiTree T,Position e,CElemType value){

    //找到当前e在数组中的具体位置索引
    int i = (int)powl(2, e.level-1)+e.order -2;

    //叶子结点的双亲为空
    if (value != Nil &&  T[(i+1)/2-1] == Nil) {
        return ERROR;
    }

    //给双亲赋空值但是有叶子结点
    if (value == Nil && (T[i*2+1] != Nil || T[i*2+2] != Nil)) {
        return  ERROR;
    }

    T[i] = value;
    return OK;
}

/*
 6.9 获取e的双亲;
 初始条件: 二叉树存在,e是T中的某一个结点
 操作结果: 若e是T的非根结点, 则返回它的双亲,否则返回"空"
 */
CElemType Parent(SqBiTree T, CElemType e){

    //空树
    if (T[0] == Nil) {
        return Nil;
    }

    for (int i = 1 ; i < MAX_TREE_SIZE; i++) {
        //找到e
        if (T[i] == e) {
            return T[(i+1)/2 - 1];
        }
    }

    //没有找到
    return Nil;

}

/*
 6.10 获取某个结点的左孩子;
 初始条件:二叉树T存在,e是某个结点
 操作结果:返回e的左孩子,若e无左孩子,则返回"空"
 */
CElemType LeftChild(SqBiTree T,CElemType e){

    //空树
    if (T[0] == Nil) {
        return Nil;
    }
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        //找到e
        if (T[i] == e) {
            return T[i*2+1];
        }
    }

    //没有找到
    return Nil;

}

/*
 6.11 获取某个结点的右孩子;
 初始条件:二叉树T存在,e是某个结点
 操作结果:返回e的左孩子,若e无左孩子,则返回"空"
 */
CElemType RightChild(SqBiTree T,CElemType e){

    //空树
    if (T[0] == Nil) {
        return Nil;
    }
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        //找到e
        if (T[i] == e) {
            return T[i*2+2];
        }
    }

    //没有找到
    return Nil;

}

/*
 6.12 获取结点的左兄弟
 初始条件:  二叉树T存在,e是T中某个结点
 操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂
 */
CElemType LeftSibling(SqBiTree T,CElemType e)
{
    /* 空树 */
    if(T[0]==Nil)
        return Nil;

    for(int i=1;i<=MAX_TREE_SIZE-1;i++)
    /* 找到e且其序号为偶数(是右孩子) */
        if(T[i]==e && i%2==0)
            return T[i-1];

    return Nil; /* 没找到e */
}

/* 6.13 获取结点的右兄弟
 初始条件: 二叉树T存在,e是T中某个结点
 操作结果: 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂
 */
CElemType RightSibling(SqBiTree T,CElemType e)
{
    /* 空树 */
    if(T[0]==Nil)
        return Nil;

    for(int i=1;i<=MAX_TREE_SIZE-1;i++)
    /* 找到e且其序号为奇数(是左孩子) */
        if(T[i]==e && i%2==1)
            return T[i+1];

    return Nil; /* 没找到e */
}

#pragma mark -- 二叉树的遍历

/*
 6.14 层序遍历二叉树
 */
void LevelOrderTraverse(SqBiTree T){

    int i = MAX_TREE_SIZE-1;

    //找到最后一个非空结点的序号
    while (T[i] == Nil) i--;

    //从根结点起,按层序遍历二叉树
    for (int j = 0; j <= i; j++)
        //只遍历非空结点
        if (T[j] != Nil)
            visit(T[j]);

    printf("\n");
}

/*
 6.15 前序遍历二叉树
 */
void PreTraverse(SqBiTree T,int e){

    //打印结点数据
    visit(T[e]);

    //先序遍历左子树
    if (T[2 * e + 1] != Nil) {
        PreTraverse(T, 2*e+1);
    }
    //最后先序遍历右子树
    if (T[2 * e + 2] != Nil) {
        PreTraverse(T, 2*e+2);
    }
}

Status PreOrderTraverse(SqBiTree T){

    //树不为空
    if (!BiTreeEmpty(T)) {
        PreTraverse(T, 0);
    }
    printf("\n");
    return  OK;
}

/*
 6.16 中序遍历
 */
void InTraverse(SqBiTree T, int e){

    /* 左子树不空 */
    if (T[2*e+1] != Nil)
        InTraverse(T, 2*e+1);

    visit(T[e]);

    /* 右子树不空 */
    if (T[2*e+2] != Nil)
        InTraverse(T, 2*e+2);
}

Status InOrderTraverse(SqBiTree T){

    /* 树不空 */
    if (!BiTreeEmpty(T)) {
        InTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

/*
 6.17 后序遍历
 */
void PostTraverse(SqBiTree T,int e)
{   /* 左子树不空 */
    if(T[2*e+1]!=Nil)
        PostTraverse(T,2*e+1);
    /* 右子树不空 */
    if(T[2*e+2]!=Nil)
        PostTraverse(T,2*e+2);

    visit(T[e]);
}
Status PostOrderTraverse(SqBiTree T)
{
    if(!BiTreeEmpty(T)) /* 树不空 */
        PostTraverse(T,0);
    printf("\n");
    return OK;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("二叉树顺序存储结构实现!\n");

    Status iStatus;
    Position p;
    CElemType e;
    SqBiTree T;

    InitBiTree(T);
    CreateBiTree(T);
    printf("建立二叉树后,树空否？%d(1:是 0:否) \n",BiTreeEmpty(T));
    printf("树的深度=%d\n",BiTreeDepth(T));

    p.level=3;
    p.order=2;
    e=Value(T,p);
    printf("第%d层第%d个结点的值: %d\n",p.level,p.order,e);

    iStatus = Root(T, &e);
    if (iStatus) {
        printf("二叉树的根为:%d\n",e);
    }else
    {
        printf("树为空,无根!\n");
    }

    //向树中3层第2个结点位置上结点赋值99
    e = 99;
    Assign(T, p, e);

    //获取树中3层第2个结点位置结点的值是多少:
    e=Value(T,p);
    printf("第%d层第%d个结点的值: %d\n",p.level,p.order,e);

    //找到e这个结点的双亲;
    printf("结点%d的双亲为%d_",e,Parent(T, e));
    //找到e这个结点的左右孩子;
    printf("左右孩子分别为:%d,%d\n",LeftChild(T, e),RightChild(T, e));
    //找到e这个结点的左右兄弟;
    printf("结点%d的左右兄弟:%d,%d\n",e,LeftSibling(T, e),RightSibling(T, e));

    Assign(T, p, 5);

    printf("二叉树T层序遍历:");
    LevelOrderTraverse(T);

    printf("二叉树T先序遍历:");
    PreOrderTraverse(T);

    printf("二叉树T中序遍历:");
    InOrderTraverse(T);

    printf("二叉树T后序遍历:");
    PostOrderTraverse(T);

    return 0;
}

四、二叉树的链式存储实现

#include "string.h"
#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* 存储空间初始分配量 */
#define MAXSIZE 100
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

#pragma mark--二叉树构造
int indexs = 1;
typedef char String[24]; /*  0号单元存放串的长度 */
String str;
Status StrAssign(String T,char *chars)
{
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];i++)
            T[i]=*(chars+i-1);
        return OK;
    }
}

#pragma mark--二叉树基本操作

typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode  /* 结点结构 */
{
    CElemType data;        /* 结点数据 */
    struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;

/*7.1 打印数据*/
Status visit(CElemType e)
{
    printf("%c ",e);
    return OK;
}

/* 7.2 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
    *T=NULL;
    return OK;
}

/* 7.3 销毁二叉树
 初始条件: 二叉树T存在。
 操作结果: 销毁二叉树T
 */
void DestroyBiTree(BiTree *T)
{
    if(*T)
    {
        /* 有左孩子 */
        if((*T)->lchild)
            DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */

        /* 有右孩子 */
        if((*T)->rchild)
            DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */

        free(*T); /* 释放根结点 */

        *T=NULL; /* 空指针赋0 */
    }
}
#define ClearBiTree DestroyBiTree

/*7.4 创建二叉树
 按前序输入二叉树中的结点值(字符),#表示空树;
 */
void CreateBiTree(BiTree *T){

    CElemType ch;

    //获取字符
    ch = str[indexs++];

    //判断当前字符是否为'#'
    if (ch == '#') {
        *T = NULL;
    }else
    {
        //创建新的结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        //是否创建成功
        if (!*T) {
            exit(OVERFLOW);
        }

        /* 生成根结点 */
        (*T)->data = ch;
        /* 构造左子树 */
        CreateBiTree(&(*T)->lchild);
        /* 构造右子树 */
        CreateBiTree(&(*T)->rchild);
    }

}

/*
 7.5 二叉树T是否为空;
 初始条件: 二叉树T存在
 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE
 */
Status BiTreeEmpty(BiTree T)
{
    if(T)
        return FALSE;
    else
        return TRUE;
}

/*
 7.6 二叉树T的深度
 初始条件: 二叉树T存在
 操作结果: 返回T的深度
 */
int BiTreeDepth(BiTree T){

    int i,j;
    if(!T)
        return 0;

    //计算左孩子的深度
    if(T->lchild)
        i=BiTreeDepth(T->lchild);
    else
        i=0;

    //计算右孩子的深度
    if(T->rchild)
        j=BiTreeDepth(T->rchild);
    else
        j=0;

    //比较i和j
    return i>j?i+1:j+1;
}

/*
 7.7 二叉树T的根
 初始条件: 二叉树T存在
 操作结果: 返回T的根
 */
CElemType Root(BiTree T){
    if (BiTreeEmpty(T))
        return Nil;

    return T->data;
}

/*
 7.8 返回p所指向的结点值;
 初始条件: 二叉树T存在，p指向T中某个结点
 操作结果: 返回p所指结点的值
 */
CElemType Value(BiTree p){
    return p->data;
}

/*
 7.8 给p所指结点赋值为value;
 初始条件: 二叉树T存在，p指向T中某个结点
 操作结果: 给p所指结点赋值为value
 */
void Assign(BiTree p,CElemType value)
{
    p->data=value;
}

#pragma mark--二叉树遍历
/*
 7.8  前序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 前序递归遍历T
 */

void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
    PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}

/*
 7.9  中序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 中序递归遍历T
 */
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild); /* 中序遍历左子树 */
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}

/*
 7.10  后序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 中序递归遍历T
 */
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild); /* 先后序遍历左子树  */
    PostOrderTraverse(T->rchild); /* 再后序遍历右子树  */
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("二叉树链式存储结构实现!\n");

    int i;
    BiTree T;
    CElemType e1;

    InitBiTree(&T);

    StrAssign(str,"ABDH#K###E##CFI###G#J##");

    CreateBiTree(&T);
    printf("二叉树是否为空%d(1:是 0:否),树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));

    e1=Root(T);
    printf("二叉树的根为: %c\n",e1);

    printf("\n前序遍历二叉树:");
    PreOrderTraverse(T);

    printf("\n中序遍历二叉树:");
    InOrderTraverse(T);

    printf("\n后序遍历二叉树:");
    PostOrderTraverse(T);

    printf("\n");

    return 0;
}

五、线索化二叉树

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

优势

  • (1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。
  • (2)任意一个结点都能直接找到它的前驱和后继结点。

不足

  • (1)结点的插入和删除麻烦，且速度也较慢。
  • (2)线索子树不能共用。
规则
1\. 结点左子树为空，利用左孩子指针指向它的前驱结点；
2\. 结点右子树为空，利用右孩子指针指向它的后继结点；
3\. 注意：所有前驱和后继必须按照某一种遍历逻辑（中序）

为了区分一个结点的左孩⼦指针指向的是左孩子还是前驱结点，引入了标志位（tag, 0表示左/右孩子，1表示前驱或后继），

完整代码

#include "string.h"
#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */

/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Status;
typedef char CElemType;
/* 字符型以空格符为空 */
CElemType Nil='#';

#pragma mark--二叉树构造
int indexs = 1;
typedef char String[24]; /*  0号单元存放串的长度 */
String str;
Status StrAssign(String T,char *chars)
{
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];i++)
            T[i]=*(chars+i-1);
        return OK;
    }
}

/* Link==0表示指向左右孩子指针, */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum {Link,Thread} PointerTag;

/* 线索二叉树存储结点结构*/
typedef struct BiThrNode{

    //数据
    CElemType data;

    //左右孩子指针
    struct BiThrNode *lchild,*rchild;

    //左右标记
    PointerTag LTag;
    PointerTag RTag;

}BiThrNode,*BiThrTree;

/*
 8.1 打印
 */
Status visit(CElemType e)
{
    printf("%c ",e);
    return OK;
}

/*
 8.3 构造二叉树
 按照前序输入线索二叉树结点的值,构造二叉树T
 */

Status CreateBiThrTree(BiThrTree *T){

    CElemType h;
    //scanf("%c",&h);
    //获取字符
    h = str[indexs++];

    if (h == Nil) {
        *T = NULL;
    }else{
        *T = (BiThrTree)malloc(sizeof(BiThrNode));
        if (!*T) {
            exit(OVERFLOW);
        }
        //生成根结点(前序)
        (*T)->data = h;

        //递归构造左子树
        CreateBiThrTree(&(*T)->lchild);
        //存在左孩子->将标记LTag设置为Link
        if ((*T)->lchild) (*T)->LTag = Link;

        //递归构造右子树
        CreateBiThrTree(&(*T)->rchild);
        //存在右孩子->将标记RTag设置为Link
        if ((*T)->rchild) (*T)->RTag = Link;
    }

    return OK;
}

/*
 8.3 中序遍历二叉树T, 将其中序线索化
 */

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化*/
void InThreading(BiThrTree p){

    /*
     InThreading(p->lchild);
     .....
     InThreading(p->rchild);
     */
    if (p) {
        //递归左子树线索化
        InThreading(p->lchild);
        //无左孩子
        if (!p->lchild) {
            //前驱线索
            p->LTag = Thread;
            //左孩子指针指向前驱
            p->lchild  = pre;
        }else
        {
            p->LTag = Link;
        }

        //前驱没有右孩子
        if (!pre->rchild) {
            //后继线索
            pre->RTag = Thread;
            //前驱右孩子指针指向后继(当前结点p)
            pre->rchild = p;
        }else
        {
            pre->RTag = Link;
        }

        //保持pre指向p的前驱
        pre = p;
        //递归右子树线索化
        InThreading(p->rchild);
    }
}

/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt , BiThrTree T){

    *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));

    if (! *Thrt) {
        exit(OVERFLOW);
    }

    //建立头结点;
    (*Thrt)->LTag = Link;
    (*Thrt)->RTag = Thread;
    //右指针回指向
    (*Thrt)->rchild = (*Thrt);

    /* 若二叉树空,则左指针回指 */
    if (!T) {
        (*Thrt)->lchild=*Thrt;
    }else{

        (*Thrt)->lchild=T;
        pre=(*Thrt);

        //中序遍历进行中序线索化
        InThreading(T);

        //最后一个结点rchil 孩子
        pre->rchild = *Thrt;
        //最后一个结点线索化
        pre->RTag = Thread;
        (*Thrt)->rchild = pre;

    }
    return OK;
}

/*中序遍历二叉线索树T*/
Status InOrderTraverse_Thr(BiThrTree T){
    BiThrTree p;
    p=T->lchild; /* p指向根结点 T指向头结点 */
    while(p!=T)
    { /* 空树或遍历结束时,p==T */
        while(p->LTag==Link)//A->B->D->H, 此时H结点的LTag不是Link ,则循环结束
            p=p->lchild;
        if(!visit(p->data)) /* 访问其左子树为空的结点 */
            return ERROR;
        while(p->RTag == Thread && p->rchild != T)
            //由于结点H的RTag == Tread,且不不是指向头结点, 因此打印H的后继D,之后因为D的RTag 是Link 则退出循环.
        {
            p=p->rchild;
            visit(p->data); /* 访问后继结点 */
        }
        p=p->rchild;
    }

    return OK;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 线索化二叉树!\n");
    BiThrTree H,T;

    //StrAssign(str,"ABDH#K###E##CFI###G#J##");
    StrAssign(str,"ABDH##I##EJ###CF##G##");

    CreateBiThrTree(&T); /* 按前序产生二叉树 */
    InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
    InOrderTraverse_Thr(H);
    printf("\n\n");
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 218,386评论 6赞 506
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,142评论 3赞 394
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,704评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,702评论 1赞 294
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,716评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,573评论 1赞 305
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,314评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,230评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,680评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,873评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,991评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,706评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,329评论 3赞 330
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,910评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,038评论 1赞 270
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,158评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,941评论 2赞 355