一.树的基本概念

1.树的定义

树是 N (N >= 0 )个结点的有限集合,N = 0 时,称为空树,这是一种特殊情况。在任意一棵非空树中应满足:

  • 有且仅有一个特定的称为根的结点。
  • 当 N > 1 时,其余结点可分为 m ( m > 0)个互不相交的有限集合T1 , T2 , T3 , .... Tm ,其中每一个集合本身又是 一棵树,并且称为根结点的子树。

图形化就是 除根节点外有且只有一个前驱结点,所有结点可以有零个或多个后继结点。如图所示:

定义树时,树的子集还是一棵树,这显然用到了递归的思想。

2.基本术语

  • 结点的度:结点拥有的子树数
  • 树的度:树内各结点度最大值,树的度为m,也可以成为m次树
  • 叶结点/终端结点:度为0的结点(没有子树的结点)
  • 分支结点/非终端结点;度不为0(有子树的结点)
  • 结点的层次:根结点为第一层,根结点的孩子为第二层...
  • 深度/高度:结点的最大层次
  • 森林:n(n>0)个互不相交的树组成。(把有多棵子树的树的根结点删去,就变成森林)

3.结点的关系

  • 孩子:结点的子树的根(树图形中连线的下方是上方的孩子)
  • 双亲:与孩子相对应(树图形中连线的上方是下方的孩子)
  • 子孙:(树图形中某结点下面的所有结点都是该结点的子孙)
  • 兄弟:有同一双亲的结点
  • 堂兄弟:双亲不是同一个,但在同一层

4.树的分类

  • 有序树:各子树从左到右有次序,不能互换
  • 无序树:各子树从左到右没有次序

5.树的性质

  1. 树中所有的结点数 = 所有结点的度数之和+1 :加的1是根结点。
  2. 度为m的树中第i层最多有$m^{i-1}$个结点:比如度为3,第一层有1个结点,第二层最多有3个结点,第三层最多有9个结点...... 即所有结点最多都有3个子节点,很好理解。
  3. 高度为h的m次树最多有$frac {m^h-1} {m-1}$个结点。:由上一个性质2,最多结点数 = 每层最大结点数之和 = $m^0+m^1+m^2+...+m^{h-1} = frac {m^h-1} {m-1}$,(等比数列求和)。

二.树的基本运算与存储结构

1.树的运算有三类:

  1. 访问满足条件的结点
  2. 指定结点插入或删除结点,
  3. 遍历树的所有结点

2.遍历树的三种方法:

大概了解一下就行,树的遍历不做要求,具体的遍历以及代码会在后面二叉树的遍历中给出。

  1. 先根遍历:
    1. 访问根结点
    2. 按照从左到右的顺序先根遍历结点的每一棵子树
  2. 后根遍历:
    1. 按照从左到右的顺序后根遍历结点的每一棵子树
    2. 访问根节点
  3. 层次遍历:
    1. 从根节点开始从上到下、从左到右的次序访问树的每一个结点

3.树的存储结构(代码实现)

树有三种常用的存储结构:双亲存储结构、孩子链存储结构、孩子兄弟链存储结构

3.1.双亲存储结构

双亲存储结构是一种顺序存储结构(内存连续),同时在每个结点中设一个伪指针来指示双亲结点的位置(根结点的索引为0,则根节点双亲的位置索引设成-1

typedef struct   //结点结构
{
    ElemType data;    //结点数据
    int parent;       //双亲位置
}PTNode;

typedef struct   //树结构
{
    PTNode nodes[MaxSize];   //结点数组
    int n;       //n是结点总数
}PTree;

伪指针:指针是指向内存地址,而这里的伪指针存的是索引值

例如:

特点:双亲存储结构在求双亲节点是很容易,但求某个结点的孩子结点时需要遍历整个存储结构。

3.2.孩子链存储结构

孩子存储结构的结点包含结点值(data),以及所有孩子结点指针(因为有多个孩子,所以用数组)。

每个结点的子树个数不同,孩子结点指针的个数也就不同,如果按动态分配给每个结点分配不同的指针域,操作和后续维护太麻烦了,因此一般指针域的个数用树的度(所有结点的最大值)—— 时间换空间。

代码:

typedef struct node
{
    ElemType data;
    struct node * sons[MaxSons];   //孩子结点指针
}TSonNode;

图解如下:

特点:找孩子容易,找双亲困难,而且树的度较大时存在较多的空指针域。

3.3.孩子兄弟链存储结构

设置三个域:一个数据域,一个指向左边第一个孩子的指针域,一个指向左边第一个孩子的下一个兄弟的指针域。

typedef struct tnode
{
    ElemType data;
    struct tnode * vp;   //左边第一个孩子结点指针
    struct tnode * vp;   //左边第一个孩子的兄弟结点指针
}TSonNode;

这样的方法实际上是把树转换成二叉树存储。

特点:能实现树和二叉树的相互转换,但是和孩子链存储结构一样,查找双亲结点比较困难

三.二叉树基本概念

1.二叉树

定义:二叉树是n个结点的有限集合。

  • 一个根结点和两个互不相交的根的左子树和右子树组成。左子树和右子树也是二叉树
  • 空二叉树:n=0

2.满二叉树

定义:一棵高度为h,且只有$2^h-1$个结点的二叉树(除了叶子结点,所有结点都有两个子树)

满二叉树特点:

  1. 只有最后一层有叶子结点
  2. 不存在度为1的结点
  3. 按上图编号,则结点i的左孩子为2i,有孩子为2i+1,双亲结点为$\f rac i2$(这个特点很重要,是我们能用顺序存储二叉树的原因)

3.完全二叉树

定义:最多只在最后两层有叶子结点,且叶子结点依次排列在该层最左边的位置

简而言之,完全二叉树就是满二叉树删除最底层右边的若干个结点

特点:

  1. 只有最后两层可能有叶子结点
  2. 最多只有一个度为1的结点
  3. (同满二叉树):按上图编号,则结点i的左孩子为2i,有孩子为2i+1,双亲结点为$\f rac i2$(这个特点很重要,是我们能用顺序存储二叉树的原因)
  4. i≤$\frac n2$为分支结点,否则为叶子结点

4.几个特殊的二叉树

二叉排序树:

左子树上所有结点的数据域均小于根结点的数据域

右子树上所有结点的数据域均大于根节点的数据域

左右子树又各是一棵二叉排序树

常用于元素的排序和搜索

平衡二叉树:

树上任意结点的左子树和右子树的深度之差不超过1.

平衡二叉树的搜索效率更高。

四.二叉树的存储结构

1.顺序存储

上面的介绍可以看出,树按从上到下,从左到右层序编号可以反应结点的逻辑关系,也是树能连续存储的关键,而且各结点在一片连续存储单位的存放顺序也是按照该层序编号进行排序的。

对于非完全树,我们要把它补上虚结点补成完全树再进行编号,然后去掉虚结点,如图所示:

去掉虚结点,最终的编号:

在内存中的位置("#"表示空结点):

结论:可以看到,一般二叉树采用顺序存储时,浪费的空间较多,而且插入、删除等操作也不方便(顺序存储的普遍缺点),因此,完全二叉树或满二叉树采用顺序存储能节省内存,但一般二叉树通常采用下面的链式存储方式。

2.链式存储

二叉树的链式存储结点结构一般为:一个数据域(data),左指针域(lchile)和右指针域(rchild),两个指针域分别指向左孩子结点和右孩子结点。这种链式存储结构也称为二叉链

代码:

typedef struct node
{
    ElemType data;
    struct node * lchild;   //指向左孩子结点
    struct node * rchild;   //指向右孩子结点
}BTNode;

优点:

比较节省存储空间,访问结点的孩子很方便。

但访问结点的双亲需要扫描所有结点,又是为了高效访问双亲结点,可以再添加一个双亲的指针域parent。

五.二叉树的基本运算(代码实现)

基本运算主要有:遍历输出二叉树、创建二叉树、销毁二叉树、查找结点、找孩子结点、求高度

1.遍历输出二叉树

由于二叉树的树形结构,遍历次序不同于线性结构从头至尾这样简单的遍历方式。

有四种遍历方法:前序遍历,中序遍历,后序遍历,层序遍历(了解即可)。

“前、中、后”主要指的是访问根结点的时间,可以在代码上看出这三种遍历十分相似。

前序遍历:

访问顺序:根 → 左子树 → 右子树。

如图,前序遍历访问结果为: ABDG H C E I F

代码:

void PreOrderTraverse(BTNode *b)
{
    if(b != NULL)   
    {
        printf("%c ",b->data);          //先访问根结点
        PreOrderTraverse(b->lchild);    //再访问左子树
        PreOrderTraverse(b->rchild);    //最后访问右子树
    }
}

中序遍历:

访问顺序:左子树 → 根结点 → 右子树

如图,中序遍历访问结果为:GDH B A EI C F

代码:

void PreOrderTraverse(BTNode *b)
{
    if(b != NULL)   
    {
        PreOrderTraverse(b->lchild);    //先访问左子树
        printf("%c ",b->data);          //再访问根结点
        PreOrderTraverse(b->rchild);    //最后访问右子树
    }
}

后序遍历:

访问顺序:左子树 → 右子树 → 根结点

如图,后序遍历访问结果为:GHD B IE F C A

代码:

void PreOrderTraverse(BTNode *b)
{
    if(b != NULL)   
    {
        PreOrderTraverse(b->lchild);    //先访问左子树
        PreOrderTraverse(b->rchild);    //再访问右子树
        printf("%c ",b->data);          //最后访问根结点
    }
}

层序遍历(了解即可):

从上向下从左到右 逐层遍历

如图,层序遍历访问结果为:A BC DEF GHI

(不要求掌握代码)

2.创建二叉树

我们之前已经学会了标一般二叉树的序号(添加虚结点补成完全二叉树,再把虚结点去掉),就用这个序号代表我们的二叉树进行输入(用“#”表示空指针),如,下图所示的二叉树,创建时输入的是:ABCDE#F##GH##I

代码:

void CreateBTree(BTNode *& b)
{
    ElemType ch;
    scanf("%c",&ch);
    if(ch == '#')
        b = NULL;   //输入的是#则赋值空指针
    else
    {
        b = (BTNode *) malloc(sizeof(BTNode));
        b->data = ch;   //赋值根结点
        CreateBTree(b->lchild);  //左子树
        CreateBTree(b->rchild);  //右子树
    }
}

建立二叉树,用的也是递归的原理。类似于前序遍历,不过是将 打印结点的地方 换成了 赋值生成结点。

3.销毁二叉树

递归,依次释放左子树结点、右子树结点、根结点

void DestroyBTree(BTNode *& b)
{
    if(b != NULL)
    {
        DestroyBTree(b->lchild);
        DestroyBTree(b->rchild);
        free(b);
    }
}

4.查找结点

注:要找的是结点,所以返回值是 BTNode* 结点地址的类型。

BTNode *FindNode(BTNode *b, ElemType x)  //x是要找的值
{
    BTNode *p;
    if (b == NULL)   //空树
        return NULL;
    else if (b->data == x)  //找到了
        return b;
    else {
        p = FindNode(b->lchild, x);  //递归遍历左子树
        if (p != NULL)
            return p;
        else
            return FindNode(b->rchild, x);  //遍历完左子树找不到,递归遍历右子树
    }
}

5.找孩子结点

直接返回左孩子或右孩子的地址,返回的仍是 BTNode* 结点地址。

BTNode *LchildNode(BTNode *p)  //返回左孩子结点
{
    return p->lchild;
}

BTNode *RchildNode(BTNode *p)  //返回右孩子结点
{
    return p->rchild;
}

6.求高度

递归求左子树和右子树的高度,最后树的高度=左子树高度和右子树高度中的最大值 + 1

int BTHeight(BTNode *b) {
    int lchildh, rchildh;
    if (b == NULL) return 0;
    else {
        lchildh = BTHeight(b->lchild);
        rchildh = BTHeight(b->rchild);
        return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
    }
}

7.总代码

#include <stdio.h>
#include "malloc.h"

#define MaxSize 20

typedef char ElemType;

typedef struct node {
    ElemType data;
    struct node *lchild;   //指向左孩子结点
    struct node *rchild;   //指向右孩子结点
} BTNode;

//先序遍历输出二叉树
void PreOrderTraverse(BTNode *b) {
    if (b != NULL) {
        printf("%c ", b->data);          //先访问根结点
        PreOrderTraverse(b->lchild);    //再访问左子树
        PreOrderTraverse(b->rchild);    //最后访问右子树
    }
}

//创建二叉树
void CreateBTree(BTNode *&b) {
    ElemType ch;
    scanf("%c", &ch);
    if (ch == '#')
        b = NULL;   //输入的是#则赋值空指针
    else {
        b = (BTNode *) malloc(sizeof(BTNode));
        b->data = ch;   //根结点
        CreateBTree(b->lchild);  //左子树
        CreateBTree(b->rchild);  //右子树
    }
}

//销毁二叉树
void DestroyBTree(BTNode *&b) {
    if (b != NULL) {
        DestroyBTree(b->lchild);
        DestroyBTree(b->rchild);
        free(b);
    }
}

//查找结点
BTNode *FindNode(BTNode *b, ElemType x)  //x是要找的值
{
    BTNode *p;
    if (b == NULL)   //空树
        return NULL;
    else if (b->data == x)  //找到了
        return b;
    else {
        p = FindNode(b->lchild, x);  //递归遍历左子树
        if (p != NULL)
            return p;
        else
            return FindNode(b->rchild, x);  //遍历完左子树找不到,递归遍历右子树
    }
}

//找孩子结点
BTNode *LchildNode(BTNode *p)  //返回左孩子结点
{
    return p->lchild;
}

BTNode *RchildNode(BTNode *p)  //返回右孩子结点
{
    return p->rchild;
}

//求二叉树高度
int BTHeight(BTNode *b) {
    int lchildh, rchildh;
    if (b == NULL) return 0;
    else {
        lchildh = BTHeight(b->lchild);
        rchildh = BTHeight(b->rchild);
        return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
    }
}

六.线索二叉树

七.哈夫曼树

八.并查集

并查集主要用于集合合并,以及查找某个值在哪个集合里。例如:

思想:用一棵树表示一个集合,树的根作为该集合的代表。多个集合形成一个森林。

1.存储结构

我们采用树的双亲表示法来存储并查集

typedef struct {		//并查集类型定义
    int parent[size];		//双亲指针数组
} MFSets;

2.基本运算

有三个操作:初始化、查找、合并

初始化

并查集的初始化是指将其中n个元素转化为n个只包含一个元素的集合,即创建n棵只有根结点的树。

初始化时,我们将根结点的parent域初始化为-1。(因此其他结点parent域父结点坐标,非负数,用-1表示根结点避免和他们混淆)

void initMFSets (MFSets& S, int n ){   //初始化
    for ( int i = 0; i < n; i++ )
        S.parent[i] = -1;	       //每个自成单元素集合
}

查找

因为每个树以其根结点作为代表,所以查找即为找该结点所在树的根结点,返回根结点下标x。

int find (MFSets& S, int x ) {

    while (S.parent[x] >= 0)    //函数从x开始,沿双亲链搜索到树的根
        x = S.parent[x];	//根的parent值小于0 
    return x;
}

如果我们要判断x和y是否同一个集合里,只需:判断find(S,x) == find(S,y)是否为True即可。

合并

有两种合并方法:按树的结点个数合并、按树的高度合并

按树的结点个数合并

我们可以用根结点的parent域来存 树结点个数*(-1),如下图:

合并时,把元素少的树加到元素多的树上。

很明显,合并这两个树,我们只要修改原来两个树根结点的parent域即可。

//按树的结点个数合并 
int merge(MFSets& S, int R1, int R2) {
    //把两个不相交集合R1与R2合并为一个集合。
    int x = S.parent[R1] + S.parent[R2];    //元素总个数
    if ( S.parent[R1] <= S.parent[R2] ) {   //R1的元素多
        S.parent[R1] = x;                   //R1成为合并后的根
        S.parent[R2] = R1;
        return R1;
    }
    else {		  	            //否则R2的元素多
        S.parent[R2] = x;   	            //R2成为合并后的根
        S.parent[R1] = R2;
        return R2;
    }
}

按树的高度合并

根结点的parent域存放 该树的高度*(-1),合并时把矮的树加到高的树上。

想一下下面这种情况:

若按树的结点个数进行合并, 合并后树的高度是4.

若按树的高度进行合并,合并后树的高度是3。

树的高度少1,查找最底层结点的时候就能少查1次。

代码:

int MergeByHeight (MFSets& S, int R1, int R2 ) {
    //把两个不相交集合R1与R2合并为一个集合。
    int x = S.parent[R1], y = S.parent[R2];  
    if ( x <= y ) {		 //R1高,成为合并后的根
        if ( x == y )		 //高度相等, 
            S.parent[R1]--;	 //根高度加一,负数表示应减1
        S.parent[R2] = R1;
        return R1;
    }
    else {			 //R2高,成为合并后的根
        S.parent[R1] = R2;
        return R2;
    }
}