0%

数据结构之非线性结构

非线性结构

现实中不只是有那种一对一的线性结构,还有很多一对多的非线性结构,如树、图等

线性表、队列、栈都是线性的,这个数据结构不能反映元素之间的层次特性。使用树形结构来描述数据之间的关系。

树的定义

树是n个节点的集合,集合中有一个称为根(root)的特殊节点,在根节点下分布着一些互不相交的集合,每一个集合又是一个树,这些树称为根节点的子树。

  • 在一棵树中,有且仅有一个节点没有前驱,这个节点就是树的根节点

  • 除根节点外,其余每个节点有且仅有一个前驱

  • 每个前驱可以有任意多个后继

相关术语

  • 父节点、子节点、兄弟节点 每个节点的子树的根称为该节点的子节点,相应的,该节点被称为子节点的父节点,具有同一父节点的节点称为兄弟节点
  • 节点的度 一个节点的子树的数量称为该节点的度,度为0的节点称为叶子节点,度不为0的节点称为分支节点
  • 树的度 一棵树的度值该树中节点的最大度数
  • 叶节点和分支节点 树中度为0的节点称为叶节点或终端节点。树中度不为0的节点称为分支节点
  • 节点的层数 每个节点都处在一定的层次上,从树根开始计算,根节点为第一层,依次向下,树中节点的最大层数称为树的深度
  • 树的深度 一棵树中节点的最大层数称为树的深度
  • 有序树和无序树 若树中各节点的子树(兄弟节点)是按照一定次序从左到右排列的,称为有序树,否则称为无序树
  • 森林 多个互不相交的树的集合

二叉树

二叉树任意节点最多只能有两个子节点;如果只有一个子节点,可以是左子树,也可以是右子树,二叉树的度最大为2,二叉树是有序树

特点
  • 在二叉树的第i层上至多有2^i-1^个节点
  • 深度为k的二叉树至多有2^k^-1个节点
  • 对任何一棵二叉树T,如果其叶子节点数为n0,度为2的节点数为n2,则n0=n2+1
  • 具有n个节点的完全二叉树的深度为log2n+1
  • 如果对一棵有n个节点的完全二叉树的节点按层序编号,对任一节点i有:如果i=1,则节点i是二叉树的根;如果i>1,则双亲节点时i/2;如果2i>n,则节点i无左孩子节点;否则其左孩子节点为2i;如果2i+1>n,则节点i无右孩子;否则其右孩子是节点2i+1
特殊结构
  • 满二叉树 在二叉树中,除最下一层的叶节点外,每层的节点都有两个子节点,就构成了满二叉树
  • 完全二叉树 除二叉树最后一层外,其他各层的节点数都达到最大个数,且最后一层从左到右的叶节点连续存在,只缺右侧若干节点,就是完全二叉树
  • 满二叉树肯定是完全二叉树,而完全二叉树不一定是满二叉树

存储结构

可以有三种存储方式

  • 双亲表示法:在每个节点中记录双亲节点地址,以及该节点数据,但是如果要获取孩子节点需要遍历整个树
  • 孩子表示法:每个节点都可能有多棵子树,可以使用链表来保存孩子节点的地址
  • 孩子兄弟表示法:任意一棵树,它的节点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的,可以保存该节点的第一个孩子节点地址和该节点的右兄弟节点地址,如果有必要,也可以增加双亲节点地址

图是由顶点的有穷非空集合和顶点间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V表示G中顶点的集合,E表示图G中边的集合

  • 在图中数据元素,称为顶点,且顶点不能为空
  • 在图中,任意两个顶点之间都有可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的