首页 > 代码库 > 树的基本概念

树的基本概念

树是由\(n (n \ge 0)\)个节点组成的有限集合(记为\(T\))。其中如果\(n=0\),它是一棵空树;如果\(n \gt 0\),这 \(n\)个节点中存在一个节点作为树的根节点,其余节点可分为\(m (m \ge 0)\)个互不相交的有限集\(T_1、T_2、...T_m\),其中每个集合本身又是一棵树,称为根节点的子树。「递归定义」

一些基本概念

  • 节点的度:节点中拥有的子树个数或者分支个数。
  • 树的度:树中各节点度的最大值,通常将度为\(m\)的树称为\(m\)次树。
  • 叶子(终端)节点:度为 \(0\) 的节点
  • 分支(非终端)节点:度不为 \(0\) 的节点
  • 层次:从根开始,根为第一层,根的孩子为第二层,依次类推
  • 树的高度:树中节点的最大层次。
  • 森林:\(n (n \ge 0)\) 个互不相交的树的集合称为森林。森林和树的定义十分相似,只要把树的根节点删除就成了森林,反之,只要给 \(n\) 棵独立的树加上一个节点,并把这\(n\)棵树作为该节点的子树,则森林变成了树

树的一些性质

  • 树中的节点数 \(n\) 等于所有节点的度数加 \(1\)。度之和=分支数,而分支数=n-1
  • 度为\(m\)的树中第\(i\)层上至多有 \(m^{i-1}\) 个节点
  • 高度为 \(m=h\) 的树中第\(i\)层上至多有 \(\frac{m^{h}-1}{m-1}\) 个节点
  • 具有\(n\)个节点的 \(m\)次树的最小高度为 \(\ulcorner log_m(n(m-1)+1)\urcorner\)

树的存储结构

  • 双亲存储结构: 顺序存储结构,用一组连续空间存储树的所有节点,同时在每个节点中附设一个伪指针指示其双亲节点的位置。其中根节点的伪指针为\(-1\)。 技术分享? 利用了每个节点(根节点除外)只有唯一双亲节点的性质。这种存储结构中,求某个节点的双亲节点的时间复杂度为\(O(1)\),求某个节点的孩子节点的时间复杂度为 \(O(n)\)
  • 孩子链存储表示:\(d\)越大,空间浪费越严重。 技术分享? 技术分享?
  • 孩子兄弟链存储: 技术分享? 技术分享?

树的遍历

  • 先根遍历:先访问根节点,再按照从左到右的次序先根遍历该根节点的每一个子树:
    技术分享?

  • 后根遍历:先按照从左到右的次序后根遍历根节点的每一棵子树,再访问根节点。

二叉树

二叉树是由 \(n (n \ge 0)\) 个节点的有限集合,该集合或者为空集
,或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

技术分享?

  • 满二叉树:一棵高度为\(h\) 且有\(2^h-1\)个节点的二叉树。即所有分支节点都有左右孩子,并且叶子节点集中在二叉树的最下层。
    • 叶子节点都在最后一层
    • 只有度为 \(0\) 和度为 \(2\) 的节点
  • 完全二叉树:对一棵具有\(n\)个节点的完全二叉树按层次编号,当且仅当每一个节点都与高度为 \(h\) 的满二叉树编号一一对应
    • 叶子节点只可能在层次最大的两层上出现
    • 对于最大层次中的叶子节点,都依次排列在该层最左边的位置上
    • 如果有度为 \(1\) 的节点,只可能有 \(1\) 个,且该节点只有左孩子而无右孩子
    • 按层次编号后,一旦出现某个节点(其编号为\(i\))为叶子节点或只有左孩子,则编号大于 \(i\) 的节点均为叶子节点
    • 当节点总数\(n\)为奇数时,\(n_1=0\),当节点总数为\(n\)为偶数时\(n_1=1\)

二叉树的性质

  • 每个节点最多有两棵子树,二叉树中不存在度为\(2\)的节点
  • 子树的顺序不能颠倒,某节点即使只有一棵子树也要区分是左子树还是右子树
  • 由\(n\)个节点构成的二叉树的形态总数为\(\frac{C_{2n}^n}{n+1}\) 技术分享?
  • 非空二叉树的叶子节点数等于双分支节点数\(+1\)
  • 具有\(n\) 个节点的完全二叉树的高度为\(\ulcorner log_2(n+1) \urcorner\)

二叉树的存储

  • 树的顺序存储:用一个数组来存储一棵二叉树,这种存储方式最适合于完全二叉树,用于存储一般的二叉树会浪费大量的存储空间。 技术分享? 技术分享?
  • 链式存储结构:
    • 二叉链存储结构:技术分享? 技术分享?
    • 三叉链表存储结构:技术分享?

二叉树的遍历

  • 先根(前序)遍历: 技术分享? 技术分享?
  • 中根(中序)遍历:
    技术分享?
    中序遍历的非递归实现:先扫描(并非访问)根节点的所有左节点并将它们一一进栈。然后出栈一个节点p,显然p没有左孩子节点或者左孩子节点已经访问过了,则访问它,然后扫描该右孩子节点的所有左孩子节点并一一进栈,如此继续直到栈空为止。
    技术分享?

  • 后根(后序) 遍历:
    技术分享?
    后序遍历的非递归实现:先扫描根节点的所有左节点并一一进栈,扫描完之后出栈一个节点*p,即当前节点,然后扫描该节点的右孩子节点并进栈,再扫描该右孩子的节点的所有左节点并进栈。当一个节点的左、右孩子节点均访问后再访问该节点,如此反复,直到栈空为止。
    难点是怎么判断一个节点的右孩子节点已经访问过?,不妨使用q来保存右子树中刚刚被访问的节点(初值为NULL),若此时满足p->rchild==q成立,说明此时p的左右孩子均已访问,现在应该访问p节点。
    技术分享?

树的基本概念