树与二叉树

树

树的基本概念


$\emptyset$ 空树:结点数为0的树
非空树的特性：

  • 有且仅有一个根结点
  • 没有后继的结点称为叶子结点(或终端节点)
  • 有后继的结点称为分支结点(或非终端结点)
  • 除了根结点外，任何一个结点都有且仅有一个前驱

树是n（n≥0）个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

  1. 有且仅有一个特定的称为根的结点。
  2. 当n>1时，其余结点可分为m（m>0）个互不相交的有限集合 $T_{1}$，$T_{2}$..,$T_{m}$，其中每个集合本身又是一棵树，并且称为根结点的子树。

树是一种递归定义的数据结构

结点之间的关系描述

  • 祖先结点
  • 子孙结点
  • 双亲结点(父结点)
  • 孩子结点
  • 兄弟结点
  • 堂兄弟结点
  • 两个结点之间的路径:只能从上往下
  • 路径长度:经过了几条边

结点、树的属性描述

  • 结点的层次(深度)——从上往下数(默认从1开始)
  • 结点的高度——从下往上数
  • 树的高度(深度)——总共多少层
  • 结点的度——有几个孩子(分支)
  • 树的度——各结点的度的最大值

有序树VS无序树

  • 有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
  • 无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

森林

森林是m(m≥0)棵互不相交的树的集合
考点：森林和树相互转化问题

知识回顾与重要考点

树的常考性质

  1. 结点数=总度数+1

  2. 度为m的树、m叉树的区别
    树的度——各结点的度的最大值

    度为m的树 m叉树
    任意结点的度≤m(最多m个孩子) 任意结点的度≤m(最多m个孩子)
    至少有一个结点度=m(有m个孩子) 允许所有结点的度都<m
    一定是非空树，至少有m+1个结点 可以是空树

  3. 度为m的树第i层至多有$m^{i-1}$个结点(i≥1)
    m叉树的第i层至多有$m^{i-1}$个结点(i≥1)

  4. 高度为h的m叉树至多有$\frac{m^{h}-1}{m-1}$个结点

  5. 高度为h的m叉树至少有h个结点
    高度为h、度为m的树至少有h+m+1个结点

  6. 具有n个结点的m叉树的最小高度为$\log_{m}{n(m-1)+1}$
    高度最小：所有结点都有m个孩子
    $\frac{m^{h-1}-1}{m-1}$<n≤$\frac{m^{h}-1}{m-1}$
    $h_{min}$=$\log_{m}{n(m-1)+1}$

知识回顾与重要考点

二叉树

二叉树的基本概念

二叉树是n(n≥0)个结点的有限集合

  1. 或者为空二叉树，即n=0
  2. 或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树分别是一棵二叉树

特点

  1. 每个结点至多只有两个子树
  2. 左右子树不能颠倒(二叉树是有序树)

二叉树的五种状态

  1. 空二叉树
  2. 只有左子树
  3. 只有右子树
  4. 只有根节点
  5. 左右子树都有

几个特殊的二叉树

满二叉树

满二叉树 一棵高度为h，且含有$2^{h-1}$-1个结点的二叉树
特点

  1. 只有最后一层有叶子结点
  2. 不存在度为1的结点
  3. 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父节点为$\frac{1}{2}$ (向下取整)

完全二叉树

完全二叉树 当且仅当其每个结点都与高度h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树(在满二叉树的基础上可去掉若干个编号更大的结点)

特点

  1. 只有最后两层可能有叶子结点
  2. 最多只有一个度为1的结点
  3. 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父节点为[$\frac{1}{2}$]
  4. i≤[$\frac{n}{2}$]为分支结点，i>[$\frac{n}{2}$]为叶子结点

二叉排序树

二叉排序树 一棵二叉树或者空二叉树，或者是具有如下性质的二叉树
左子树上所有结点的关键字均小于根节点的关键字；
右子树上所有结点的关键字均大于根节点的关键字。
左子树和右子树又各是一个二叉排序树

例如需要查找关键字为60的结点
从根节点开始，60>19,所以在右子树上
60>50,所以在右子树上
60<66,所以在左子树上
60==60，左子树上的就是所找关键字为60的结点

二叉排序树可用于元素的排序、搜索

平衡二叉树

平衡二叉树 书上任一结点的左子树和右子树深度相差小于1

知识回顾与重要考点

二叉树的常考性质

  1. 设非空二叉树中度为0、1、2的结点个数分别为 $n_{0}$、$n_{1}$、$n_{2}$,则 $n_{0}$=$n_{2}$+1(叶子结点比二分支结点多一个)
    假设树中结点总数为n，则

    1. n=$n_{0}$+$n_{1}$+$n_{2}$
    2. n=$n_{1}$+2$n_{2}$+1(树的结点数=总度数+1)

    2-1得：$n_{0}$=$n_{2}$+1

  2. 二叉树第i层至多有$2_{i-1}$个结点(i≥1)
    m叉树第i层至多有$m_{i-1}$个结点(i≥1)

  3. 高度为h的二叉树至多有$2^{h}-1$个结点(满二叉树)
    高度为h的m叉树至多有$\frac{m^{h}-1}{m-1}$个结点

完全二叉树的常考性质

  1. 具有n(n>0)个结点的完全二叉树的高度h为[$\log_{2}{n+1}$]或[$\log_{2}{n}+1$]
    高为h的满二叉树共有$2^h-1$个结点
    $2^{h-1}-1$ < n ≤ $2^h-1$
    化简得h=[$\log_{2}{n+1}$]

高度为h的二叉树至少有$2^{h-1}$个结点，至多$2^h-1$个结点
$2^{h-1}$≤n<$2^h$
化简得[$\log_{2}{n}+1$]
第i个结点所在层次为[$\log_{2}{n+1}$]或[$\log_{2}{n}+1$]
2. 对于完全二叉树，可以由结点数n推出度为0、1、2的结点个数$n_{0}$、$n_{1}$、$n_{2}$
完全二叉树**最多** 只有**一个度为1**的结点，即$n_{1}$=1或0
$n_{0}$=$n_{2}$+1->$n_{0}$+$n_{2}$一定为奇数
若完全二叉树有2k(偶数)个结点，则$n_{1}$=1，$n_{0}$=k,$n_{2}$=k-1
若完全二叉树有2k-1(奇数)个结点，则$n_{1}$=0，$n_{0}$=k,$n_{2}$=k-1

知识回顾与重要考点

二叉树：

  • $n_{0}$=n²+1
  • 第i层至多有$2^{i-1}$个结点（i≥1）
  • 高度为h的二叉树至多有$2^h$一1个结点

完全二叉树：

  • 具有n个（n>0）结点的完全二叉树的高度h为[$\log_{2}(n+1)]$或[$\log_{2}{n}]$+1
  • 对于完全二叉树，可以由的结点数n推出为0、1和2的结点个数为$n_{0}$、$n_{1}$
    和$n_{2}$（突破点：完全二叉树最多只会有一个度为1的结点）

二叉树的顺序存储

1
2
3
4
5
#define MAXSIZE 100
typedef struct TreeNode{
    int value;//结点中的数据元素
    bool isEmpty;//结点是否为空
}TreeNode;

定义一个长度为MAXSIZE的数组t，按照从上至下，从左至右的顺序依次存储完全二叉树中的各个结点
可以让第一个位置空缺，这样就可以让数组下标和结点编号一致

1
2
3
4
TreeNode t[MAXSIZE];
for(int i=1;i<MAXSIZE;i++){
    t[i].isEmpty=true;
}//初始化时所有结点标记为空
  • 几个常考的基本操作
    • i的左孩子——2i
    • i的右孩子——2i+1
    • i的父节点——[$\frac{i}{2}$]
    • i所在的层次[$\log_{2}{(i+1)}$]或[$\log_{2}{i}$]+1
  • 若完全二叉树中共有n个结点，则
    • 判断i是否有左孩子——2i≤n?
    • 判断i是否有右孩子——2i+1≤n?
    • 判断i是否时分支结点/叶子结点——i>[$\frac{n}{2}$]?

如果不是完全二叉树，依然按层次将各节点顺序存储，那么无法从结点编号反映结点间的逻辑结构
二叉树的顺序存储中，一定要将二叉树的结点编号与完全二叉树的编号对应起来，这样就可以通过i来求出i结点的左孩子、右孩子、父节点、所在层次。
但是不能通过i和n判断是否有左孩子、右孩子、是否为分支节点/叶子结点，可以通过求出i结点的左孩子、右孩子，然后再通过isEmpty判断是否存在左孩子、右孩子
最坏情况：高度为h且且只有h个结点的单支树(所有结点都只有右孩子)，也至少需要$2^{h}$-1个存储单元
结论：二叉树的顺序存储结构，只适合存储完全二叉树

二叉树的链式存储

1
2
3
4
typedef struct BitNode{
    int data;
    struct BitNode *lchild,*rchild;
}BitNode,*BiTree;

n个结点的二叉链表共有n+1个空链域(可以构造线索二叉树) 

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
31
typedef struct BitNode{
    int data;
    strcut BitNode *lchild,*rchild;
}BitNode,*BiTree;
//定义一个空树
BiTree root=NULL;
//插入根节点
root=(BiTree)malloc(sizeof(BiTree));
root->data=1;
root->lchild=NULL;
root->rchild=NULL;
//插入新结点
BitNode *p=(BitNode)malloc(sizeof(BitNode));
p->data=2;
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;//作为根节点的左孩子 
```  



找到指定结点p的左右孩子只需要检查lchild和rchild指针即可，但是找到父节点需要从根节点遍历  
如果经常需要寻找父节点的话，可以在结构体中再定义一个指针，指向父节点，形成三叉链表，方便寻找父节点 


```cpp
typedef struct BitNode{
    int data;
    struct BitNode *lchild,*rchild;
    struct BitNode *parent;
}BitNode,*BiTree;

知识回顾与重要考点


二叉树的先中后序遍历

什么是遍历

遍历：按照某种次序把所有结点都访问一遍
层次遍历：基于树的层次特性确定的次序规则

二叉树的遍历

二叉树的递归特性

  • 要么是空二叉树
  • 要么就是由根节点+左右子树组成的二叉树
  1. 先序遍历：根左右(NLR)
  2. 中序遍历：左根右(LNR)
  3. 后序遍历：右根左(RNL)

手算

分支结点逐层展开法

机算

  1. 先序遍历
    1. 若二叉树为空，则什么也不做
    2. 若二叉树非空：
      1. 访问根节点
      2. 先序遍历左子树
      3. 先序遍历右子树
  2. 中序遍历
    1. 若二叉树为空，则什么也不做
    2. 若二叉树非空：
      1. 中序遍历左子树
      2. 访问根节点
      3. 先序遍历右子树
  3. 中序遍历
    1. 若二叉树为空，则什么也不做
    2. 若二叉树非空：
      1. 后序遍历左子树
      2. 后序遍历右子树
      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
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}
//后序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T); 
    }
}
  • 例：求树的深度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int TreeDepth(BiTree T){
        if(T==NULL){
            return 0;
        }
        else{
            int l=TreeDepth(T->lchild);
            int r=TreeDepth(T->rchild);
        }
        //树的深度=Max(左子树深度，右子树深度)+1
        return l>r?l+1:r+1;
    }

知识回顾与重要考点

二叉树的层序遍历


算法思想：

  1. 初始化一个辅助队列
  2. 根节点入队
  3. 若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾(如果有的话)
  4. 重复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
    typedef struct BiTNode{
        int data;
        struct BiTNode lchild,rchild;
    }BiTNode,*BiTree;
    typedef struct LinkNode{
        BiTNode *data;
        struct LinkNode *next;
    }LinkNode;
    typedef struct {
        LinkNode *front,*rear;
    }LinkQueue;
    void LevelOrder(BiTree T){
        LinkQueue Q;
        InitQueue Q;
        BiTree p;
        EnQueue(Q,T)//将根节点入队
        while(!IsEmpty(Q)){//队列不空则循环
            DeQueue(Q,p);//对头结点出队
            visit(p);//访问出队结点
            if(p->lchild!=NULL){
                EnQueue(Q,p->lchild);//左孩子入队
            }
            if(p->rchild!=NULL){
                EnQueue(Q,p->rchild)l;//右孩子入队
            }
        }
    }

由遍历序列构造二叉树

结论：若只给出一颗二叉树的前/中/后/层序遍历中的一种，不能唯一确定一种二叉树
但若给出中的两种，可以唯一确定一种二叉树

前序+中序遍历序列


例：前序：A D B C E
中序：B D C A E
前序遍历序列的第一个一定是根节点，所以A为根节点，BDC为左子树的中序遍历，DBC是左子树的前序遍历，同理，D为左子树的根节点，B为左孩子，C为右孩子

例：前序：D A E F B C H G I
中序：E A F D H C B G I
由前序遍历序列知，D为根节点，再看中序知EAF为左子树的中序遍历序列,HCBGI为右子树的中序遍历序列，再看前序遍历序列，AEF为左子树的前序遍历序列，A为左子树的根节点，E为左孩子，F为右孩子，B为右子树的根节点，HC为左孩子的中序遍历序列，GI为右孩子的中序遍历序列，由前序遍历序列知，C和G为根节点。

后序+中序遍历序列


例：后序：E F A H C I G B D
中序：E A F D H C B G I
先看后序，D在最后，为根节点，所以EAF为左子树的中序，HCBGI为右子树的中序，A为左子树的根，E为左子树的左孩子，F为左子树的右孩子。B为右子树的根，HC为左子树的中序，GI为右子树的中序，C和G为根

层序+中序遍历序列


例：层序：D A B E F C G H I
中序：E A F D H C B G I
看层序，D为根节点，所以EAF为左子树的中序，HCBGI为右子树的中序，A为左子树的根，E为左子树的左孩子，F为左子树的右孩子，B为右子树的根，HC为右子树的左子树的中序，GI为右子树的右子树的中序，C和G为根节点

例：层序：A B C D E
中序：A C B E D
A为根节点，CBED为右子树，B为右子树的根，ED为右子树的右子树的中序，C为右子树的左孩子，D为右子树的右子树的根

知识回顾与重要考点


结论：前序、后序、层序两两组合无法唯一确定一棵二叉树

线索二叉树

线索二叉树的作用

二叉树每次遍历都需要从根节点开始，不能做到从给定的一个结点开始遍历

中序遍历序列


思路：从根节点出发，再进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点，当p==q时，pre为前驱;当pre==p时，q为后继结点

1
2
3
4
5
6
7
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

缺点：找前驱、后继不方便，每次遍历都需要从根结点开始

三种线索二叉树

中序线索二叉树


n个结点的二叉树，有n+1个空链域，可以用来存放前驱后继
指向前驱后继的指针称为线索

1
2
3
4
5
6
typedef struct ThreadNode{
    int data;
    struct ThreadNode *lchild,*rchild*;
    int ltag,rtag;//左右线索标志
}TreadNode,*TreadTree;
//tag==0，说明指针指向孩子，tag==1，说明指针是线索

先序线索二叉树


后序线索二叉树


知识回顾与重要考点

二叉树的线索化

用土方法找到中序前驱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void FindPre(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}
void visit(BiTNode *q){
    if(q==p){
        _final=pre;
    }
    else{
        pre=q;
    }
}
BiTNode *p;
BiTNode *_final=NULL;
BitNode *pre=NULL;

中序线索化二叉树

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
31
32
33
34
typedef struct ThreadNode{
    int data;
    struct ThreadNode *rchild,*lchild;
    int rtag,ltag;
}ThreadNode,*ThreadTree;

void InThread(ThreadTree T){
    InThread(T->lchild);
    visit(T);
    InThread(T->rchild);
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){/左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;//建立前驱结点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

ThreadNode *pre=NULL;
void CreatInThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        InThread(T);
        if(pre->rchild==NULL){
            pre->rtag=1;//处理遍历的最后一个结点
        }
    }
}

先序线索化二叉树

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
31
32
33
34
35
typedef struct ThreadNode{
    int data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;

void PreThread(ThreadTree T){
    visit(T);
    if(T->ltag==0)
        PreThread(T->lchild);//lchild不是前驱结点
    PreThread(T->rchild);
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}

void CreatPreThread(ThreadTree T){
    if(T!=NULL){
        PreThread(T);
        if(pre->rchild==NULL){
            pre->rtag=1;
        }
    }
}

ThreadNode *pre=NULL;

后序线索化二叉树

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
31
typedef struct ThreadNode{
    int data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;
void PostThread(ThreadTree T){
    PostThread(T->lchild);
    PostThread(T->rchild);
    visit(T);
}
void visit(ThreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
void CreatPostThread(ThreadTree T){
    if(T!=NULL){
        pre=NULL;
        PostThread(T);
        if(pre->rchild==NULL){
            pre->rtag=1;
        }
    }
}
ThreadNode *pre=NULL;

知识回顾与重要考点

线索二叉树找前驱/后继

中序线索二叉树

  • 在中序线索二叉树找到指定结点*p的中序后继*next
    1. 若p->rtag==1，则next=p->rchild
    2. 若p->rtag==0，则next=p右子树最左下的结点 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      ThreadNode *FirstNode(ThreadNode *p){
          //循环找到最左下的结点
          while(p->ltag==0){
              p=p->lchild
          }
          return p;
      }
      //在中序线索二叉树中找到结点p的后继结点
      ThreadNode *NextNode(ThreadNode *p){
          if(p->rtag==1)return p->rchild;
          else return FirstNode(p->rchild);
      }
      //对中序二叉树可以进行不用递归的中序遍历，利用线索实现
      void InOrder(ThreadTree T){
          for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p)){
              visit(p);
          }
      }
  • 在中序线索二叉树找到指定结点*p的中序前驱*pre
    1. 若p->ltag==1,则next=p->lchild
    2. 若p->ltag==0,则next=p左子树最右下角的结点 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      ThreadNode *LastNode(ThreadNode *p){
          while(p->rtag==0){
              p=p->rchild;
          }
          return p;
      }
      ThreadNode *PreNode(ThreadNode *p){
          if(p->ltag==1)return p->lchild;
          else return LastNode(p->lchild);
      }
      //对中序线索二叉树进行逆向中序遍历
      void RevInOrder(ThreadTree T){
          for(ThreadNode *p=T;p!=NULL;p=PreNode(p)){
              visit(p);
          }
      }

先序线索二叉树

  • 在先序线索二叉树中找到指定结点*p的后继结点*next
    1. 若p->rtag==1,则next=p->rchild
    2. 若p->rtag==0,若p有左孩子，则next为左孩子，若没有左孩子，则next为右孩子 
      1
      2
      3
      4
      5
      6
      7
      ThreadNode *NextNode(ThreadNode *p){
          if(p->rtag==1)return p->rchild;
          else if(p->ltag==0){
              return p->lchild;
          }
          else return p->rchild;
      }
  • 在先序线索二叉树中找到指定结点*p的前驱结点*pre
    1. 若p->ltag==1,则pre=p->lchild
    2. 若p->ltag==0,则找不到前驱结点，但是可以将二叉链表改为三叉链表，即在每个结点设置指向其父节点的指针

      若p是根节点，则p没有先序前驱

后序线索二叉树

  • 在后序线索二叉树中找到指定结点*p的前驱结点*pre
    1. 若p->ltag==1,则pre=p->lchild
    2. 若p->ltag==0,若p有右孩子，则后序前驱为右孩子，若p没有右孩子，则后序前驱为左孩子 
      1
      2
      3
      4
      5
      ThreadNode *PreNode(ThreadNode *p){
          if(p->ltag==1)return p->lchild;
          else if(p->rtag==0)return p->rchild;
          else return p->lchild;
      }
  • 在后序线索二叉树中找到指定结点*p的后继结点*next
    1. 若p->rtag==1,则next=p->rchild
    2. 若p->rtag==0,则找不到前驱结点，但是可以将二叉链表改为三叉链表，即在每个结点设置指向其父节点的指针

知识回顾与重要考点

中序线索二叉树 前序线索二叉树 后序线索二叉树
找前驱 √ × √
找后继 √ √ ×

树的存储结构

树的逻辑结构

树是n（n≥0）个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

  1. 有且仅有一个特定的称为根的结点。
  2. 当n>1时，其余结点可分为m（m>0）个互不相交的有限集合 $T_{1}$，$T_{2}$..,$T_{m}$，其中每个集合本身又是一棵树，并且称为根结点的子树。

树是一种递归定义的数据结构

双亲表示法(顺序存储)

用数组顺序存储各个结点。每个结点存储数据元素和指向双亲结点的指针

根结点的双亲指针=-1，非根结点的双亲指针=父节点的数组下标

1
2
3
4
5
6
7
8
9
#define MAX_TREE_SIZE 100
typedef struct {//树的结点定义
    int data;//数据元素
    int parent;//双亲位置域
}PTNode;
typedef struct{//树的类型定义
    PTNode nodes[MAX_TREE_SIZE];//双亲表示
    int n;//结点数
}PTree;

双亲表示法也可以存储森林
双亲表示法的优缺点

  • 优点：找双亲方便
  • 缺点：找孩子不方便，只能从头到尾遍历数组
  • 适用于找双亲多，孩子少的场景，如：并查集

孩子表示法(顺序+链式存储)

用数组顺序存储各个结点。每个结点保存数据元素、孩子链表头指针

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAX_TREE_SIZE 100
struct CTNode{
    int child;//孩子结点在数组的位置
    struct CTNode *next;//下一个孩子
}
typedef struct{
    int data;
    struct CTNode *firstchild;//第一个孩子
}CTBox;
typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;//结点和根的位置
}CTree

用孩子表示法表示森林，需要记录多个根的位置
孩子表示法的优缺点

  • 优点：找孩子方便
  • 缺点：找双亲不方便，只能遍历每个链表
  • 适用于找孩子多，找双亲少的场景，如：服务流程树

兄弟孩子表示法(链式存储)

1
2
3
4
typedef struct CSNode{
    int data;
    struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;

树的兄弟孩子表示法与二叉树类似，采用二叉链表实现，每个节点内保存数据元素和两个指针，但两个指针的含义与二叉树结点不同

拓展：用兄弟孩子表示法存储森林：森林中的每一棵树的根节点视为平级的兄弟关系

知识回顾与重要考点

树、森林、二叉树的转换

本质：用兄弟孩子表示法存储树或森林时，在形态上与二叉树类似

树->二叉树的转换

  1. 先在二叉树中，画出一个根节点
  2. 按照树的层序，依次处理每个结点
  3. 处理结点的方法：如果当前处理的结点在树中有孩子，就把所有的孩子结点用右指针串起来，并在二叉树中把第一个孩子结点挂在当前结点的左指针下方

森林->二叉树的转换

森林中各棵树的根节点视为平级的兄弟关系

  1. 先把所有树的根节点画出来，在二叉树中用右指针串起来
  2. 按森林的层序依次处理每个结点
  3. 处理结点的方法：如果当前处理的结点在树中有孩子，就把所有孩子结点用右指针串起来，并在二叉树中把第一个孩子挂在当前结点的左指针下方

二叉树->树的转换

  1. 先画出树的根节点
  2. 从树的根节点开始，按树的层序恢复每个结点的孩子
  3. 恢复结点孩子的方法：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和一整串右指针拆下来，按顺序挂在当前结点的下方

二叉树->森林的转换

  1. 先把二叉树的根节点和一整串右指针拆下来，作为多棵树的根节点
  2. 按照森林的层序恢复每个结点的孩子
  3. 恢复结点孩子的方法：在二叉树中，如果当前处理的结点有左孩子，就把左孩子和一整串右指针拆下来，按顺序挂在当前结点的下方

知识回顾与重要考点

树、森林的遍历

树的遍历

树的先根遍历(深度优先遍历)

若树非空，先访问根节点，再依次对每棵子树进行先根遍历

1
2
3
4
5
6
7
void PreOrder(TreeNode *R){
    if(R!=NULL){
        visit(R);
        while(R还有下一个子树T)
            PreOrder(T);
    }
}

树的先根遍历序列与这棵树对应二叉树的先序序列相同

树的后根遍历(深度优先遍历)

若树非空，先依次对每棵子树进行后根遍历，最后再访问根节点

1
2
3
4
5
6
7
void PostOrder(TreeNode *R){
    if(R!=NULL){
        while(R还有下一个子树T)
            PostOrder(T);
        visit(R);
    }
}

树的后根遍历序列和这棵树相应二叉树的中序序列相同

树的层次遍历(用队列实现)（广度优先遍历）

  1. 若树非空，则根节点入队
  2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
  3. 重复2直到队列为空

森林的遍历

森林的先序遍历

若森林非空，则按照如下规则遍历

  1. 访问森林中第一棵树的根节点
  2. 先序遍历第一棵树中根节点的子树森林
  3. 先序遍历除去第一棵树之后剩余的树构成的森林
    (效果等同于依次对各个树进行先根遍历，也可先将森林转化为二叉树，对二叉树进行先序遍历)

森林的中序遍历

  1. 中序遍历第一棵树中根结点的子树森林
  2. 访问第一棵树的根节点
  3. 中序遍历除去第一棵树之后剩余的树构成的森林
    (效果等同于依次对各个树进行后根遍历，也可以将森林转化为二叉树，对二叉树进行中序遍历)

知识回顾与重要考点

树 森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历

哈曼夫树

带权路径长度

  • 结点的权：有某些现实意义的数值(如：表示结点的重要性等)
  • 结点的带权路径长度：从树的根到该节点的路径长度(经过的边数)与该节点上权值的乘积
  • 树的带权路径长度：树中所有叶结点的带权路径长度之和(WPL)
    WPL=$\sum_{i=1}^{n}$ $w_{i}l_{i}$

哈曼夫树定义

在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树叫做哈曼夫树，也称最优二叉树

哈曼夫树的构造

给定n个权值为$w_{1},w_{2},…,w_{n}$的结点，构造哈曼夫树的算法描述如下

  1. 将这n个结点分别作为n棵仅含一个节点的二叉树，构成森林F
  2. 构造一个新结点，从F中选取两棵根节点权值最小的树作为新节点的左右子树，并将新结点的权值置为左、右子树上根节点的权值之和
  3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中
  4. 重复步骤2和3，直至F中只剩下一棵树为止

    性质:
  5. 每个初始结点最终都成为叶结点，且权值越小的结点到根节点的路径长度越大
  6. 哈曼夫树的结点总数为2n-1
  7. 哈曼夫数中不存在度为1的结点
  8. 哈曼夫树不唯一，但WPL必然相同且为最优

哈曼夫编码

  • 固定长度编码：每个字符用相等长度的二进制位表示
  • 可变长度编码：允许对不同字符用不等长的二进制位表示
  • 前缀编码：若没有一个编码时另一个编码的前缀，则称这样的编码为前缀编码(前缀码解码无歧义)
  • 由哈曼夫树得到哈曼夫编码：字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，构建哈曼夫树
  • 哈曼夫树不唯一，哈曼夫编码也不唯一
  • 哈曼夫编码可用于数据的压缩

知识回顾与重要考点