Tree Structures

Tree Structures

五月 29, 2021

树

  1. 树的定义（一对多）

    1. 树的结构定义：有且仅有一个特定的根（root）的结点，其余节点为互不相交的有限集合，即子树，n=0为空树
    2. （结点的）度：结点拥有的子树个数 ； 树的度：树中的==度的最大值==
    3. 结点间的关系：孩子，双亲，兄弟，祖先，子孙
    4. 树的相关概念：层次，高度，深度，堂兄弟，森林，有序/无序树
    5. 树的抽象数据类型：P130

  2. 树的存储结构

    1. 双亲表示法（改：+长子域 == 方便找孩子、+右兄弟域 ==> 方便找兄弟）【根结点无双亲：-1（双亲域）】

      1. 结构：b32a02266416134b39aff7d20707c6ad.png

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        //定义（双亲表示法）结点结构
        typedef struct PTNode
        {
            int data;
            int parent;
        }PTNode;
        //定义树结构
        typedef struct
        {
            PTNode nodes[MAX_TREE_SIZE];	//结点数组
            int r,n;	//r记录根位置，n记录结点数
        }PTree;

    2. 孩子表示法（改：+双亲域 == 双亲孩子表示法）

      1. 结构1：多重链表表示法（结点长度统一，多个指针域指向孩子，空为^）EP8S3KLWZ@_}YJNE0$Z%X6A.png（浪费空间）

      2. 结构2：长度不统一，按需分配，degree记录度数。4[YXP~V05$[E3)VC@C[$2A9.png

      3. （最佳）结构3：顺序线性表（一维数组存储）+单链表（子结点）![3N@@%{4B77`AS15@G{1TZ6S.png](:/f9ac07328a994c99a73c017c6e8ff2d0)

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        //（单链表）孩子结点
        typedef struct CTNode
        {
            int child;
            struct CTNode *next; 
        }*ChildPtr;
        //（一维数组）表头节点
        typedef struct
        {
            int data;
            ChildPtr firstchild;
        }CTBox;
        //树结构
        typedef struct
        {
            CTBox nodes[MAX_SIZE];	//结点数组
            int r,n;
        }CTree;

    3. 孩子兄弟表示法（可以转换为==二叉链表==：右兄弟变左孩子）

      1. 结构：8R39OOU@ODY1NYR$~%L76HL.png

        1
        2
        3
        4
        5
        typedef struct CSNode
        {
            int data;
            struct CSNode *firstchild,*rightsib;
        }CSNode,*CSTree;

  3. 二叉树的定义&特点

    1. 结构定义：根 + 左、右子树
    2. 二叉树三个特点：最多只有两度、区分左右、单结点分左右
    3. 二叉树的五种基本形态：空二叉树、只有根、左斜树、右斜树、左右斜树
    4. 特殊二叉树：斜树【结点个数=深度】、满二叉树【有左有右】、完全二叉树（同结点深度最小）【编号连续的有序结点】

  4. 二叉树的性质

    1. 二叉性质：
      1. 【单层结点数】第i层至多有2i-1个结点（i≥1）
      2. 【总结点数】深度为k至多有2k-1个结点（k≥1）
      3. 任何一棵二叉树T，终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
    2. 完全二叉性质：
      1. n个结点完全二叉树的深度为⌊log⁡2n⌋+1（⌊x⌋：小于x的最大整数）
      2. n个节点的完全二叉树的结点按层序编号，对任一结点i（1≤i≤n）有：
        1. 如果i=1，结点i是二叉树的根，无双亲；i>1，气双亲式结点⌊i/2⌋
        2. 如果2i>n，结点i无左孩子（结点i为叶子结点）；否则左孩子是结点2i
        3. 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

  5. 二叉树存储结构

    1. 顺序存储结构：上至下，左到右

    2. 链式存储结构：二叉链表b0977392113afa533bdc24d733f28f58.png

      1
      2
      3
      4
      5
      6
      //数据域+左右孩子
      typedef struct BiTNode
      {
          int data;
          struct BiTNode *lchild,*rchild;
      }BiTNode,*BiTree;

  6. 二叉树的遍历（从根结点出发，按照不同次序，对每个结点进行访问）

    1. 前序遍历：根、左、右

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      //前序遍历T二叉树
      void PreOrderTraverse(BiTree T)
      {
          if(T==NULL)
          {
              return;
          }
          printf("%c",T->data);
          PreOrderTraverse(T->lchild);
          PreOrderTraverse(T->rchild);
      }

    2. 中序遍历：左、根、右

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      void InOrderTraverse(BiTree T)
      {
          if(T==NULL)
          {
              return;
          }
          InOrderTraverse(T->lchild);
          printf("%c",T->data);
          InOrderTraverse(T->rchild);
      }

    3. 后序遍历：左、右、根

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      PostOrderTraverse(BiTree T)
      {
          if(T==NULL)
          {
              return;
          }
          PostOrderTraverse(T->lchild);
          PostOrderTraverse(T->rchild);
          printf("%c",T->data);
      }

    4. 层序遍历：同层，左到右、上到下

    5. 推导确定一颗二叉树：

      1. 能确定：前序 + 中序、中序 + 后序
      2. 不能确定：前序 + 后序

  7. 扩展二叉树的建立【经处理后的二叉树：虚结点“#”表示空NULL】

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //前序遍历建立一个扩展二叉树
    void CreatBiTree(BiTree T)
    {
        char ch;
        scanf("%c",&ch);	//输入要生成的二叉树结点，输入#作为结点
        if(ch=='#')
        {
            *T=NULL;	//遇到#，作为空节点
        }
        else
        {
            *T=(BiTree)malloc(sizeof(BiTNode));	//动态生成结点
            if(!*T)
            {
                exit(OVERFLOW);	//（内存分配失败）异常判断
            }
            (*T)->data=ch;
            CreatBiTree(&(*T)->lchild);
            CreatBiTree(&(*T)->rchild);
        }
    }

  8. 线索二叉树（加上标志域tag，进行切换==孩子==和==前后==的二叉树）

    1. 结构：2f934f0cd86823d6ee9c2101da90857e.png
    2. 线索化：将二叉链表中的空指针改为指向前驱后继的线索（对二叉树==以某种次序遍历(前/中/后)==，使其==变为线索二叉树==）【线索化过程：修改空指针的过程】
    1
    2
    3
    4
    5
    6
    7
    8
    9
    //线索二叉树结点结构
    //link = 0;thread = 1
    typedef enum {Link,Tread} PointerTag;
    typedef struct BiThrNode
    {
        char data;
        struct BiThrNode *lchild,*rchild;	//左右指针域
        PointerTag LTag,RTag;	//左右标志域
    }BiThrNode,*BiThrTree;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    //中序遍历线索化
    //pre：临时存放上一个结点（用于作前驱）；p：用来索引结点
    BitThrTree pre;	//全局变量，指向刚刚访问过的结点
    void InThreading(BiThrTree p)
    {
        if(p)	//树p存在
        {
            InThreading(p->lchild);	//左
            /*******线索化过程*********/
            if(!p->lchild)
            {
                p->LTag=Thread;
                p->lchild=pre;
            }
            if(!pre->rchild)
            {
                pre->RTag=Thread;
                pre->rchild=p;
            }
            /****************************/
            pre=p;	//pre指向旧p
            InThreading(p->rchild);	//右
        }
    }

  9. 树、森林、二叉树的转换

    1. 树 转换为 二叉树（转换方式：二叉链表）【右兄变右孩子】

    2. 森林 转换为 二叉树：1、==每棵树==转成二叉树。2、后一棵树==根结点==作为==前一个根的右孩子==。

    3. 二叉树 转换 树：（转换方式：逆二叉链表）【右孩子变右兄】

    4. 二叉树 转换 森林：1、==判断==：根有无右孩子。2、从根开始，==遇右==孩子==断开==

    5. 森林的遍历：先根，后根；树的遍历：前序，后序

  10. 哈夫曼树（最优二叉树）

    1. 哈夫曼树概念：

      1. 权：边上的数
      2. 路径长度：边的数目
      3. 带权路径长度：路长 * 结点上的权
      4. 【WPL】树的带权路径长度：所有结点带权路长之和（WPLmin == 哈夫曼树）

    2. 哈夫曼树生成方式：

      1. ==从小到大==排列带权的叶结点
      2. 选出==两个最小结点==，==小左大右==，==相加作为新结点权值==
      3. 加入新结点，==重复操作==

  11. 哈夫曼树的应用：哈夫曼编码方式（无损压缩、数据传输优化）

    1. 叶结点（源码）：{d1,d2,……,dn-1,dn}
    2. 叶结点权值（各个字符出现的频率）：{w1,w2,……,wn-1,wn}
    3. 左0右1：小左大右构成树
    4. 哈夫曼编码：根结点 到 叶结点路径01序列
  1. 1. 树
    1. 1.0.1. 树的定义（一对多）
    2. 1.0.2. 树的存储结构
    3. 1.0.3. 二叉树的定义&特点
    4. 1.0.4. 二叉树的性质
    5. 1.0.5. 二叉树存储结构
    6. 1.0.6. 二叉树的遍历（从根结点出发，按照不同次序，对每个结点进行访问）
    7. 1.0.7. 扩展二叉树的建立【经处理后的二叉树：虚结点“#”表示空NULL】
    8. 1.0.8. 线索二叉树（加上标志域tag，进行切换==孩子==和==前后==的二叉树）
    9. 1.0.9. 树、森林、二叉树的转换
      1. 1.0.9.1. 树 转换为 二叉树（转换方式：二叉链表）【右兄变右孩子】
      2. 1.0.9.2. 森林 转换为 二叉树：1、==每棵树==转成二叉树。2、后一棵树==根结点==作为==前一个根的右孩子==。
      3. 1.0.9.3. 二叉树 转换 树：（转换方式：逆二叉链表）【右孩子变右兄】
      4. 1.0.9.4. 二叉树 转换 森林：1、==判断==：根有无右孩子。2、从根开始，==遇右==孩子==断开==
      5. 1.0.9.5. 森林的遍历：先根，后根；树的遍历：前序，后序
    10. 1.0.10. 哈夫曼树（最优二叉树）
      1. 1.0.10.1. 哈夫曼树概念：
      2. 1.0.10.2. 哈夫曼树生成方式：
    11. 1.0.11. 哈夫曼树的应用：哈夫曼编码方式（无损压缩、数据传输优化）