ednow

0%

王道-数据结构-ch5-树和二叉树

发表于 更新于 分类于
本文字数： 17k 阅读时长 ≈ 16 分钟

王道

树与二叉树(Binary tree)

$\color{red}{\text{森林的遍历}}$

树的意义

树家族是为了实现方便快捷的$\color{red}{\text{查找}}$而存在的。树的高度是命中查找的一个不可抗拒的时间下限。在一定的数据条件下，树的高度和宽度是互相制约的。（就像一定面积下，矩形的长和宽是互相制约的）而树家族中最简单的二叉树，尽管易于实现，却不能有实际的价值。其最最令人发指的是二叉树的高度太高。n叉树的提出和实现解决了二叉树的不足，典型的n叉树有：2-3-4树/红黑树和B树。

满m叉树的性质

  • 第$i$层的节点数是多少？：$m^{i-1}(i \leq i \leq h)$
  • 编号为$i$的节点的双亲结点(若存在)的编号是多少？：$\lfloor \dfrac{i-2}{m} \rfloor + 1(i>1)$
  • 编号为$i$的结点的第$k$个孩子结点（若存在）的编号是多少?
    : $(i-1)m+k+1(1 \leq k \leq m)$
  • 编号为$i$的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?$\color{green}{\text{条件}}$：结点$i$不是其双亲的第$m$个子女时才有右兄弟。右兄弟结点的$\color{green}{\text{编号}}$：$i+1$

$\color{red}{\text{Q：}}$ $\mho$(要补充的内容) 森林和树的遍历的关系

树的基本概念

树的定义

  • 树是$n(n \geq 0)$个节点的有限集。
  • 当$n=0$时，称为空树。
  • 在任意一颗非空树中应满足:
    • 有且仅有一个特定的称为根的节点。
    • 当$n>1$时，其余节点可分为$m(m>0)$个互不相交的有限集$T_1,T_2,\cdots,T_m$,其中每个集合本身又是一颗树，并且称为根的子树
  • 树是一种分层的逻辑结构。
    • 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
    • 树中所有结点可以有零个或多个后继。
  • 树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点(即其父结点)有直接关系，根结点没有直接上层结点，因此在$n$个结点的树中有$n-1$条边。而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。

基本术语

  • 祖先:根A到结点K的唯一路径上的任意结点，称为结点K的祖先。
  • 双亲:如结点B是结点K的$\color{green}{\text{祖先}}$，而结点K是结点B的$\color{green}{\text{子孙}}$。路径上最接近结点K的结点E称为K的$\color{green}{\text{双亲}}$，而K为结点E的$\color{green}{\text{孩子}}$。根A是树中唯一没有双亲的结点。有相同双亲的结点称为$\color{green}{\text{兄弟}}$，如结点K和结点L有相同的双亲E，即K和L为兄弟。
    • 树中节点最大的度称为树的度
  • 分支节点：度大于0的结点称为分支结点(又称非终端结点);
  • 终端节点：度为0（没有子女结点）的结点称为叶子结点(又称终端结点)。在分支结点中，每个结点的分支数就是该结点的度。
  • 深度：结点的深度是从根结点开始自顶向$\color{red}{\text{下}}$逐层累加的。
  • 高度，结点的高度是从叶结点开始自底向$\color{red}{\text{上}}$逐层累加的。
  • 有序树和无序树
  • 路径和路径长度：路径和路径长度。树中两个结点之间的$\color{green}{\text{路径}}$是由这两个结点之间所经过的结点序列构成的，而$\color{green}{\text{路径长度}}$是路径上所经过的边的个数。
    • 两个孩子之间不存在路径
  • 森林

树的性质

树中的节点数等于所有节点的度加1
度为m的树中第i层上至多有$m^{i-1}$个节点($i \geq 1$)
高度为h的m叉树至多有$ \dfrac{m^h-1}{m-1}$个节点
具有n个结点的m叉树的最小高度为$\lceil log_m(n(m-1)+1) \rceil$
树节点与度的关系
  • 总结点数 = $n_0 + n_1 + n_2 + \cdots + n_m$
  • 总分支数 = $1n_1 + 2n_2 + \cdots + mn_m $(度为$m$节点引出$m$条分支)
  • 总节点数 = 总分支数 + 1

二叉树的概念

二叉树的定义及主要特性

使用$\color{red}{\text{L，N，R法}}$来理解节点出现的先后顺序

二叉树的定义
  • 度为2，子树有左右之分，不能任意颠倒
    • $\color{red}{\text{Q}}$：度为2，且有序的=二叉树？
    • $\color{green}{\text{A}}$：不是，1.度为2的有序树至少有3个节点,二叉树可以为空 2.度为2的有序树某节点只有一个孩子，该孩子的时候无需区分左右，但是二叉树需要区分子树
  • 5种基本形态
    • 空二叉树
    • 只有根节点
    • 只有左子树
    • 左右子树都有
    • 只有右子树

性质

  • 任何一棵二叉树，叶子结点个数为度为2的结点数减1，即$n_0=n_2+1$(记忆口诀：0比2多1)
几种特殊的二叉树
满二叉树

一棵高度为h，且含有$2^h-1$个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点

完全二叉树

高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。

二叉排序树

左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树。

平衡二叉树

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

二叉树的存储结构

顺序存储结构

顺序存储结构示意图

链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含3个域:数据域data、左指针域lchild和右指针域rchild，如图5.5所示。

  • 含有n个节点的二叉链表中，含有$n+1$个空链域
    • 证明：$n$个节点出度和为$n-1$(树的性质),一个$2n$个指针域，被使用的指针域即是出度和,即空指针域为$2n-(n-1)=n+1$

二叉树的遍历和线索二叉树

二叉树的遍历

  • 根节点N,左子树L，右子树R，
  • 前中后序遍历序列的$\color{red}{\text{人工求法}}$：
先序遍历(PreOrder)(NLR)

若二叉树为空，则什么也不做；否则，

访问根节点
先序遍历左子树
先序遍历右子树
1
2
3
4
5
6
7
void PreOrder (BiTree T){
    if(T!=NULL){
        visit(T);//访问根结点
        PreOrder (T->lchild);//递归遍历左子树
        PreOrder (T->rchild); //递归遍历右子树
    }
}

例图的先序遍历结果：124635

中序遍历(InOrder)(LNR)

若二叉树为空，则什么也不做；否则，

中序遍历左子树
访问根节点
中序遍历右子树
1
2
3
4
5
6
7
void InOrder (BiTree T){
    if(T!=NULL){
        InOrder (T->lchild);//递归遍历左子树
        visit(T);//访问根结点
        InOrder (T->rchild); //递归遍历右子树
    }
}

例图的中序遍历结果：264135

后序遍历(PostOrder)(LRN)

若二叉树为空，则什么也不做；否则，

后序遍历左子树
后序遍历右子树
根节点
1
2
3
4
5
6
7
void PostOrder (BiTree T){
    if(T!=NULL){
        PostOrder (T->lchild);//递归遍历左子树
        PostOrder (T->rchild); //递归遍历右子树
        visit(T);//访问根结点
    }
}

例图的后序遍历结果：642531 642153

  • 快速方法，左右中打印
以上三种方法的负责度分析
时间复杂度都是$O(n)$
空间复杂度是$O(n)$

递归工作栈的深度恰好为树的深度

递归算法和非递归算法的转换

在上节介绍的3种遍历算法中，暂时抹去和递归无关的visit语句，则3个遍历算法完全相同，因此，从递归执行过程的角度看先序、中序和后序遍历也是完全相同的。

图5.7用带箭头的虚线表示了这3种遍历算法的递归执行过程。其中，向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回;虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历的过程中访问结点时输出的信息。例如，由于中序遍历中访问结点是在遍历左子树之后、遍历右子树之前进行的，则带圆形的字符标在向左递归返回和向右递归调用之间。由此，只要沿虚线从1出发到2结束，将沿途所见的三角形（或圆形或方形)内的字符记下，便得到遍历二叉树的先序（或中序或后序）序列。例如在图5.7中，沿虚线游走可以分别得到先序序列为ABDEC、中序序列为DBEAC、后序序列为DEBCA。

借助栈，来分析中序遍历的访问过程:

沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点，此时栈内元素依次为AB D。②栈顶元素出栈并访问:若其右孩子为空，继续执行②;若其右孩子不空，将右子树转执行①。栈顶D出栈并访问，它是中序序列的第一个结点;D右孩子为空，栈顶B出栈并访问;B右孩子不空，将其右孩子E入栈，E左孩子为空，栈顶E出栈并访问;E右孩子为空，栈顶A出栈并访问;A右孩子不空，将其右孩子C入栈，C左孩子为空，栈顶C出栈并访问。由此得到中序序列DBEAC。

根据分析可以写出中序遍历的非递归算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
void Inorder2 (BiTree T){
  InitStack(S);BiTree p=T;//初始化栈s;p是遍历指针
  while(plI!ISEmpty (S)){//栈不空或p不空时循环
    if(p){//一路向左
      Push (S,p);//当前结点入栈
      p-p->lchild;//左孩子不空,一直向左走
    }
    else{//出栈,并转向出栈结点的右子树
      Pop (s,p);//栈顶元素出栈,访问出栈结点p-p->rchild;
      visit(p) ;//向右子树走,p赋值为当前结点的右孩子
    }//返回while循环继续进入if-else语句
  }
}

先序遍历和中序遍历的基本思想是类似的，只需把访问结点操作放在入栈操作的前面，可以参考中序遍历的过程说明自行模拟出入栈示意图。先序遍历的非递归算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
void PreOrder2(BiTree T){
  InitStack(S); BiTree p=T;//初始化栈S;p是遍历指针
  while(p || !IsEmpty(S)){//栈不空或p不空时循环
    if(p){//一路向左
      visit(p);Push (s,p);//访问当前结点,并入栈p=p->lchild;
      p=p->lchild; //左孩子不空,一直向左走
    }
    else{//出栈,并转向出栈结点的右子树
      Pop (s,p);//栈顶元素出栈
      p=p->rchild;//向右子树走，p赋值为当前结点的右孩子
    }//返回while循环继续进入if-else语句
  }

后序遍历的非递归实现是三种遍历方法中最难的。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。

后序非递归遍历算法的思路分析:从根结点开始,将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，但是此时不能出栈并访问，因为如果其有右子树，还需按相同的规则对其右子树进行处理。直至上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完（此时左子树早已访问完)，这样就保证了正确的访问顺序。

后序遍历的非递归算法见本节综合题3的解析部分。

按后序非递归算法遍历图5.7(a)中的二叉树，当访问到E时，A,B,D都已入过栈，对于后序非递归遍历，当一个结点的左右子树都被访问后才会出栈，图中D已出栈，此时栈内还有A和B,这是E的全部祖先。实际上，访问一个结点p时，栈中结点恰好是p结点的所有祖先，从栈底到栈顶结点再加上p结点，刚好构成从根结点到p结点的一条路径。在很多算法设计中都可以利用这一思路来求解，如求根到某结点的路径、求两个结点的最近公共祖先等。

层次遍历

图5.8所示为二叉树的层次遍历，即按照箭头所指方向，按照1,2,3,4的层次顺序，对二叉树中的各个结点进行访问。

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队;若它有右子树，则将右子树根结点入队。然后出队，访问出队结点$\cdots$如此反复，直至队列为空。

二叉树的层次遍历算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
void Levelorder(BiTree T){
  InitQueue (Q);//初始化辅助队列
  BiTree p;
  EnQueue (Q, T);//将根结点入队
  while(!IsEmpty (Q)){//队列不空则循环
    DeQueue(o,p);//队头结点出队
    visit (p);//访问出队结点
    if(p->lchild!-NULL)
      EnQueue(o,p->lchild);//左子树不空,则左子树根结点入队if(p->rchild!-NULL)
    if(p->rchild!-NULL)
      EnQueue(Q,p->rchild);//右子树不空，则右子树根结点入队
  }
}

上述二叉树层次遍历的算法，读者在复习过程中应将其作为一个模板，在熟练掌握其执行过程的基础上来记忆，并达到熟练手写的程度。这样才能将层次遍历模板应用于各种题目之中。

注意:遍历是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作，例如，对于一棵已知树求结点的双亲、求结点的孩子结点、求二叉树的深度、求二叉树的叶子结点个数、判断两棵二叉树是否相同等。所有这些操作都建立在二叉树遍历的基础上，因此必须掌握二叉树的各种遍历过程，并能灵活运用以解决各种问题。

由遍历序列构造二叉树

由二叉树的$\color{green}{\text{先序序列}}$和$\color{green}{\text{中序序列}}$可以$\color{red}{\text{唯一地}}$确定一棵二叉树。

在先序遍历序列中，第一个结点一定是二叉树的根结点;而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树。

同理，由二叉树的$\color{green}{\text{后序序列}}$和$\color{green}{\text{中序序列}}$也可以唯一地确定一棵二叉树。

因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。

由二叉树的$\color{green}{\text{层序序列}}$和$\color{green}{\text{中序序列}}$也可以$\color{red}{\text{唯一地}}$确定一棵二叉树，实现方法留给读者思考。需要注意的是，若只知道二叉树的先序序列和后序序列，则无法唯一确定一棵二叉树。

例如，求先序序列（ABCDEFGHI）和中序序列(BCAEDGHFI)所确定的二叉树。

首先，由先序序列可知A为二叉树的根结点。中序序列中A之前的BC为左子树的中序序列，EDGHFI为右子树的中序序列。然后由先序序列可知B是左子树的根结点,D是右子树的根结点。以此类推，就能将剩下的结点继续分解下去，最后得到的二叉树如图5.9(c)所示。

线索二叉树

  • 应用：利用二叉链表中的空指针域，方便求前驱和后继
  • 线索化（左前右后）
    • 若无左子树，则将左指针指向其前驱节点
    • 若无右子树，则将右指针指向其后继节点
  • 优劣
    • 一般常用的是中序线索二叉树
    • 先序线索二叉树寻找前驱结点的过程是非常繁琐的
    • 后序线索二叉树寻找前驱和后继节点的过程都是非常繁琐的
  • 中序线索二叉树（下面的性质感觉都是L，N，R的应用）
    • 视频中的前驱和后继节点的求法感觉很绕
    • 前驱节点
      • 若左指针为线索，则其指向节点为前驱节点
      • 若左指针为左孩子，则其左子树的最右侧节点为前驱节点
    • 后驱节点
      • 若右指针为线索，则其指向节点为后驱节点
      • 若右指针为右孩子，则其右子树的最左侧节点为后驱节点
线索二叉树的基本概念

人工算线索二叉树最快的方法直接求出来$\color{red}{\text{*序遍历的序列}}$

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含$n$个结点的二叉树中，有$n +1$个空指针。这是因为每个叶结点有$2$个空指针，每个度为$1$的结点有$1$个空指针，空指针总数为$2n_0+n_1$，又$n_0=n_2+1$，所以空指针总数为$n_0 + n_1 + n_2 +1 =n+1$。由此设想能否利用这些空指针来存放指向其前驱或后继的指针﹖这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

规定:若无左子树，令lchild指向其前驱结点;若无右子树，令rchild指向其后继结点。如图5.10所示，还需增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继)。($\color{red}{\text{口诀}}$：左前右后,0孩子1标记)

中序线索二叉树的构造

  • 思路：首先要遍历整颗二叉树，找到对应的空指针位，让他们指向正确的位置

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。

以中序线索二叉树的建立为例。附设指针pre 指向刚刚访问过的结点，指针p 指向正在访问的结点，即 pre指向 p 的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre;检查pre 的右指针是否为空，若为空就将它指向p，如图5.11所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 中序遍历对二叉树线索化的递归算法
void InThread(ThreadTree &p, ThreadTree &pre)i
  if(p !=NULL){
    InThread(p->lchild,pre);//递归,线索化左子树
    if(p->lchild==NULL){
      p->lchild=pre; //左子树为空,建立前驱线索
      p->ltag=1;  
    }
    if(pre!=NULL& &pre->rchild==NULL){
      pre->rchild=p;//建立前驱结点的后继线索
      pre->rtag=1;
    }
    pre=p;//标记当前结点成为刚刚访问过的结点
    InThread(p->rchild,pre); //递归,线索化右子树
  }//if(p !-NULL)
}

1
2
3
4
5
6
7
8
9
10
11
// 中序遍历的主过程
void createInThread ( ThreadTree T){
  ThreadTree pre = NULL;
  if(T!=NULL){//非空二叉树,线索化
    InThread(T,pre) ;// 线索化二叉树
    pre->rchild=NULL;//处理遍历的最后一个结点
    pre->rtag=1 ;
  }
}


为了方便，可以在二叉树的线索链表上也添加一个头结点，令其 lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点;令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点。这好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历，如图5.12所示。

下面的性质感觉都是L，N，R的应用

如何找中序遍历序列的第一个结点

一直往左走，最后一个节点就是中序遍历的第一个结点

如何找中序遍历序列的最后一个结点

一直往右走

找后继结点

如果右指针是线索那么右指针所指向的结点就是后继结点；
如果不是线索，那么往右走一步，再往左走

找前驱结点

如果有前驱结点，且左指针是线索，那么左指针指向的结点就是前驱结点；
如果不是线索，那么往左走一步，再一直往右走

中序线索二叉树的遍历

中序线索二叉树的结点中隐含了线索二叉树的前驱和后继信息。在对其进行遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继，直至其后继为空。在中序线索二叉树中找结点后继的规律是:若其右标志为“1”，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。不含头结点的线索二叉树的遍历算法如下。

1）求中序线索二叉树中中序序列下的第一个结点:

1
2
3
ThreadNode *Firstnode (ThreadNode *p){
while(p->ltag==0) p=p->lchild;//最左下结点(不一定是叶结点)return p;
}

2）求中序线索二叉树中结点p在中序序列下的后继:

1
2
3
4
ThreadNode *Nextnode(ThreadNode *p){
  if(P->rtag-=0) return Firstnode (p->rchild);
  else return p->rchild; //rtag==1直接返回后继线索
}

请读者自行分析并完成求中序线索二叉树的最后一个结点和结点p前驱的运算。

将程序1中的ltag和lchild换成rtag和rchild,即为求中序线索二叉树的最后一个结点;将程序2中的rtag和rchild换成ltag和 lchild，即为求中序线索二叉树中结点p的前驱。

3)利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历的算法:

1
2
3
4
void Inorder (ThreadNode *T){
  for (ThreadNode *p=Firstnode(T);p!=NULL; p=Nextnode (p))
    visit (p);
}
先序线索二叉树和后序线索二叉树

上面给出了建立中序线索二叉树的代码，建立先序线索二叉树和后序线索二叉树的代码类似，只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。

以图5.13(a)的二叉树为例给出手动求先序线索二叉树的过程:先序序列为ABCDF，然后依次判断每个结点的左右链域，如果为空则将其改造为线索。结点4.B均有左右孩丁将右链域指左孩子，将左链域指向前驱B，无右孩子，将右链域指向后继D;结点D无左孩子，将左链域指
向前驱C，无右孩子，将右链域指向后继F;结点F无左孩子，将左链域指问前的驱D，后序序列也无后继故置空，得到的先序线索二叉树如图5.13(b)所示。求后序线索二叉树的过程:后序序列为CD BFA，结点C无左孩子，也无前驱故置空，无右孩子，将右链域指向后继D;结点D无左孩子，将左链域指向前驱C，无右孩子，将右链域指向后继B;结点F无左孩子，将左链域指向前驱B，无右孩子，将右链域指向后继A，得到的后序线索二叉树如图5.13(c)所示。

如何在先序线索二叉树中找结点的后继?如果有左孩子，则左孩子就是其后继;如果无左孩子但有右孩子，则右孩子就是其后继;如果为叶结点，则右链域直接指示了结点的后继。

在后序线索二叉树中找结点的后继较为复杂，可分3种情况:①若结点x是二叉树的根，则其后继为空;②若结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有石于树，则具后继即为双亲;③若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的石丁树上孩后序遍历列出的第一个结点。图5.13(c)中找结点B的后继无法通过链域找到，可见在后序线索二叉树上找后继时需知道结点双亲，即需采用带标志域的三叉链表作为存储结构。

树、森林

树的存储结构

双亲表示法

这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。如图5.14所示，根结点下标为0，其伪指针域为-1。

  • 伪指针域为-1
  • 区别树的顺序存储结构与二叉树的顺序存储结构
    • 在树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系。而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。当然，二叉树属于树，因此二叉树都可以用树的存储结构来存储，但树却不都能用二叉树的存储结构来存储。

双亲表示法的存储结构描述如下:

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

孩子表示法

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时$n$个结点就有$n$个孩子链表（叶子结点的孩子链表为空表)，如图5.15(a)所示。

这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历$n$个结点中孩子链表指针域所指向的$n$个孩子链表。

孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容:$\color{green}{\text{结点值}}$、$\color{green}{\text{指向结点第一个孩子结点的指针}}$，及指向结点$\color{green}{\text{下一个兄弟结点的指针}}$（沿此域可以找到结点的所有兄弟结点)，如图5.15(b)所示。

孩子兄弟表示法的存储结构描述如下:

1
2
3
4
5
typedef struct CSNode{
ElemType data;//数据域
struct CSNode *firstchi1d, *nextsibling;//第一个孩子和右兄弟指针
}CSNode, *CSTree;

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，$\color{green}{\text{易于查找结点的孩子等}}$,但缺点是从当前结点查找其$\color{green}{\text{双亲结点比较麻烦}}$。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。

树，森林与二叉树的转换

树和二叉树
  • [树]转换为[二叉树]规则：左孩子右兄弟
    • ①在兄弟结点之间加一连线
    • ②对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉
    • ③以树根为轴心，顺时针旋转45°。
森林和二叉树
  • [森林]转换成[二叉树]的画法
    • ①将森林中的每棵树转换成相应的二叉树
    • ②每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线
    • ③以第一棵树的根为轴心顺时针旋转45°。

树和森林的遍历

树的遍历

图5.16

用某种方式访问树中的每个结点，且仅访问一次

先根遍历
  • 若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。
  • 其遍历序列与这棵树相应二叉树的先序序列相同。
    • 方法：先转换为二叉树，再进行先序遍历
后根遍历
  • 若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。
  • 其遍历序列与这棵树相应二叉树的中序序列相同。
    • 方法：先转换为二叉树，再进行中序遍历

图5.16的树的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA。

森林的遍历

图5.17

图5.17的森林的先序遍历序列为ABCDEFGHI，中序遍历序列为BCDAFEHIG。

先序遍历森林
  • 若森林为非空
  • 访问森林中第一棵树的根结点。
  • 先序遍历第一棵树中根结点的子树森林。
  • 先序遍历除去第一棵树之后剩余的树构成的森林。
中序遍历森林
  • 森林为非空
  • 中序遍历森林中第一棵树的根结点的子树森林
  • 访问第一棵树的根结点
  • 中序遍历除去第一棵树之后剩余的树构成的森林

树的应用————并查集

并查集是一种简单的集合表示，它支持以下3种操作:

1 ) Union(S,Root1,Root2):把集合s 中的子集合Root2并入子集合Root1。要求Root1和 Root2互不相交，否则不执行合并。

2) Find(S,x):查找集合s中单元素x所在的子集合，并返回该子集合的名字。

3 ) Initial(S):将集合s 中的每个元素都初始化为只有一个单元素的子集合。

通常用$\color{red}{\text{树（森林）的双亲}}$表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。

例如,若设有一个全集合为S= {0,1,2,3,4,5,6,7,8,9}，初始化时每个元素自成一个单元素子集合，每个子集合的数组值为-1，如图5.18所示。

经过一段时间的计算，这些子集合合并为3个更大的子集合S= {0,6,7,8}，S={1,4,9}，S,={2,3，5},此时并查集的树形表示和存储结构如图5.19所示。

为了得到两个子集合的并，只需将其中一个子集合根结点的双亲指针指向另一个集合的根结点。因此，S1US2可以具有如图5.20所示的表示。

在采用树的双亲指针数组表示作为并查集的存储表示时，集合元素的编号从0到size-1。其中size是最大元素的个数。下面是并查集主要运算的实现。

并查集的结构定义如下:

1
2
#define SIZE 100
int UFSets [SIZE];//集合元素数组（双亲指针数组)

并查集的初始化操作（s即为并查集):

1
2
3
4
void Initial(int S[]){
  for (int i-0;i<size;i++)//每个自成单元素集合
  S[i]--1;
}

Find操作（函数在并查集s中查找并返回包含元素x的树的根)（$\color{red}{\text{解释}}$：根据初始化，根节点的下标对应的数值值为$\color{red}{\text{-1}}$）:

1
2
3
4
5
6
int Find(int S[],int ×){
while (S[×]>=0)//循环寻找x的根
  x=S[x];
return x;//根的s[]小于0
}

Union操作(函数求两个不相交子集合的并集):

1
2
3
void Union (int S[],int Root1,int Root2){//要求Root1与Root2是不同的,且表示子集合的名字
S[Ro0t2]  = Rootl;//将根Root2连接到另一根Root1下面
}

树与二叉树的应用

二叉排序树(BST,Binary Sort Tree)

  • 性质
    • 动态树表。结构不是一次性生成，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。
定义
  1. 空树
    1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
    2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
    3. 左、右子树也分别是一棵二叉排序树。
二叉排序树的查找
非递归实现
1
2
3
4
5
6
7
8
BSTNode *BSTSearch (BiTree T, ElemType key){
  while(T!=NULL&&key!=T->data){//若树空或等于根结点值，则结束循环
  if(key<T->data) T=T->lchild;//小于,则在左子树上查找
  else T=T->rchild;
  //大于,则在右子树上查找
  }
  return T;
}
递归实现
  • 实现简单但是效率比较低

TODO

二叉排序树的插入
  • 插入的结点一定是一个叶子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int BSTInsert (BiTree &T, KeyType k){
  if(T==NULL){//原树为空,新插入的记录为根结点
    T=(BiTree)malloc(sizeof(BSTNode));
    T->key=k;
    T->lchild=T->rchild=NULL;
    return 1;//返回1,插入成功
  }
  else if (k==T->key) //树中存在相同关键字的结点,插入失败
    return 0;
  else if(k<T->key)//插入到T的左子树
    return BST_Insert(T->lchild,k);
  else//插入到T的右子树
  return BSTInsert(T->rchild, k);
}
二叉排序树的构造
1
2
3
4
5
6
7
8
9
void Creat_ BST (BiTree &T, KeyType str[],int n) {
  T=NULL;
  //初始时T为空树
  int i=0 ;
  while (1<n){//依次将每个关键字插入到二叉排序树中
    BST_Insert(T, str[i]);
    i++;
  }
}
二叉排序树的删除

三种情况
①若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
②若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
③若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱)，这样就转换成了第一或第二种情况。

二叉排序树的查找效率分析
  • 若是平衡二叉树，它的平均查找长度为$O(log_2n)$
  • 若是单支树，平均查找长度为$O(n)$
  • 二叉排序树与二分查找
    • 从查找过程看，二叉排序树与二分查找相似。就平均时间性能而言，二叉排序树上的查找和二分查找差不多。但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树。
      • $\blacktriangleright$ 判定树是什么？
    • 就维护表的有序性而言，二叉排序树无须移动结点,只需修改指针即可完成插入和删除操作，平均执行时间为$O(log_2n)$。二分查找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是$O(n)$。当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作;若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

平衡二叉树(AVL,Adelson-Velsky and Landis Tree)

平衡二叉树和AVL树的区别

百度出来的一堆答案的都是错的。。「每次插入新节点之后需要旋转的次数不能预知」明明可以实现只需要一次旋转

平衡二叉树可以后序遍历查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Judge_AVL(BiTree bt, int &balance, int &h) {
  int bl = 0, br = 0,hl = 0, hr = 0 ;
  if (bt ==NULL){
    h = 0;
    balance = 1;
  }
  else if (bt->lchild==NULL&&bt->rchild==NULL){
    h = 1;
    balance =1;
  }
  else{
    Judge_AVL (bt->lchild,bl, hl) ;Judge_AVL (bt->rchild, br, hr) ;if(hl > hr)
    h = hl+1;else
    h = hr+1;
    if(abs (hl-hr) <2&&bl==1&&br==1)
      balance=1;
    else
      balance=0 ;
  }
}


严书pr.235

因此,当平衡的二叉排序树因插人结点而失去平衡时,仅需对最小不平衡子树进行平衡旋转处理即可。因为经过旋转处理之后的子树深度和插人之前相同,因而不影响插入路径上所有祖先结点的平衡度。

严书代码pp.236(看代码会递归的检查调整每一层)

Q:会有出现多次旋转的情况吗(即：会出现插入路径上的祖先节点也需要更新吗)
A：不需要。只会调整一次，后面退出递归其实都在更新每一个节点树的高度

平衡二叉树的定义(Balanced Binary Tree)
  • 平衡二叉树:在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1
  • 平衡因子:结点左子树与右子树的高度差，
平衡二叉树的插入

每次调整的对象都是最小不平衡子树
假设关键字序列为{15,3,7，10,9,8}（$\blacktriangleright$ 不是很能理解？ ）

  • 其实这个操作本质上就是矩阵转置和恒等变形(弹幕)
LL平衡旋转(右单旋转)

由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
如图5.28所示，结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。

RR平衡旋转（左单旋转）

由于在结点A的右孩子(R）的右子树(R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树，如图5.29所示。

LR平衡旋转（先左后右双旋转）

由于在A的左孩子(L)的右子树(R)上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置，如图5.30所示。

  • 个人理解：先旋B（往左旋）再选A

RL平衡旋转（先右后左双旋转）

由于在A的右孩子(R)的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置，如图5.31所示。

平衡二叉树的查找

平均查找长度为$log_2n$

哈夫曼树和哈夫曼编码

  • 哈夫曼树的性质
    1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
    2. 构造过程中共新建了n-1个结点（双分支结点)，因此哈夫曼树的结点总数为2n一1。
    3. 每次构造都选择⒉棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。
哈夫曼树的定义
  • $\color{red}{\text{带权路径长度}}$:从树的根到任意结点的路径长度(经过的边数)与该节点上权值的乘积。
    • $w_i$是第i个叶节点的权值，$l_i$是该叶结点到根结点的路径长度
    • 记为$WPL=\sum_{i=1}^{n}w_il_i$
  • 哈夫曼树：在含有n个带权叶结点的二叉树中，其中带权路径长度最小的二叉树
哈夫曼树的构造

给定n个权值分别为$w1,w,\cdots,w_n$的结点，构造哈夫曼树的算法描述如下:

将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且.将新结点的权值置为左、右子树上根结点的权值之和。
从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
重复步骤2）和3)，直至F中只剩下一棵树为止。
哈夫曼编码
  • 固定长度编码：每个字符用相等长度的二进制位表示
  • 可变长度编码:允许对不同字符用不等长的二进制位表示
  • 前缀编码:没有一个编码是另一个编码的前缀
  • 利用哈夫曼树可以设计出总长度最最短的二进制前缀编码

习题

武功门派

有一些古老悠久的历史门派，经久不衰，在任何战争中都能发挥非常大的作用

枚举法
特殊值法

题目种类归纳（不限于本章）

性质题
  • p148 t24：性质题
    • 基本上所有的题目都可以是LNR的运用
概念题
  • p148 t25：概念题
纯知识点运用题
  • p148 t25：知识点运用题（单纯求先序，中序，后序）
  • p148 t28：定义运用(就算不知道很详尽的知识点，通过定义，也能够求解)
  • 公式运用
综合运用题（题目给的条件犹抱琵琶半遮面）
  • p148 t14-16：综合运用题（题目给的条件犹抱琵琶半遮面）

做题方法的评价指标

时间复杂度（越快做出来越好）
准确率(Accuracy)（这个方法的准确率越高越好）
  • 影响准确率的因素
    • 计算(Timu Accuracy 1：TA1)
    • 因素考虑完全（枚举）（TA2）
    • 步骤太多（TA3）
    • 题目看错（TA4）
      • 计算题
    • 答案看错(TA5)
      • 概念描述题
几乎没有空间复杂度（草稿纸无限，墨水无限）
  • 使用草稿纸的面积大小（步骤多）会影响准确率，嵌套多，难以维护