数据结构——树与二叉树

树和二叉树

树和二叉树的定义、基本术语、性质

树（tree）是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点：

1.有且仅有一个特定的称为根的节点。

2.当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。二叉树的子树有严格的左右之分，其次序不能颠倒，即使某个结点只有一棵子树，也要区分是左子树还是右子树。

逻辑表示方法

树形表示法
文氏图表示法
凹入表示法
括号表示法先将根结点放在一对圆括号外，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理，同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。

基本术语

结点的度与树的度、节点层次和树的高度、分支结点和叶子结点、路径和路径长度、孩子、双亲和兄弟结点、有序树和无序树

二叉树及其5种基本形态、满二叉树、完全二叉树

性质

树的性质

树中的结点数等于所有结点的度数加1。
度为m的树中第i层上至多有m^i-1个结点(i≥1)。
深度为h的m次树至多有(m^h-1)/(m-1)个结点。
具有n个结点的m次树的最小深度为⌈log_m(n(m-1)+1)⌉。（ ⌈⌉为向上取整符号。）

二叉树的性质

非空二叉树上叶子结点数等于双分支结点数加1。
二叉树上第i层上至多有2^i-1个结点(i≥1)。
深度为h的二叉树至多有2^h-1个结点。
具有n个(n>0)结点的完全二叉树的深度为⌈log₂(n+1)⌉或⌊log₂(n)⌋+1。

二叉树中其他常用性质（n是二叉树中结点总数、n_i 是度为i的结点数）

n = n₀ + n₁ + n₂
n = n₁ + 2 * n₂ + 1
n₀ = n₂ + 1
完全二叉树中有n₁ + n₂ = n₀或者n₁ + n₂ = n₀ - 1。
任何一棵完全二叉树中度为1的结点要么有1个，要么就没有度为1的结点。当n为偶数时，n₁ = 1；当n为奇数时，n₁ = 0。
含有n个结点的不同形态的二叉树有1/(n+1) * C(2n,n)

二叉树存储结构

顺序存储结构

将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中。因此，必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。适用于完全二叉树和满二叉树。完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。

链式存储结构

二叉树的一个节点最多可以指向左右两个孩子节点，所以二叉树的每一个节点包含三部分。

存储数据的data变量

指向左孩子的left指针

指向右孩子的right指针

结点类型BTNode的声明如下：

typedef struct node
{
    ElemType data; //存储数据的data变量
    struct node *lchild;  //指向左孩子结点
    struct node *rchild;  //指向右孩子结点
} BTNode;

创建二叉树(使用二叉链存储结构)

对应算法如下：

 //str是用括号表示法表示的二叉树的字符串(每个结点只储存单个字符)
void CreateBTree(BTNode *&b, char *str)
{
    BTNode *St[MAXSIZE]; //用一个St数组作为顺序栈，用来储存新建的结点
    BTNode *p;           //新创建的结点指向p
    int top = -1;        //top作为栈顶的指针
    int k;               //定义一个k来处理是左孩子还是右孩子
    int j = 0;           //字符串的下标为0，即从字符串第一位开始扫描
    char ch;             //用ch储存str[j]的值
    b = NULL;            //初始二叉链为空
    ch = str[j];         //首先将str[0]的值赋给ch
    while (ch != '\0')   //循环扫描str的每个字符
    {
        switch (ch)
        {
        case '(':               //若ch='(' 表示刚创建的p结点存在孩子结点，需要将其入栈作为栈顶结点
            top++;                            //栈顶指针上移一位
            St[top] = p;                      //将结点p入栈成为栈顶结点
            k = 1;                            //把k设置成1 开始处理左孩子结点
            break;                            //跳出swich语句
        case ')':               //ch='(' 表示以栈顶结点为根结点的子树创建完毕，需要将其退栈
            top--;                            //栈顶指针下移一位 表示退栈一次
            break;                            //跳出swich语句
        case ',':               //若ch=',' 表示其后创建的结点将作为当成栈顶结点的右孩子结点
            k = 2;                                //把k设置成2 开始处理左孩子结点
            break;                                //跳出swich语句
        default:                                  //其他情况 即ch为单个字符
            p = (BTNode *)malloc(sizeof(BTNode)); //创建一个结点，由p指向它
            p->data = ch;                         //储存结点的值
            p->lchild = p->rchild = NULL;         //将该节点的左右指针都设置为空
            if (b == NULL)                        //如果b为NULL证明还没有建立根节点
                b = p;                            //将p所指向的结点设置为根节点
            else                                  //如果已经建立了根节点
            {
                switch (k)
                {
                case 1:                  //如果k为1
                    St[top]->lchild = p; //将新建的结点作为栈顶结点的左孩子
                    break;               //跳出swich语句
                case 2:                  //如果k为2
                    St[top]->rchild = p; //将新建的结点作为栈顶结点的右孩子
                    break;               //跳出swich语句
                }
            }
        }
        //跳出swich语句直接来到这里
        j++;         //字符串的下标后移一位
        ch = str[j]; //将str[] 的值赋给ch，重新回到while循环 如果ch=='\0'扫描完毕 结束while循环
    }               
}

二叉树和树的转换

树->二叉树

二叉树->树

转换后的序列关系

如果将一棵有序树T转换成二叉树B，那么T中结点的先序遍历序列就是B中结点的先序序列。

如果将一棵有序树T转换成二叉树B，那么T中结点的后序遍历序列就是B中结点的中序序列。

知乎文章树与二叉树的转换 https://zhuanlan.zhihu.com/p/134251528

二叉树的遍历

先序遍历（根左右）

二叉树的先序遍历，输出顺序是根节点、左子树、右子树。

上图就是一个二叉树的先序遍历，每个节点左侧的序号代表该节点的输出顺序。

中序遍历（左根右）

二叉树的中序遍历，输出顺序是左子树、根节点、右子树。

上图就是一个二叉树的中序遍历，每个节点左侧的序号代表该节点的输出顺序。

后序遍历（左右根）

二叉树的后序遍历，输出顺序是左子树、右子树、根节点。

上图就是一个二叉树的中序遍历，每个节点左侧的序号代表该节点的输出顺序。

遍历序列相同的条件

1.二叉树的先序序列和中序序列相同的条件是该二叉树每个结点最多只有一个右孩子。

先序序列为NLR，中序序列为LNR，要使NLR=LNR，只能让L为空或者L、R均为空，因此该二叉树每个结点最多只有一个右孩子。

2.二叉树的后序序列和中序序列相同的条件是该二叉树每个结点最多只有一个左孩子。

后序序列为LRN，中序序列为LNR，要使LRN=LNR，只能让R为空或者L、R均为空，因此该二叉树每个结点最多只有一个左孩子。

通过两种遍历序列写出完整的二叉树

前提是二叉树中结点的值均不相同 可以通过通过先序和中序写出完整的二叉树，也可以通过后序和中序写出完整的二叉树。但是已知先序序列和后序序列无法写出一棵完整的二叉树。

知乎文章还原一棵二叉树 https://zhuanlan.zhihu.com/p/73438175

二叉树遍历的非递归算法

二叉树的非递归算法先序遍历和中序遍历比较简单、思路基本相同。后序遍历因为根节点要最后打印，导致思路与前两者有所差异，算法也要复杂一些。

先序遍历

void PreOrder(BTNode *b)
{
    BTNode *p;                           //定义一个结点p
    SqStack *st;                         //定义一个栈st
    InitStack(st);                       //初始化栈
    p = b;                               //将根结点b存到p中
    while (!StackEmpty(st) || p != NULL) //如果栈不为空或p结点不为空
    {
        while (p != NULL) //如果p结点不为空
        {
            printf("%c", p->data); //打印p结点的数据
            Push(st, p);           //并将p结点入栈
            p = p->lchild;         //将p更新为p的左孩子
        }
        if (!StackEmpty(st)) //如果st不是空栈
        {
            Pop(st, p);    //将栈顶的结点赋给p，并将其出栈
            p = p->rchild; //将p更新为p的右孩子
        }
    }
    printf("\n");
    DestoryStack(st); //销毁栈
}

中序遍历

void InOrder(BTNode *b)
{
    BTNode *p;                           //定义一个结点p
    SqStack *st;                         //定义一个栈st
    InitStack(st);                       //初始化栈
    p = b;                               //将根结点b存到p中
    while (!StackEmpty(st) || p != NULL) //如果栈不为空或p结点不为空
    {
        while (p != NULL) //如果p结点不为空
        {
            Push(st, p);   //并将p结点入栈
            p = p->lchild; //将p更新为p的左孩子
        }
        if (!StackEmpty(st)) //如果st不是空栈
        {
            Pop(st, p);            //将栈顶的结点赋给p，并将其出栈
            printf("%c", p->data); //打印p结点的数据
            p = p->rchild;         //将p更新为p的右孩子
        }
    }
    printf("\n");
    DestoryStack(st); //销毁栈
}

后序遍历

自己写了一个不需要用到flag的程序

void PostOrder(BTNode *b)
{
    BTNode *p;                           //定义一个结点p
    BTNode *r;                           //定义一个结点r来保存已经被访问过的右孩子
    SqStack *st;                         //定义一个栈st
    InitStack(st);                       //初始化栈
    p = b;                               //将根结点b存到p中
    r = NULL;                            //先把r置为NULL
    while (!StackEmpty(st) || p != NULL) //如果栈不为空或p结点不为空
    {
        while (p != NULL) //如果p结点不为空
        {
            Push(st, p);   //并将p结点入栈
            p = p->lchild; //将p更新为p的左孩子
        }
        Pop(st, p);                              //将栈顶的结点赋给p，并将其出栈
        if (p->rchild == NULL || p->rchild == r) //如果p的右孩子是NULL或者p的右孩子是r(表示这个右孩子已经被访问过了)
        {
            printf("%c", p->data); //打印p结点的数据
            r = p;                 //将p赋给r
            p = NULL;              //这里要将p置为NULL，否则会进入上面的while循环打乱遍历顺序
        }
        else //如果p有右孩子，且还没有被访问过
        {
            Push(st, p);   //将p重新入栈
            p = p->rchild; //将p更新为p的右孩子
        }
    }
    printf("\n");
    DestoryStack(st); //销毁栈
}

线索化二叉树

线索二叉树的概念

中序线索二叉树的算法

TBTNode *pre;  //pre作为全局变量指向刚访问过的结点
void Thread(TBTNode *&p) //中序线索化二叉树p
{
    if (p != NULL)  //p指的是当前被线索化的结点，如果p不是NULL
    {
        Thread(p->lchild);     //首先进行左子树线索化
        if (p->lchild == NULL) //如果p不存在左孩子
        {
            p->lchild = pre;  //让p的左孩子指向前驱结点
            p->ltag = 1;      //将p的左标志置为1
        }
        else
            p->ltag = 0;   //否则p的左标志置为0
        if (pre->rchild == NULL) //如果pre不存在右孩子
        {
            pre->rchild = p;   //让pre的右孩子指向后继结点
            p->rtag = 1;       //将pre的右标志置为1
        }
        else
            p->rtag = 0;    //否则pre的右标志置为0
        pre = p;
        Thread(p->rchild);  //递归调用Thread进行右子树线索化
    }
}
TBTNode *CreatThread(TBTNode *b)   //中序线索化二叉树
{
    TBTNode *root;
    root = (TBTNode *)malloc(sizeof(TBTNode));  //创建一个头结点root
    root->ltag = 0; //头结点的左标志为0
    root->rtag = 1; //头结点的右标志为1
    root->lchild = b; //书上写错了 应该是头结点的左指针域指向根节点b
    if (b == NULL)  //如果根节点为空
        root->lchild = root;  //就让根节点的左指针指向自身
    else
    {
        root->lchild = b;  //将头结点的左指针域指向根节点b
        pre = root; //pre指向头结点root
        Thread(b);  //调用Thread(b)对整个二叉树线索化
        pre->rchild = root; //最后加入指向头结点的线索
        pre->rtag = 1;
        root->rchild = pre; //头右节点指向最后一个结点pre
    }
    return root; //返回头结点
}

遍历线索化二叉树

void ThInOrder(TBTNode *tb)  //tb指向的是中序线索二叉树的头结点
{
    TBTNode *p = tb->lchild; //p指向的是根结点
    while (p != tb) //当p不是头结点时循环
    {
        while (p->ltag == 0)   //寻找开始结点
            p = p->lchild;
        printf("%c", p->data); //打印开始结点的值
        while (p->rtag == 1 && p->rchild != tb) //当p结点有右线索且p的右孩子不是头结点
        {
            p = p->rchild; //一直访问下去
            printf("%c", p->data); //并打印p的值
        }
        p = p->rchild; //如果p结点没有右线索，转向右孩子结点
    }
}

哈夫曼树

哈夫曼树的定义

WPL（带权路径长度）

哈夫曼树的概念（简单说就是WPL最小的二叉树）

哈夫曼树的构造算法

定理：具有n₀个叶子结点的哈夫曼树，共有2n₀-1个结点。

为了实现构造哈夫曼树的算法，设计哈夫曼树的结点类型如下：

typedef struct{
    char data;      //结点值
    double weight;  //权重
    int parent;     //双亲结点
    int lchild;     //左孩子结点
    int rchild;     //右孩子结点
}HTNode;

代码实现：

void CreatHT(HTNode ht[], int n0)
{
    int i, k, lnode, rnode;
    double min1, min2;
    for (i = 0; i < 2 * n0 - 1; i++) //首先将所有的结点的相关域均置为-1
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    for (i = n0; i <= 2 * n0 - 2; i++) //构造哈夫曼树的n0-1个非叶子结点
    {
        min1 = min2 = 32767;         //首先将两个存放权重的变量设一个非常大的值
        lnode = rnode = -1;          //lnode和rnode是最小权重的两个结点的位置
        for (k = 0; k <= i - 1; k++) //通过for循环在ht[0..i-1]中找权重最小的两个结点
            if (ht[k].parent == -1)  //判断一下如果ht[k]的parent是-1，表示还未参与构造二叉树
            {
                if (ht[k].weight < min1) //如果ht[k]的权重小于min1
                {
                    min2 = min1;         //将原来最小的替换次小的
                    rnode = lnode;       //次小的做右孩子
                    min1 = ht[k].weight; //找到的最小的替换原来最小的
                    lnode = k;           //最小的做左孩子
                }
                else if (ht[k].weight < min2) //调整min2的值成为真正的次小值
                {
                    min2 = ht[k].weight; //更新min2的值
                    rnode = k;           //更新右孩子
                }
            }
        ht[i].weight = ht[lnode].weight + ht[rnode].weight;//ht[i]的权重为左右孩子的权重值之和
        ht[i].lchild = lnode;                               //设置ht[i]的左孩子为lnode
        ht[i].rchild = rnode;                               //设置ht[i]的右孩子为rnode
        ht[lnode].parent = i;                               //设置ht[lnode]的父结点为i
        ht[rnode].parent = i;                               //设置ht[rnode]的父结点为i
    }
}

哈夫曼编码

存放每个结点的哈夫曼编码的类型如下：

typedef struct{
    char cd[N]; //存放当前结点的哈夫曼码
    int start;  //表示cd[start..n0]部分是哈夫曼码
}HCode;

左分支为0、右分支为1，(也可以是左分支为1、右分支为0)从根节点到每个叶子结点经过的分支对应的0和1组成的序列便是该结点对应的编码。使用频率越高的字符采用越短的编码。

根据哈夫曼树求对应的哈夫曼编码的算法如下：

void CreatHCode(HTNode ht[], HCode hcd[], int n0)
{
    int i, f, c;
    HCode hc;
    for (i = 0; i < n0; i++) //根据哈夫曼树求哈夫曼编码
    {
        hc.start = n0; //先将htd[i]的start域置为n0
        c = i;
        f = ht[i].parent;
        while (f != -1) //循环直到没有双亲结点，抵达根节点
        {
            if (ht[f].lchild == c)       //如果当前结点是双亲结点的左孩子
                hc.cd[hc.start--] = '0'; //在hcd[i]的cd数组中添加0 start域减一
            else                         //如果当前结点是双亲结点的右孩子
                hc.cd[hc.start--] = '1'; ////在hcd[i]的cd数组中添加1  start域减一
            c = f;                       //对双亲结点进行同样的操作，直到到达根节点
            f = ht[f].parent;
        }
        hc.start++;  //start指向哈夫曼编码的最开始的字符
        hcd[i] = hc; //保存该叶子结点的哈夫曼编码
    }
}

说明：在一组字符的哈夫曼编码中，任一字符的哈夫曼编码不可能是另一字符哈夫曼编码的前缀。

哈夫曼树中没有度为1的结点。