数据结构笔记——树

1、树的概念

• 定义

  递归定义：树是由n（n≥0）个节点组成的有限集合（记为T）。其中：

  • 如果n=0，它是一棵空树，这是树的特例；

  • 如果n>0，其中存在一个唯一节点作为树的根节点（root），其余节点可分为m（m≥0）个互不相交的有限子集T1、T2、…、Tm， 而每个子集本身又是一棵树，称为根节点root的子树。

• 逻辑表示

  • 树形表示法
  • 文氏图表示法
  • 凹入表示法
  • 括号表示法

• 基本术语

  • 节点的度：该节点子树的个数

  • 树的度：树中各节点度的最大值（度为m的树 称为m次树或者m叉树

  • 分支节点（非终端节点）：度不为零的节点

    （度为1的结点称为单分支节点；度为2的节点称为双分支节点， 依此类推。

  • 叶节点（叶子节点/终端节点）：度为零的节点

  • 孩子节点、双亲节点和兄弟节点：

    • 一棵树中，每个节点的后继，被称作该节点的孩子节点（或子女节点）。

    • 相应地，该节点被称作孩子节点的双亲节点（或父母节点）。

    • 具有同一双亲的孩子节点互为兄弟节点。

  • 子孙节点和祖先节点：

    • 一棵树中，一个节点的所有子树中的节 点称为该节点的子孙节点。

    • 从根节点到达一个节点的路径上经过的所有节点被称作该节点的祖先节点。

  • 节点的层次和树的高度：
    树中的每个节点都处在一个层次上。

    • 节点的层次从树根开始定义，根节点为第1层，它的孩子节点为第2 层，以此类推，一个节点所在的层次为其双亲节点所在的层次加1。
    • 树中节点的最大层次称为树的高度（或树的深度）

  • 路径与路径长度：

    • 两个节点$d_i$di​和$d_j$dj​的 节点序列（$d_i$di​，$d_{i1}$di1​，$d_{i2}$di2​，…，$d_j$dj​）称为路 径。其中<$d_x$dx​，$d_y$dy​>是分支。
    • 路径长度等于路径所通过的节点数目减1（即路径上分支数目）。

  • 有序树和无序树：若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。

  • 森林：n(n>0)个互不相交的树的集合。

• 树的性质

  • 性质1：树中的节点数等于所有节点的度数加一。
  • 性质2：度为m的树中第i层上至多有$m^{i-1}$mi−1个节点（i≥1）
    • 数学归纳法证明
  • 性质3：高度为h的m次树至多有$\frac{m^h-1}{m-1}$m−1mh−1​个节点
    • 证明：$m^0+m^1+m^2+\cdots+m^{h-1}=\frac{m^h-1}{m-1}$m0+m1+m2+⋯+mh−1=m−1mh−1​
  • 性质4：具有n个节点的m次树的最小高度为$log_m(n(m-1)+1)$logm​(n(m−1)+1)

• 树的基本运算

  • 查找
  • 插入或删除
  • 遍历
    • 先根遍历：先访问根节点，然后依次先根遍历各棵子树（ABEFCDGHIJK)
    • 后根遍历：先依次后根遍历各棵子树，然后访问根节点(EFBCIJKHGDA)
    • 层次遍历：自上而下、自左至右(ABCDEFGHIJK)
      

• 树的存储结构

  • 双亲存储结构

    typedef struct
    {
    	ElemType data; //节点的值
    	int parent;  //指向双亲的位置
    }PTtree[MaxSize];
    

    求某个双亲结点十分容易；但在求某个结点的孩子节点时，需要遍历整个存储结构。

  • 孩子链存储结构

    typedef struct node
    {
    	ElemType data; //结点的值
    	struct node *sons[MaxSons]; //指向孩子的结点
    }TSonNode;
    

    查找某节点的孩子结点方便；查找某节点的双亲结点费时