基本概念

树的定义

在图论中,树是一种无向图,其中任意两个顶点间存在一条唯一路径.

换句话说,没有环的连通图就是树.并且树有层次关系,其有且仅有一个根节点.

如果一个无向简单图G满足如下关系,那么G是一棵树:

  • G是没有环的连通图
  • G内添加一条边则会形成一个环
  • G删除一条边则不再联通
  • G中任意2个顶点间存在唯一路径

与线性表不同,树是一种非线性的结构,并且各顶点(数据项)间有一定的层次关系,一个顶点有着0个或若干个子顶点.

各结点的关系

image-20240108191132338

森林

森林是m(m>=0)棵互不相交的树的集合.

每棵树去掉其根节点后,剩下的部分即若干个子树,构成一个森林.

常见属性

  1. 结点的度

    一个节点含有的子树的个数称为该节点的度

  2. 树的度

    一棵树中,最大的结点的度称为树的度,例如二叉树的度为2

  3. 树的高度(定义不统一)

    高度从下向上数,即该节点到叶子结点的最长路径(边数)+1,叶子结点的高度为1

  4. 树的深度(定义不统一)

    深度从上向下数,即从树根到该节点的路径(边数)+1,树根的深度为1

常用公式

一般的树

  1. 总结点数 = 总度数 + 1

二叉树

  1. 第i层有2^(k-1)个结点(k>=1)

  2. 深度为m的二叉树最多有2^m-1个结点,最少有m个节点

    最多时为满二叉树,最少时退化为单链表

  3. 任意一颗二叉树,叶子结点数为N0,度为2结点数为N2,则N0 = N2 + 1

    证明: 度为1的结点数为N1,总结点数为N,则N=N0+N1+N2,又总度数=N1*1+N2*2,且N=总度数+1,联立即可得出.

  4. 具有n个结点的完全二叉树,其深度为[log2(n)]+1,其中[log2(n)]为向下取整

  5. 具有n个结点的满二叉树,其深度为log2(n+1)或[log2(n)]+1

  6. 对完全二叉树从上到下,从左到右从1依次编号,第i个结点的父亲是[i/2],左孩子是2*i,右孩子是2*i+1