Author:JaneOnly300 Date:2021：12.6 Categories: 数据结构(专升本) 本章参考王卓数据结构与算法基础

一、树的定义

树形结构(非线性结构)，结点之间有分支，具有层次关系。
image.png

树的定义

树是有n个结点的有限集合

  • 若n=0为空树
  • 若n>0，则他满足如下的两个条件
    1. 有且仅有一个特定的根结点
    2. 其余的结点可以分为m个不互相叫的有限集，每个集合本身有事一颗树，并且称为根的子树(su Tree)。

image.png
image.png

它是一个递归嵌套的定义.

树的基本术语

  • 根节点(无前驱结点)
  • 结点的度
    • 就是结点拥有的子树个数
  • 树的度
    • 就是所有节点度的最大值
  • 叶子
    • 就是度=0

  • 分支节点

    • 度!=0

    image.png

    有序树.子树有次序和无次序

森林

m(>=0)的互不相交的树的集合,一颗树也可以看成一个特殊森林
image.png

二、二叉树的定义

  • 二叉树的结构性强，规律性强
  • 所有的树都能转换为对应的二叉树，不失去一般性

普通树(多叉树)若不转换为二叉树，那么就会导致运算能难..二叉树的结构性强，规律性强，每个节点**最多**能有2个分支节点或者叶子，所有的树都可以转换为二叉树，这样就能解决很多树的存储结构和运算的存储性

二叉树的特点

  • 每个节点最多能有两个孩子
  • 子树有左右区分，次序不能颠倒
  • 二叉树可以是空集合

注意: 二叉树不是树的特殊情况，他们是两种概念。
二叉树节点的子树一定需要区分左右子树！！
image.png

二叉树的5中形态

image.png

虽然二叉树和树的概念不同，但树的基本术语和二叉树通用

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

重要操作:

  • 前中后序遍历

    image.png

    四、二叉树的性质和存储结构

    1. 性质1

  • 第i层当中最多2^i-1个节点

  • 第i层当中最少有1个结点

image.png

2. 性质二

  • 深度为K的二叉树当中最多有2^k-1个结点

image.png

3. 性质三

image.png

特殊性质的二叉树

二叉树有两种特殊形式，满二叉树和完全二叉树。

满二叉树

定义

  • 一个深度为k的二叉树有2^k-1个结点称之为满二叉树(也就是结点==最大结点)

image.png

特点

  1. 每一层上的结点数，都是最大结点树
  2. 叶子结点全部都在最底层
  3. 二叉树的编号规则
    1. 从根节点开始，层层编号

      在同样深度的二叉树结点个数最多 在同样深度的二叉树叶子结点个数最多

完全二叉树

深度为k的具有n个结点的二叉树，每一个结点与深度为k的满二叉树中编号一一对应的就是完全二叉树。

判断是否为完全二叉树

  • 给二叉树编号，和满二叉树的编号作对比
    • 若完全一样，则是完全二叉树
    • 若有不一样，则不是完全二叉树
  • 方法二

image.png
image.png

特点

  1. 叶子结点只可能分配在层此最大的两层之上
  2. 对于任意的结点，如果右边子树最大层次为i，name左子树的最大层此必须为i或者i+1

    性质1

  • 表明了完全二叉树结点n树与完全二叉树深度K之间的关系

image.png

性质2

  • 求完全二叉树双亲结点和孩子结点编号之间的关系

image.png

五、二叉树的存储结构

1. 二叉树的顺序存储

按照满二叉树的结点层此编号，一次存放二叉树当中的元素

image.png

  • 二叉树的顺序存储表示方式

    1. #define MAXSIZE 100
    2. Typedef TElemType sqlBiTree[MAXSIZE]
    3. SqBiTree bt;

    小练习

  • 将下面用完全二叉树表述出来

image.png

3. 顺序存储的特点

  • 二叉树顺序存储缺点，神队为K的只有k个结点的树，却需要2^k-1的二维数组，造成空间浪费
  • 只能适用于满二叉树和完全二叉树当中
  • 结点关系在存储位置当中

image.png

2. 二叉树的链式存储结构(常用)

每个节点有两个指针，分别指向左孩子和右孩子。
image.png

代码表示

  1. typedef struct BiNode{
  2.     TElemType data;
  3.     struct BiNode *lchild,*rchild;
  4. }BiNode,*BiTree;

image.png
结论:
在n个结点当中，一共有n+1个空指针域

三叉链表(略..)

image.png

六、 二叉树的遍历(核心)

遍历就是通过某一条搜索路径访问二叉树的结点，使得每个结点都被访问一次
为了得到树的线性排列

1. 遍历方法

若是规定先左后右边,则有三种情况

  • DLR:先序遍历
  • LDR:中序遍历

  • LRD:后序遍历

    image.png

    1. 先序遍历

  • 若二叉树为空，则空操作，否则

    • 访问根节点
    • 遍历左子树
    • 遍历右子树

      2. 中序遍历

  • 若二叉树为空，则空操作，否则

    • 中序遍历左子树
    • 访问根节点
    • 中序遍历右子树

      3. 后序遍历

  • 若二叉树为空，则空操作，否则

    • 后序遍历左子树
    • 后序遍历右子树
    • 最后访问根节点

练习1:
image.png

练习2
image.png

2. 遍历算法的实现

递归实现

算法时间复杂度为On

  • 先序遍历递归遍历的实现

    1. void preOrder(Btree *T)
    2. {
    3.   if(T != NULL) {
    4.       printf("%d ", T->element);  //访问根节点
    5.       preOrder(T->lchild);    //先根序遍历左子树
    6.       preOrder(T->rchild);    //先根序遍历右子树
    7.   }
    8. }

  • 中序遍历

    1. void inOrder(Btree *T)
    2. {
    3.   if(T != NULL) {
    4.       inOrder(T->lchild);     //中根序遍历左子树
    5.       printf("%d ", T->element);  //访问根节点 
    6.       inOrder(T->rchild); //中根序遍历右子树
    7.   }
    8. }

  • 后序遍历

    1. void postOrder(Btree *T)
    2. {
    3.   if(T != NULL) {
    4.       postOrder(T->lchild);   //后根序遍历左子树
    5.       postOrder(T->rchild);   //后根序遍历右子树
    6.       printf("%d ", T->element);  //访问根节点
    7.   }
    8. }

    非递归的算法

  • 中序遍历非递归算法

  1. 建立一个栈;
  2. 根结点进栈，遍历左子树，

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

    image.png

    层此遍历算法

  • 根据深度一层一层访问，从上到下，从左到右，每个结点只访问一次
  1. 将根结点入队;
  2. 队不为空循环: 从队列出列一个节点*p,访问它;
    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); printf(“%c”,p->data);//访问数 if(p->Lchild!=null) enQueue(qu,p->LChild); if(p->rChild!=null) enQueue(qu,p->rChild); } }

  2. <a name="jM4J2"></a>
  3. ## 3. 遍历算法的应用
  4. <a name="OkOln"></a>
  5. ### 1. 二叉树的算法建立
  6. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/12423141/1638970159544-576bd131-e61e-4ef6-9b24-7e0d5ab29dc2.png#clientId=ua065e676-5e1c-4&from=paste&height=391&id=u28c42268&margin=%5Bobject%20Object%5D&name=image.png&originHeight=782&originWidth=1002&originalType=binary&ratio=1&size=408454&status=done&style=none&taskId=u8c2f0235-81ae-4ea2-a85f-7abb7f51d08&width=501)
  7. <a name="oGUdB"></a>
  8. ### 2. 二叉树的复制
  9. 算法的实现: （先序遍历）
  11. - 如果是空树，递归结束
  12. - 否则，申请新的结点空间，复制根结点
  13. - 递归复制左子树
  14. - 递归复制右 子树
  15. ```c
  16. int Copy(BiTree T,BiTree &NewT){
  17.      if(T == null ){ //如果是空树，返回
  18.         NewT = NULL ; return 0;
  19.     }else{
  20.          NewT = new BiTNode;
  21.         NewT->data = T->Data;
  22.         //
  23.         Copy(T->LChild,New->Lchild();
  24.         Copy(T->RChild,New->Rchild();
  25.     }
  27. }

计算二叉树的深度

  • 若果是为空树，则深度为0
  • 否则
    • 计算左子树的深度，
    • 计算右子树的深度
    • 求出来后+1
      1. int Depth(BiTree T){
      2. if(T == null) return 0; //空树返回0
      3. else{
      4.  m = Depath(T->lChild); //计算左子树的深度
      5.  n = Depath(T->RChild); //计算右子树的深度
      6.  if(m>n) return (m+1);
      7.  else{
      8.    return (n+1)        
      9.  }
      10. }
      11. }

计算二叉树的节点

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

  • 否则节点的个数加上左子树的结点个数+右子树的结点个数+1

    1. int CountNode(BiTree b){
    2.    if(b == null){
    3.        return 0;   
    4.   }else{ //如果不等于null
    5.          //计算左子树+右边子树的的节点+根节点
    6.       return CountNode(b->Lchild)+CountNode(B->Rchild)+1;
    7.   }
    8. }

    计算二叉树的叶子结点

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

  • 否则，判断
    • 左右都没有孩子(叶子结点)返回1
    • 否则
      • 左子树叶子结点+右子树叶子结点
  1. int LeadCount(BiTree T){
  2.     if(T == null){
  3.         return 0;
  4.     }
  5.     if(T->LChild == null && T->Rchild == null){
  6.         return 1; //找出了一个叶子结点
  7.     }else{
  8.         return LeadCount(T->LChild)+LeadCount(T->Rchild)
  9.     }
  10. }

4. 根据遍历序列确定一个二叉树

若果二叉树的各个节点都不一样，则而二叉树的先序遍历中序遍历和后序遍历都是唯一的
由二叉树的先序和中序，或者由二叉树的后序和中序则可以确定一个唯一的二叉树

例子

先序与中序判断
  • 先序: ABCDEFGHIJ
  • 中序: CDBFEAIHGJ

后序和中序
  • 后序: BDCEAFHG
  • DECBHGFA

5. 线索二叉树

使用二叉链表作为二叉树存储结构时，可以方便找到某个结点左右孩子; 但一般情况， 无法直接找到该结点在某种遍历序列中的前驱和后继结点。

  • 如果寻找特定遍历序列中二叉树结点的前驱和后继？？

    了利用空着的指针域

1. 概念

利用二叉链表的空指针域
如果某个结点的左孩子为空，则将左孩子指针域改为指向前驱，如果右孩子为空，则指向后继。

这种改变指向的指针称之为线索 对于二叉树按照某种遍历次使得其变为线索二叉树的过程叫做线索化

加上了线索的二叉树就是线索二叉树
image.png
为了区分二叉链表的中Lchild和Rchild是指向左右孩子还是前驱后继的，我们来添加tag来加以区分

  1. ltag = 0  //指向左孩子
  2. rtag = 0 // 指向右孩子
  4. ltag = 1; //指向前驱
  5. rtag = 1; //指向后继
  7. //Code
  8. typedef struct BiThrNode{
  9.     int data;
  10.     int ltag,rtag ; //表示符号
  11.     struct BiThrNode *lchild,rchild;
  12. }BiThrNode.*BiThrTree;

image.png

1.1. 关于线索二叉树线索为空的状态?

image.png

2. 线索二叉树练习

练习1

先序序列: A B C D E
image.png
请根据以上的 二叉树，将其按先序、中序、后续、进行线索化;

练习2

image.png

七、树和森林

review 树的定义

1. 树的存储

1. 双亲表示法

  • 定义: 定义结构数组存放树的结点，每个结点含有两个域
  • 数据域: 存放结点本身的信息
  • 双亲域: 指示本结点 的双亲结点在数组当中的位置
  • 数组索引表示位置

image.png

c语言表示

  1. typedf struct PtNode{
  2.     TElemType data;
  3.     int parent ; //双亲位置域
  4. }PTNode;
  5. #define MAX_TREE_SIZE
  6. //树
  7. type struct{
  8.     PTNode nodes[MAX_TREE_SIZE];
  9.     int r,n ; //根节点的位置，和结点个数
  10. }PTree;

找到双亲很容易，找孩子难。

2. 孩子链表

把每个结点的孩子结点排列起来，看成一个线性表，用单链表进行存储,则n个结点就有n个孩子链表，(叶子结点的链表为空)，而n个头指针又组成一个线性表，用顺序表进行存储。
image.png

c语言表示

  1. //孩子结点
  2. typedef struct CTNode{
  3.     int child ; //
  4.     struct CTNode *next;
  5. }*ChildPtr;
  6. //双亲结点
  7. typedef struct{
  8.     TElemType data;//数据
  9.     ChildPtr fistchild; //孩子链表的头结点
  10. }CTBox;
  11. //树
  12. typedef struct{
  13.     CTBox Nodes[MAXSIZE];
  14.     int n,r;//头结点位置和根节点位置
  15. }

找孩子容易，找双亲难

3. 孩子兄弟表示法(二叉链表表示法)

实现: 用儿茶链表作树的存储结构，链表中每一个结点的两个指针域，
分别指向第一个孩子结点和下一个兄弟结点

c语言表示

  1. typedef struct CSNodeP{
  2.     ElemType data;
  3.     struct CSNode *firstChild，*nextsibling;
  4. }CSnode,*CSTree;

image.png

2. 树和二叉树的转换

目的

将树转换为二叉树进行处理，利用二叉树算法实现对树的操作。
二叉树，都是可以使用二叉链表作为存储结构，则二叉链表作为媒介可以导出树与二叉树之间的对应关系。

  • 给定一颗树，我们就能将其转换为二叉树

    image.png

    树转换为二叉树

  1. 加线: 在兄弟之间加一个线
  2. 摸线: 对每个结点，除了左孩子，去除其余孩子的关系
  3. 旋转，以树的根节点为轴心。整个树旋转45°

image.png

兄弟相连接留长子

二叉树转换为树

  • 左孩右右连双亲、
  • 去掉原来右孩线

image.png

3. 森林和二叉树的转换

1. 森林转换成为二叉树

  • 树变二叉，根相连

image.png

2. 二叉树转换为森林

  • 去掉全部右孩子线，孤立二叉再还原

image.png

4. 树和森林的遍历

1. 树的遍历

先根遍历

  • 若树不为空，则先访问根节点，然后依次遍历各个子树

    后根遍历

  • 若树不空，则先依次后根遍历各个子树，然后访问根结点

    按照层次遍历

  • 若树不为空，则自上而下从左到右访问每个结点

练习:

  • 写出下列树的先后根和层次遍历的序列

image.png

2. 森林的遍历

我们可以将森林看做三个部分

  • 第一棵树的根节点
  • 第一棵树的子树森林
  • 其他的树构成的森林

image.png

先序遍历

  • 若森林不为空
  1. 先访问根
  2. 然后访问子树森林

    依次进行先序遍历

中序遍历

  • 若森林不为空
  1. 中序遍历森领当中第一棵树的子森林
  2. 访问森林中第一棵树的根结点
  3. 中序遍历森林中其余树构成森林

image.png

依次从左到右对森林每一个树进行后根遍历