树是一种有节点(树形结构中的逻辑单元,用于保存数据)和节点间的联系组成,但其结构和线性结构(表)不同,最重要的特征是:

  • 每个节点都只有一个前驱
  • 一个节点可以有很多后继
  • 从一个树形结构里面的任意两个节点出发,通过后继关系可达的节点集合,相互之间或者互不相交,或者有子级关系

树形结构常被用来表示层次性关系,树形结构形成了对其节点集合的一种层次性的划分,这类关系具有层次性,只有高层和低层可能有关,同层元素之间相互无关,也没有低层到高层的关系,和不同元素相关的元素互不相交。

树形结构-节点连线图

树形结构-韦恩图

相关概念

父节点和子节点:

  • 一棵树的根节点称为该树的子树的根节点的父节点
  • 子树的根是树根的子节点

边:

  • 从父节点到子节点的连线
  • 边是有方向的

兄弟节点:

  • 父节点相同的节点互称为兄弟节点

树叶、分支节点:

  • 没有子节点的节点称之为树叶,树中其余节点称为分支节点(分支节点可以只有一个分支)

祖先和子孙:

  • 基于父节点和子节点关系和传递性,可以确定相应的传递关系,称为祖先关系或者子孙关系

度数:

  • 一个节点的子节点个数称为该节点的度数,显然树叶的度数为零,一棵树的度数就是它里面度数最大的节点的度数

路径、路劲长度:

  • 从一个祖先节点到其子孙节点的一系列边称为树中一条路径
  • 路径中的边数称为路径的长度

节点的层数:

  • 树根到节点的路径长度是该节点的层数
  • 节点都有层数,根节点的层数为0

高度(或深度):

  • 树的高度或深度是树中节点的最大层数

树林:

  • m(m >= 0)棵互不相交的树的集合
  • 一课非空树是一个二元组 Tree=(r, F),其中
    • r 是树的根节点
    • F 是 m (m >= 0) 棵树构成的树林

三棵树组成的森林如下:

二叉树

二叉树的五种形态

二叉树不是树的特殊情形,主要是其子树分左子树和右子树,即使只有一棵子树也要明确说明是左还是右。画二叉树的图示时,需要明确地把子树画在左边或右边,下面是两棵不同的二叉树,而作为树它们是相同的。

左右二叉树

满二叉树和完全二叉树

满二叉树:
除最后一层无任何子节点外,每一层上的所有结点都有两个子结点。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值,所有叶子结点必须在同一层上。

满二叉树的性质:

  • 一个树的深度为 h ,最大层数为 k ,深度和最大层数相同,k = n
  • 叶子数为2^h
  • 第 i 层节点数是 2^(i - 1)
  • 总的节点数为 2^(h - 1)

完全二叉树:

完全二叉树,若二叉树的深度为 h ,除第 h 层外,其它各层 (1~(h-1)层) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

完全二叉树的性质:

  • 在非空二叉树中,第 i 层的结点总数不超过2^(i - 1), i >= 1;

  • 深度为 h 的二叉树最多有 2h - 1 个结点(h>=1),最少有 h 个结点;

  • 对于任意一棵二叉树,如果其叶结点数为 N0,而度数为2的结点总数为 N2,则 N0 = N2 + 1;

  • 具有 n 个结点的完全二叉树的深度为 log2(n+1);

  • 有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:

    • 若I为结点编号则 如果I>1,则其父结点的编号为I/2;
    • 如果2I<=N,则其左儿子(即左子树的根结点)的编号为2I;若2I>N,则无左儿子;
    • 如果2I+1<=N,则其右儿子的结点编号为2I+1;若2I+1>N,则无右儿子。
  • 给定 N 个节点,能构成 h(N) 种不同的二叉树,其中,h(N) 为卡特兰数的第N项,h(n) = C(2*n, n)/(n + 1)