数据结构与算法(5)-树

一.树的定义

1.定义：

(1)树(Tree)是n(n≥0)个结点的有限集。n=0时称为空树

(2)在任意一棵非空树中：

• 有且仅有一个特定的称为根（Root）的结点；
• 当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树

(3)注意：

• n>0时，根结点是唯一的
• m>0时，子树的个数没有限制，但它们一定是互不相交的

2.结点的分类

(1)树的结点包含一个数据元素及若干指向其子树的分支。
(2)结点拥有的子树数称为结点的度（De-gree）
(3)度为0的结点称为叶结点（Leaf）或终端结点；
(4)度不为0的结点称为非终端结点或分支结点。
(5)除根结点之外，分支结点也称为内部结点。
(6)树的度是树内各结点的度的最大值

3.结点间的关系

(1)结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）
(2)同一个双亲的孩子之间互称兄弟（Sibling）
(3)结点的祖先是从根到该结点所经分支上的所有结点
(4)以某结点为根的子树中的任一结点都称为该结点的子孙

4.树的其他相关概念：

(1)结点的层次(Level):

从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树就在第l+1层。其双亲在同一层的结点互为堂兄弟。显然图6-2-6中的D、E、F是堂兄弟，而G、H、I与J也是堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度

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

(3)森林（Forest）是m（m≥0）棵互不相交的树的集合

(4)线性表与树的区别

二.树的抽象数据类型

三.树的存储结构

双亲表示法、孩子表示法、孩子兄弟表示法可以实现对树的存储结构的表示

1.双亲表示法

2.孩子表示法

3.孩子兄弟表示法

四.二叉树的定义

1.二叉树的特点：

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

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

(3)即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。如图所示，树1和树2是同一棵树，但它们却是不同的二叉树。

2.二叉树具有5种基本形态：

(1).空二叉树
(2).只有一个根结点
(3).根结点只有左子树
(4).根结点只有右子树
(5).根结点既有左子树又有右子树”

3.特殊二叉树

(1)斜树：

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树

(2)满二叉树：

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

(a)满二叉树的特点有：

• 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
• 非叶子结点的度一定是2。
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

(3)完全二叉树：

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

• 首先，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的
• 其次，完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一一对应的

(a)完全二叉树的特点：

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

五.二叉树的性质

1.性质一

性质1:在二叉树的第i层上至多有2^i-1个结点（i≥1）”

2.性质二

性质2：深度为k的二叉树至多有2^k-1个结点（k≥1）

3.性质三

性质3：对任何一棵二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。

4.性质四

性质4：具有n个结点的完全二叉树的深度为|log₂n+1|（|x|表示不大于x的最大整数）

5.性质五

性质5：如果对一棵有n个结点的完全二叉树（其深度为i）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：

• 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。
• 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
• 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。”

六.二叉树的存储结构

1.二叉树顺序存储结构

2.二叉链表

七.遍历二叉树

1.二叉树遍历原理

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

2.二叉树遍历方法：

(1)前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图所示，遍历的顺序为：ABDGH-CEIF

前序遍历算法：

1
2
3
4
5
6
7
8
9
10
11
12

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

(2)中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图所示，遍历的顺序为：GDHBAE-ICF

中序遍历算法：

1
2
3
4
5
6
7
8
9
10
11
12

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    /* 中序遍历左子树 */
    InOrderTraverse(T->lchild);    
    /* 显示结点数据，可以更改为其他对结点操作 */
    printf("%c", T->data);         
    /* 最后中序遍历右子树 */
    InOrderTraverse(T->rchild);    
}

(3)后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图所示，遍历的顺序为：GHDBIEFCA

后序遍历算法：

1
2
3
4
5
6
7
8
9
10
11
12

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

(4)层序遍历：

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图所示，遍历的顺序为：ABCDEFGHI

3.推导遍历结果：

(1)二叉树遍历的两个性质：

• 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

(2)已知前序和后序遍历，是不能确定一棵二叉树的

八.二叉树的建立

1.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树T。 */
void CreateBiTree(BiTree *T)
{
    TElemType ch;
    scanf("%c", &ch);
    if (ch == '#')
      *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T)
            exit(OVERFLOW);
        /* 生成根结点 */
        (*T)->data = ch;                
        /* 构造左子树 */
        CreateBiTree(&(*T)->lchild);    
        /* 构造右子树 */
        CreateBiTree(&(*T)->rchild);    
    }
}

九.线索二叉树

1.线索二叉树原理

2.线索二叉树结构实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/* 二叉树的二叉线索存储结构定义 */
/* Link==0表示指向左右孩子指针 */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum {Link, Thread} PointerTag;    
/* 二叉线索存储结点结构 */
typedef struct BiThrNode                   
{
    /* 结点数据 */
    TElemType data;                        
    /* 左右孩子指针 */
    struct BiThrNode *lchild, *rchild;     
    PointerTag LTag;
    /* 左右标志 */
    PointerTag RTag;                       
} BiThrNode, *BiThrTree;” 

3.中序遍历线索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

BiThrTree pre;                     /* 全局变量，始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
    if (p)
    {
        /* 递归左子树线索化 */
        InThreading(p->lchild);    
        /* 没有左孩子 */
        if (!p->lchild)            
        {
            /* 前驱线索 */
            p->LTag = Thread;      
            /* 左孩子指针指向前驱 */
            p->lchild = pre;       
        }
        /* 前驱没有右孩子 */
        if (!pre->rchild)          
        {
            /* 后继线索 */
            pre->RTag = Thread;    
            /* 前驱右孩子指针指向后继（当前结点p） */
            pre->rchild = p;       
        }
        /* 保持pre指向p的前驱 */
        pre = p;                   
        /* 递归右子树线索化 */
        InThreading(p->rchild);    
    }
}

十.树，二叉树，森林之间的转换

1.树转换为二叉树步骤：

(1)加线。在所有兄弟结点之间加一条连线。
(2)去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
(3)层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子

2.森林转换为二叉树步骤：

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

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

3.二叉树转化为树步骤：

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

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

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

4.二叉树转化为森林步骤：

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

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

5.树与森林的遍历

(1)树的遍历分为两种方式

• 一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树
• 另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点

(2)森林的遍历也分为两种方式：

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