树

树：

树是n(n>=0)个节点的有限集。n=0时称为空树。在任一棵非空树中:

(1)有且仅有一个特定的称为根的节点；

(2)当n>1时其余节点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm,其中每一个集合本身又是一棵树，并且称为根的子树。

节点分类：

节点拥有的子树数称为节点的度。度为0的节点称为叶节点或终端节点；度不为0的节点称为非终端节点或分支节点。除根节点之外，分支节点也称为内部节点。树的度是树内各节点的度的最大值。

节点间关系：

节点的子树的根称为该节点的孩子，相应地，该节点称为孩子的双亲。同一个双亲的孩子之间互称兄弟。节点的祖先是从根到该节点所经分支上的所有节点

其他概念：

节点的层次从根开始定义起，根为第一层，根的孩子为第二层·。其双亲在同一层的节点互为堂兄弟。树中节点的最大层次称为树的深度或高度。

若将树中节点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林是(m>=0)棵互不相交的集合。

如图：

树

对比线性表与树的结构：

线性结构：

1.第一个数据元素：无前驱

2.最后一个数据元素：无后继

3.中间元素：一个前驱一个后继

树结构：

1.根节点：无双亲，唯一

2.叶节点：无孩子，可以多个

3.中间节点：一个双亲，多个孩子

树的存储结构的表示方法：

1.双亲表示法（在每个节点中，附设一个指示器指示其双亲节点在数组中的位置）；

2.孩子表示法（多重链表，即每个节点有多个指针域，其中每个指针指向一棵子树的根节点），由于难以寻找双亲，可改进为双亲孩子表示法)；

3.//孩子兄弟表示法（任意一棵树，它的节点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该节点的第一个孩子和此节点的右兄弟）也可加parent指针域来解决快速查找双亲的问题。这个表示法的最大好处是他把一颗复杂的树变成了一颗二叉树。

上图的二叉树表示

//树的孩子兄弟表示法结构定义

struct CSNode

{

    int data;

    CSNode* firstchild;

    CSNode* rightsib;

};

二叉树

二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树特点：

1.每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。

2.左子树和右子树是有顺序的，次序不能任意颠倒。

3.即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

二叉树有5种基本形态：

1.空二叉树；

2.只有一个根节点；

3.根节点只有左子树；

4.根节点只有右子树；

5.根节点既有左子树悠悠右子树。

特殊二叉树：

1.斜树：所有的节点都只有左子树的二叉树叫左斜树；所有节点都是只有右子树的二叉树叫右斜树。

2.满二叉树：在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树

特点：

(1)叶子只能出现在最下一层；

(2)非叶子节点的度一定是2；

(3)在同样深度的二叉树中，满二叉树的节点个数最多，叶子数最多。

3.完全二叉树：

对一棵具有n个节点的二叉树按层序编号，如果编号为i（1<=i<=n）的节点与同样深度的满二叉树编号为i的节点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

完全二叉树1 完全二叉树2

特点：

(1):叶子节点只能出现在最下两层；

(2):最下层的叶子一定集中在左部连续位置；

(3):倒数二层，若有叶子节点，一定都在右部连续位置；

(4):如果节点度为1，则该节点只有左孩子，即不存在只有右子树的情况；

(5):同样节点数的二叉树，完全二叉树的深度最小。

二叉树性质：

1.在二叉树的第i层上至多有2^(i-1)个节(i>=1);

2.深度为k的二叉树至多有个节点(k>=1）;

3.对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1;

4.具有n个节点的完全二叉树的深度为[log2n]+1([x]表示不大于x的最大整数)；

5.如果对一棵有n个节点的完全二叉树（其深度为[log2n]+1）的节点按层序编号（从第1层到第[log2n]+1层，每层从左到右），对任一节点i（1<=i<=n）有：

(1).如果i=1，则节点i是二叉树的根，无双亲；如果i>1,则其双亲是节点[i/2];

(2).如果2i>n,则节点i无左孩子（节点i为叶子节点）；否则其左孩子是节点2i；

(3).如果2i+1>n，则节点i无右孩子；否则其右孩子是节点2i+1;

二叉树的存储结构：

1.顺序存储：

顺序存储

考虑一种极端的情况，一棵深度为k的右斜树，他只有k个节点，却要分配-1个存储单元空间，这显然是对存储空间的浪费。所以，顺序存储结构一般只用于完全二叉树。

2.二叉链表：

节点结构

//二叉树的二叉链表节点结构定义

struct BitNode

{

    int data;

    BitNode* lchild;

    BitNode* rchild;

};

二叉树的遍历：

二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次。

方法：

1.前序遍历：若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树；

//二叉树的前序遍历递归算法

void PreOrderTraverse(BitNode* T)

{

    if (T == NULL)

        return;

    printf("%d ", T->data);

    PreOrderTraverse(T->lchild);

    PreOrderTraverse(T->rchild);

}

2.中序遍历：若二叉树为空，则空操作返回，否则从根节点开始(注意并不是先访问根节点)，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树；

//二叉树的中序遍历递归算法

void InOrderTraverse(BitNode* T)

{

    if (T == NULL)

        return;

    InOrderTraverse(T->lchild);

    printf("%d ", T->data);

    InOrderTraverse(T->rchild);

}

3.后续遍历：若二叉树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后是访问根节点。

//二叉树的后序遍历递归算法

void postOrderTraverse(BitNode* T)

{

    if (T == NULL)

        return;

    postOrderTraverse(T->lchild);

    postOrderTraverse(T->rchild);

    printf("%d ", T->data);

}

4.层序遍历：若二叉树为空，则空操作返回，否则从树的第一层，特就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对节点逐个访问。

二叉树遍历的性质：

1.已知前序遍历和中序遍历，可以唯一确定一棵二叉树；

2.已知后序遍历和中序遍历，可以唯一确定一棵二叉树；

3.已知前序遍历和后序遍历，不能确定一棵二叉树。

二叉树的建立：

普通二叉树

为了能让每个节点确认是否有左右孩子，我们对它进行了扩展，如下图，也就是将二叉树中每个节点的空指针引出一个虚节点，其值为一特定值，比如“#”。我们称这种处理后的二叉树为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。

扩展二叉树

//常用操作：

//构造空二叉树

int InitBiTree(BitNode** T)

{

    *T = NULL;

    return 0;

}

//初始条件 ：二叉树T存在。操作结果：销毁二叉树T

void DestroyBiTree(BitNode** T)

{

    if (*T)

    {

        if ((*T)->lchild)//有左孩子

            DestroyBiTree(&(*T)->lchild);

        if ((*T)->rchild)//有右孩子

            DestroyBiTree(&(*T)->rchild);

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

        *T = NULL;//空指针赋07

    }

}

//按前序输入二叉树中节点的值（一个字符）

//“#”表示空树，构造二叉链表表示二叉树T

void CreateBiTree(BitNode** T)

{

    char ch;

    /*printf("请输入：");

    scanf("%c", &ch);*/

    ch = str[index++];

    if (ch == '#')

    *T = NULL;

    else

    {

        *T = (BitNode*)malloc(sizeof(BitNode));

        if (!*T)

        {

            exit(OVERFLOW);

        }

        (*T)->data = ch;//生成根节点

        CreateBiTree(&(*T)->lchild);//构造左子树

        CreateBiTree(&(*T)->rchild);//构造右子树

    }

}

//二叉树的前序遍历递归算法

void PreOrderTraverse(BitNode* T)

{

    if (T == NULL)

    {

        return;

    }

    printf("%c ", T->data);

    PreOrderTraverse(T->lchild);

    PreOrderTraverse(T->rchild);

}

//二叉树的中序遍历递归算法

void InOrderTraverse(BitNode* T)

{

    if (T == NULL)

        return;

    InOrderTraverse(T->lchild);

    printf("%c ", T->data);

    InOrderTraverse(T->rchild);

}

//二叉树的后序遍历递归算法

void postOrderTraverse(BitNode* T)

{

    if (T == NULL)

        return;

    postOrderTraverse(T->lchild);

    postOrderTraverse(T->rchild);

    printf("%c ", T->data);

}

//生成一个其值等于字符串常量chars的串T,即在头部添加长度

char* StrAssign(char* T, char* chars)

{

    T[0] = strlen(chars);

    for (int i = 1; i <= T[0]; i++)

    {

        T[i] = *(chars + i - 1);

    }

    return T;

}

//初始条件：二叉树存在

//操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE

bool BiTreeEmpty(BitNode* T)

{

    if (T)

        return false;

    return true;

}

//初始条件：二叉树T存在。操作结果：返回T的深度

int BiTreeDepth(BitNode* 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;

    return i > j ? i + 1 : j + 1;

}

//初始条件：二叉树T存在。操作结果：返回T的根

char Root(BitNode* T)

{

    if (BiTreeEmpty(T))

        return NULL;

    return T->data;

}

//初始条件：二叉树T存在，p指向T某个节点

//操作结果：返回P所指向的节点的值

char Value(BitNode* p)

{

    return p->data;

}

//初始条件：二叉树T存在

//给p所指节点赋值为value

void Assign(BitNode* p, char value)

{

    p->data = value;

}

线索二叉树

我们会发现二叉树中指针域并不是都充分的利用了，有空指针域的存在。在二叉链表上，我们只能知道每个节点指向其左右孩子节点的地址，而不知道某个节点的前驱的后继。要想知道，必须遍历一次。以后每次需要知道时，都必须先遍历一次。所以可以在创建的时候就记住这些前驱和后继。

把指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。

二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历二叉树时才能得到，所以线索化的过程就是在遍历的过程修改空指针的过程。

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

节点结构：

//二叉树的二叉线索存储结构定义
typedef enum MyEnum

{

    Link,//=0表示指向左右孩子指针

    Thread//=1表示指向前驱或者后继的线索

} PointerTag;

struct BiThrNode

{

    char data;//节点数据

    BiThrNode* lchild;//左右孩子指针

    BiThrNode* rchild;

    PointerTag LTag;//左右标志

    PointerTag RTag;

};

线索二叉树常用操作：

//按前序输入二叉线索树中节点的值，构造二叉树T

//0(整型)/空格（字符型）表示空节点

int CreateBiThrTree(BiThrNode** T)

{

    char h;

    scanf("%c", &h);

    if (h == '#')

        *T = NULL;

    else

    {

        *T = (BiThrNode*)malloc(sizeof(BiThrNode));

        if (!*T)

            exit(OVERFLOW);

        (*T)->data = h;//生成根节点

        CreateBiThrTree(&(*T)->lchild);//递归构造左子树

        if ((*T)->lchild)//有左孩子

            (*T)->LTag = Link;

        CreateBiThrTree(&(*T)->rchild);

        if ((*T)->rchild)

        (*T)->RTag = Link;

    }

    return 0;

}

//中序遍历进行中序线索化

void InThreading(BiThrNode* p)

{

    if (p)

    {

        InThreading(p->lchild);//递归左子树线索化

        if (!p->lchild)//没有左孩子

        {

            p->LTag = Thread;//前驱线索

            p->lchild = pre;//左孩子指向前驱

        }

        if (!pre->rchild)

        {

            pre->RTag = Thread;//后继线索

            pre->rchild = p;//前驱右孩子指针指向后继（当前节点p）

        }

        pre = p;//保持pre指向p的前驱

        InThreading(p->rchild);//递归右子树线索化

    }

}

有了线索二叉树后，我们对它进行遍历时发现，其实就等于时操作一个双向链表结构。和双向链表一样，在二叉树线索链表上添加一个头结点，如下图所示，并令其lchild域的指针指向二叉树的根节点，其rchild域的指针指向中序遍历时访问的最后一个节点。反之，令二叉树的中序序列中的第一个节点中，lchild域指针和最后一个节点的rchild域指针均指向头结点。这样定义的好处是我们既可以从第一个节点起顺后继进行遍历，也可以从最后一个节点起顺前驱进行遍历。

//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点

int InOrderThreading(BiThrNode** Thrt, BiThrNode* T)

{

    *Thrt = (BiThrNode*)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);//中序遍历进行中序线索化

        pre->rchild = *Thrt;

        pre->RTag = Thread;//最后一个节点线索化

        (*Thrt)->rchild = pre;

    }

    return 1;

}

int visit(char e)

{

printf("%c", e);

return 1;

}

//中序遍历二叉线索树T（头结点）的非递归算法

int InOrderTraverse_Thr(BiThrNode* T)

{

    BiThrNode* p;

    p = T->lchild;//p指向根节点

    while (p != T)//空树或遍历结束时p==T

    {

        while (p->LTag == Link)

        p = p->lchild;

        visit(p->data);

        while (p->RTag == Thread&&p->rchild != T)

        {

            p = p->rchild;

            visit(p->data);//访问后继节点

        }

        p = p->rchild;

    }

    return 1;

}

树、森林与二叉树的转换：

树的孩子兄弟表示法可以将一棵树用二叉链表进行存储，所以借助二叉链表，树和二叉树可以进行相互转换。从物理结构来看，他们的二叉链表也是相同的，只是解释不太一样而已。因此，只要我们设定一定的规则，用二叉树来表示树，甚至表示森林都是可以的，森林与二叉树也可以进行相互转换。

1.树转换为二叉树：

(1).加线。在所有兄弟之间加一条连线。

(2).去线。对树中每个节点，只保留它与第一个孩子节点的连线删除它与其它孩子节点之间的连线。

(3).层次调整。以树的根节点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树节点的孩子，兄弟转换过来的孩子是节点的右孩子。

树 (1).给兄弟加线 (3).给除长子外的孩子去线 (3).层次调整

2.森林转换为二叉树：

森林是由若干棵树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。步骤如下：

(1).把每个树转换为二叉树.

(2).第一棵树不动，从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树的根节点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

拥有三棵树的森林 (1).森林中每棵树转换为二叉树 (2).将所有二叉树转换为一棵二叉树

3.二叉树转换为树：

二叉树转换为树是树转换为二叉树的逆过程。

(1).加线。若某节点的左孩子节点存在，则将这个左孩子的右孩子节点、右孩子的右孩子节点、右孩子的右孩子的右孩子节点……，即左孩子的n个右孩子节点都作为此节点的孩子。将该节点与这些右孩子节点用线连接起来。

(2).去线。删除原二叉树中所有节点与其右孩子节点的连线。

(3).层次调整。使之结构层次分明。

4.二叉树转换为森林:

判断一棵二叉树能够转换成一棵树还是森林，只需要看这棵二叉树的根节点有没有右孩子，有就是森林，没有就是一棵树。

(1).从根节点开始，若右孩子存在，则把与右孩子节点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有孩子连线都删除位置，所得的分离的二叉树。

(2).再将每棵分离后的二叉树转换为树即可。

5.树与森林的遍历：

树的遍历分为两种方式：

(1).先根遍历树，即先访问树的根节点，然后依次先根遍历根的每棵子树。

(2).后根遍历，即先依次后根遍历每棵子树，然后再访问根节点。

森林的遍历分为两种方式：

(1).前序遍历：先访问森林中第一棵树的根节点，然后再依次先根遍历根的每棵子树，再依次用同样的方式遍历除去第一棵树的剩余树构成的森林。

(2).后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根节点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。

森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。也就是说，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历算法来实现.也就是我们找到了对数和森林这种复杂问题的简单解决办法。

赫夫曼树及其应用：

1.赫夫曼树定义与原理：

下面两个图为叶子节点带权的二叉树（树节点间的边相关的数叫做权）。

从树中一个节点到另一个节点之间的分支构成两个节点之间的路径，路径上的分支数乘坐路径长度。例如，二叉树a中，根节点到节点D的路径长度就为4，二叉树b中根节点到节点D的路径长度就为2.树的路径长度就是从树根到每一节点的路径长度之和。二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20；二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16。

如果考虑带权的节点，节点的带权的路径长度就为从该节点到树根之间的路径长度与节点上权的乘积。树的带权路径长度为树中所有叶子节点的带权路径长度之和。假设有n个权值{,,…，},构造一棵有n个叶子节点的二叉树，每个叶子带权，每个叶子的路径长度为，我们通常记作，则其中带权路径长度WPL最小的二叉树称作赫夫曼树。也可称为最优二叉树。

二叉树a的WPL=51+152+403+304+104=315;

5是A节点的权，1是A、

节点的路径长度，其他同理。

二叉树b的WPL=220

赫夫曼树的赫夫曼算法描述：

(1).根据给定的n个权值{，，…，}构成n棵二叉树的集合F={，，…，}，其中每棵二叉树中只有一个带权为根节点，其左右子树均为空；

(2).在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和；

(3).在F中删除这两棵树，同时将新得到的二叉树加入F中；

(4).重复2和3步骤，知道F只含一棵树为止。这棵树便是赫夫曼树。

2.赫夫曼编码：

编码中非0即1，长短不等的话其实是很容易混淆的，所以要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。

一般地，设需要编码的字符集为{，，…，}，各个字符在电文中出现的次数或品绿集合为{，，…，}，以，，…，作为叶子节点，以，，…，作为相应叶子节点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根节点到叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，这就是赫夫曼编码。