数据结构第五章(汇总)

5 树和二叉树

​ 树形结构与线性结构的不同就是，线性结构的前驱和后继是一对一的，树状结构属于非线性结构，有多个后继。前驱与后继是一对n的

5.1 树和二叉树的定义

5.1.1 树的定义

• 树是个n个结点的有限集：
  • 若n=0，称为空树；
  • 若n>0，则他满足如下两个条件：
    1. 有且仅有一个特定的称为根的结点
    2. 其余结点可分为吗（m>=0）个互不相交的有限集T1,T2,T3。。
  • 

5.1.2 树的基本术语

• 根结点：非空树中无前驱结点的结点。
• 结点的度：结点拥有的子树数。
• 树的度：树内各结点的度的最大值。
• 结点的子树的根称为该结点的孩子，该结点称为该孩子的双亲，还有结点的祖先，结点的子孙就不展开描述了。
• 有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。
• 无序树：树中结点的各子树无次序。
• 森林：是m棵互不相交的树的集合
  • 把根结点删除树就变成了森林
  • 一棵树可以看成是一个特殊的森林，树一定是森林，森林不一定是树
  • 给森林中各子树加上一个双亲节点，森林就变成了树

5.1.3 二叉树的定义

二叉树的结构最简单，规律性最强，可以证明所有树都能转化为唯一对应的二叉树，不失一般性。

• 二叉树：是n个结点的有限集，他或者是空集或者是由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成

  • 特点：每个节点最多两个孩子

  • 子树有左右之分(即使只有一棵子树也进行区分)，次序不能颠倒

  • 二叉树可以是空集合，根可以有空的左子树或空的右子树。

  • 具有三个结点的树可能有几种形态？

    

5.2 案例引入

5.2.1 数据压缩问题

将数据文件转换成由0、1组成的二进制串，称之为编码

具体的方法到哈夫曼树和哈弗曼编码那里学习，这里暂且按下不表

5.2.2 利用二叉树求解表达式的值

• 以二叉树表示表达式的递归定义如下：
  1. 若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；
  2. 若表达式为 “ 第一操作数 运算符 第二操作数” 的形式， 则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点存放运算符，其中错作数本身又为表达式。

具体实现，我们会在[5.8 案例分析与实现](####5.8 案例分析与实现)进行讲解

5.3 树和二叉树的抽象数据类型定义

5.4 二叉树的性质和存储结构

1. 在二叉树的第i层上之多有$\large 2^{i-1}$个结点

2. 深度为k的二叉树至多有$\large 2^k-1$个结点

3. 对任何一棵二叉树T，如果其叶子树为$\large n_0$,度为2的结点数为$\large n_2$，则$\large n_0=n_2+1$

   • 总边数$\large B=n-1 = B=n_22+n_11$
   • 总结点数为$\large n=n_22+n_11+1$ 又 $n=n_2+n_1+n_0$
   • 推导出$\large n_0=n_2+1$

4. 具有n个结点的完全二叉树的深度为[log_2n]（向下取整）+1

   性质4表明了完全二叉树结点数n与完全二叉树深度k之间的关系

5. 如果对一棵有 n个结点的完全二叉树，其结点按层序编号（从第 1 层到第[log2n]+ 1 层， 每层从左到右）， 则对任一结点(n=>i>=1), 有如果i=1，无双亲，如果i>1.则其双亲是结点[$\large i/2$]。

   1. 性质5表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系

• 两种特殊形式的二叉树
  • 满二叉树：一颗深度为k且有$\large 2^k-1$个结点的二叉树称为满二叉树
  • 特点：
    • 每一层上的结点数
    • 编号从上到下，从左到右
  • 完全二叉树：深度为K的， 有n个结点的二叉树， 当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时， 称之为完全二叉树。
    • 在满二叉树中，从最后一个结点开始，连续去掉任意个结点，都是一棵完全二叉树
    • 叶子只能分布在最大的两层上
    • 对任意一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i-1

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

5.5.1 遍历二叉树

• 遍历的定义——顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次

  • “访问”可以看做对结点作各种处理

• 遍历的目的——得到树中所有结点的一个线性排列

• 遍历的用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心

• 遍历的算法

  • DLR——先（根）序遍历

  • LDR——中（根）序遍历 【从最左边 开始左根右】，可以吧空序都先画出来，然后再开始遍历

  • LRD——后（根）序遍历

    

  • 例题——已知中序序列和后续序列求二叉树

  • 

  • 前后确定根，中序辨左右 重点

• 二叉树先序遍历算法

  Status PreOrderTiraverse（BiTree T）{
      if(T==NULL)return OK;
      else{
          visit(T);								//访问根结点
          PreOrderTiraverse(T->lchild);			//递归遍历左子树，递归调用
          PreOrderTiraverse(T->rchild);			//递归遍历右子树
      }
  }

  • 

    其中涉及到了递归调用的逐层返回

    

如果去掉输出语句，从递归的角度看，三种三发事完全相同的，只是访问的十几不同

时间复杂度是3n，其中3是常数可以去掉，所以O(n)

5.5.1.1 遍历二叉树的非递归算法

• 二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树

• 基本思想

  1. 建立一个栈

  2. 根结点进栈，遍历左子树

  3. 根结点出栈，输出根结点，遍历右子树

  4. Status InOrderTraverse(BiTree T){
         BiTree p;InitStack(S);P=T;
         while(p||!StackEmpty(S)){		//StackEmpty（S），S空返回true,非空返回false
             if(p){Push (S,p); p=p->lchild;}//push（S，p）是把p值入栈S
             else {Pop(S,q); printf("%c", q->data);//pop（S，q）是出栈值给q
                  p=q->rchild;}
         }//while
     }
          ***走到D时，左右子树都为空返回时，q会指向A应为栈内一开始就存放了A，然后再访问A的右子树***
     
     ##### 5.5.1.2 二叉树的层次遍历
     
     - 队列类型定义
     
       ```c
       typedef struct{
           BTNode data[MaxSize];
           int front,rear;
       }SqQueue;
     
     

  二叉树层次遍历算法：

  void LevelOrder(BTNode*b){
      BTNode *p;   SqQueue *qu;
      InitQueue(qu);//初始化队列
      enQueue(qu, b);//根结点指针进入队列
      while(!QueueEmpty（qu)）{
          deQueue(qu,p);//出队结点p
          printf("%c",p->data);//访问结点p
          if(p->lchild!=NULL)enQueue(qu,p->lchild);//有左孩子时将其进队
          if(p->rchild!=NULL)enQueue(qu,p->rchild);//有右孩子时将其进队
      }
  }

5.5.1.3 遍历算法的应用——二叉树的建立

• 算法描述：

Statys CreatBiTree(BiTree &T){
    scanf(&ch);
    if(ch=="#")T=NULL;
    else{
        if(!(BiTNode*)malloc(sizeof(BiTNode)))	//分配一块儿结点空间
            exit(OVERFLOW);	
        T->data=ch;								//生成根结点
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

5.5.1.4 复制二叉树

int Copy(BiTree T,BiTree &NewT){
    if(T==NULL){
        NewT==NULL;return 0;
    }
    else{
        NewT=new BiTNode;
        NewT->data=T->data;
        copy(T->lchild, NewT->lchild);
        copy(T->rchild, NewT->rchild);
    }
}

5.5.1.5 计算二叉树的深度

• 如果是空树，则深度为0

​ 否则，递归计算左子树深度记为m，右子树深度为n，二叉树深度则为n和m的较大者加1

int Depth(BiTree T){
    if(T==NULL) return 0;
    else {
        m=Depth {T->lchild); 
		n=Depth {T->rchild);
		if{m>n) return{m+l);
        else return(n+l);
    }
}

5.5.1.6 计算二叉树的结点总数

• 如果是空树，则结点个数为0

​ 否则，结点个数为左子树的结点个数+右子树的结点个数再加1

int NodeCount(BiTree T){
    if (T==NULL) 
        return O;
    else
        return NodeCount (T->lchild) +Node Count (T->rchild) + 1;
}

5.5.1.7 计算二叉树叶子结点数

int leafcount(BiTree T){
    if(T=NULL)
        return 0:
    if(T->lchild==NULL&&T->rchild==NULL)
        return 1;
    else
        return LeafCount(T->lchild)+LeafCount(T->rchild;)
}

5.5.2 线索二叉树

• 利用二叉链表中的空指针域：

  如果某个节点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果右孩子为空，则其指针域改为指向其后继————将改变指向的指针称为**“线索”，加上了线索的二叉树称为线索二叉树**

  

• 为了区分是指向孩子的指针还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域ltag和rtag，这样结点的结构就为【lchild | ltag | data | rtag | rchild 】并约定：

  • ltag=0/rtag=0 指针指向孩子

  • ltag=1/rtag=1 指针指向前驱/后继

    

5.6 树和森林

本节将讨论树的表示及其遍历操作，并建立森林与二叉树的对应关系。

5.6.1 树的存储结构

5,6,6,1 双亲表示法

实现：定义结构数组存放树的结点，每个结点含两个域；

• 数据域：存放结点本身信息

• 双亲域：指示本结点的双亲结点在数组中的位置
  

• C语言的类型描述：

  typedef struct PTNode{
      TElemType data;
      int parent;
  }PTNode;

• 树结构：

  #define MAX_TREE_SIZE 100
  typedef struct{
      PTNode nodes[MAX_TREE_SIZE];
      int r,n;//根结点的位置和结点个数
  }

5.6.1.2 孩子链表

• 把每个结点的孩子结点排列起来。看成一个线性表，用单链表存储

  

• C语言描述：

  typedef struct CTNode{
      int child;
      struct CTNode *next;
  }*Childptr;

• 树结构

  typedef struct{
      CTBox nodes[MAX_TREE_SIZE];
      int n,r;
  }CTree;

5.6.1.3 孩子兄弟表示法

• C语言描述

  typedef struct CSNode{
      ElemType data;
      struct CSNode *firstchild,*nextsibling;
  }CSNode,*CSTree;

  

5.6.2 树与二叉树的转换

• 将树转换为二叉树进行处理，利用二叉树的算法来实现对树的操作。

• 由于树和二叉树都可以用二叉链表做存储结构，则以二叉链表做媒介可以导出树与二叉树之间的一个对应关系。

• 给定一棵树可以找到唯一的一颗二叉树与之对应

  • 加线：在兄弟之间加一条线，

  • 抹线：对每个结点，除了其左孩子外，去除其余孩子之间的关系

  • 旋转：以树根结点为轴心，将整树顺时针旋转45°

    树变二叉树：兄弟相连留长子。其中根结点的油茶树一定为空

• 反之可以把二叉树转换成树

  • 加线：若p结点是双亲节点的左孩子，则将p的右孩子，右孩子的右孩子……沿分支找到所有右孩子，都与p的双亲用线连起来

  • 抹线：抹掉原二叉树中双亲与右孩子之间的连线

  • 调整：将结点按层次排列，形成树结构。

    二叉树变树：左孩右右连双亲，去掉原来右孩线

5.6.3 森林与二叉树的转换

• 森林转换成二叉树（二叉树与多棵树之间的关系）

  • 将个棵树分别转换成二叉树

  • 将每棵树的根结点用线相连

  • 以第一课树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

    森林变二叉树：树变二叉根相连

• 二叉树转换成森林

  • 抹线：将二叉树中根结点与其右孩子连线，及沿有分支搜索到的所有右孩子之间的连线抹掉，使之变成孤立的二叉树

  • 还原：将孤立的二叉树还原成树

    二叉树变森林：去掉全部右孩线，孤立二叉再还原

5.6.4 树和森林的遍历

5.6.4.1树的遍历

• 先根遍历：若树不为空，则先访问根结点，然后一次先根遍历各棵子树。
• 后根遍历：若树不为空，则先依次后根遍历各棵子树，然后访问根结点。
• 层次遍历：若树不为空，则自上而下自左至右访问树种每个结点。

5.6.4.2 森林的遍历

• 将森林看作由三部分构成：

  1. 森林中第一棵树的根结点；
  2. 森林中第一棵树的子树森林；
  3. 森林中其他树构成的森林。

• 先序遍历：若森林不为空，则依次从左至右对森林中的每一棵树进行先根遍历

• 中序遍历：若森林不为空，则

  1. 中序遍历森林中第一棵树的子树森林；

  2. 访问森林中第一棵树的根结点；

  3. 中序遍历森林中（除第一棵树之外）其余树构成的森林。

     即：依次从左至右对森林中每一个棵树进行后根遍历

5.7哈夫曼树的基本概念

5.7.1 哈夫曼树的基本概念

效率最高的判别树，就是哈夫曼树（也称最优二叉树）

• 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

• 结点的路径长度：两结点间路径上的分支数。

• 树的路径长度：从树根到没一个结点的路径长度之和。记作：TL

  • 结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，但路径长度最短的不一定是完全二叉树

• 权(weight)：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

• 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

• 树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：$\large WPL=\sum\limits_{k=1}^nw_kl_K$(weighted path length)

• 哈夫曼树：最优树/最优二叉树（带权路径长度最短的树）

  • 因为构造这种树的算法是由哈夫曼教授于1952年提出的，所以被称为哈夫曼树，相应的算法称为哈夫曼算法
  • 满二叉树不一定是哈夫曼树
  • 哈夫曼树中全越大的叶子离根越近
  • 具有相同带权结点的哈夫曼树不唯一

• 贪心算法：构造哈夫曼树时首先选择权值小的叶子结点

5.7.2 哈夫曼树的构造算法

• 构造过程

  1. 根据给定的n个权值{$w_1.w_2.w_3,……,w_n$}，构造n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。

  2. 在森林 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左 、右子树上根结点的权值之和

  3. 在森林F中删除这两棵树，同时将新得到的二叉树加入森林中。

  4. 重复2和3的步骤，直到森林中只有一棵树为止，这棵树即为哈夫曼树。

• 口诀

  1. 构造森林全是根
  2. 选用两小造新树
  3. 删除两小添新人
  4. 重复二三剩单根

  

  

• 总结

  1. 在哈夫曼树算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树

  2. 经过n_1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支节点

     可见：哈夫曼树中共有n+n-1=2n-1个结点，且其所有的分支结点的度均不为1.

• 哈夫曼树构造算法的实现

• 采用顺序存储结构——一维结构数组 HuffmanTree H;

• 结点类型定义

  typedef struct{
      int weight;
      int parent,lch,rch;
  }HTNode,*HuffmanTree;

  哈夫曼树中结点下标i	weight	parent	lch	rch
  1
  2
  3
  4
  ……
  2n_1

• 构造哈夫曼树

  void CreateHuffmanTree(HuffmanTree &HT,int n){
      if(n<=l) return;
  	m=2*n-l;//数组一共2n-1个元素
  	HT=new HTNode[m+l);//0号单元未用，HT[m]表示根结点
      for(i=l;i<=m;++i){//将2n-1个元素的lch/rch/parent置为0
          HT[i].parent=O;HT[i].lchild=O;HT[i].rchild=O;
      }
      for(i=l;i<=n;++i}cin>>HT[i] .weight;//输入前n个元素weight的值，初始化结束
      for (i=n+l;i<=m;++i)
          Select (HT,i-1,sl,s2);
          HT[sl] .parent=i;HT[s2] .parent=i;
          HT[i] .lchild=sl;HT [i]. rchild=s2;
          HT[i] .weight=HT[sl] .weight+HT[s2] .weight;
  }

• 例题：

  巳知 w = (5,29,7,8,14,23,3,11), 利用算法 5.10 试构造一棵哈夫曼树， 计算树的带权路径长度， 并给出其构造过程中存储结构HT的初始状态和终结状态。

  哈夫曼树中结点下标i	weight	parent	lch	rch
  1	5	9	0	0
  2	29	14	0	0
  3	7	10	0	0
  4	8	10	0	0
  5	14	12	0	0
  6	23	13	0	0
  7	3	9	0	0
  8	11	11	0	0
  9	8	11	1	7
  10	15	12	3	4
  11	19	13	8	9
  12	29	14	5	10
  13	42	15	6	11
  14	58	15	2	12
  15	100	0	13	14

5.7.3 哈夫曼编码

void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
    HC=nuw char*[n+1];										//分配n个字符编码的头指针矢量
    cd=new char[n];											//分配临时存放编码的动态数组空间
    cd[n-1]='\0';											//编码结束符
    for(i=1;i<=n;++i){										//逐个字符求哈夫曼编码
        start=n-1;c=i;f=HT[i].parent;
        while(f!=0){										//从叶子结点开始向上回溯，直到根节点
            --start;										//回溯一次start向前指一个位置
            if
                (HT[f].lchild==c)cd[start]='0';				//结点c是f的左孩子，则生成代码0
            else				 cd[start]='1';				//结点c是f的右孩子，则生成代码1
                c=f;f=HT[f].parent;							//继续向上回溯
        }													//求出第i个字符的编码
        HC[i]=new char[n-start];							//为第i个字符串编码分配空间
        strcpy(HC[i],&cd[start]);							//将求得的编码从临时空间cd复制到HC的当前行中
    }
   delete cd;												//释放临时空间
}															//creatHuffmanCode

1. 编码：
   1. 输入各字符及其权值
   2. 构造哈夫曼树——HT[i] n+n-1个
   3. 进行哈夫曼编码——HC[i]
   4. 查HC[i]，得到各字符的哈夫曼编码
2. 解码：
   1. 构造哈夫曼树
   2. 依次读入二进制码
   3. 读入0，则走向左孩子，读入1，则走向右孩子
   4. 一旦到达某叶子时，即可译出字符
   5. 然后再从根出发继续译码，直到结束