树的基本概念

没有回路的联通无向图

特性

  1. 任意两节点有且只有唯一通路
  2. 树有n个节点,就会有n-1条边
  3. 在树中加一条边将会构成一个回路

结构

父节点、子节点、叶节点


二叉树

一种特殊的树,每个父节点只有两个子节点:左儿子、右儿子。

满二叉树:深度为h,且有$2^{h}-1$个节点的二叉树(所有叶节点都具有相同深度。)
完全二叉树:设树高为h,除第h层外,其他各层的节点数都达到最大个数,第h层从右向左连续缺若干节点。(最右边有一或多个叶节点缺少,其他丰满)

  • 有N个节点的完全二叉树的高度为 $\log N$

完全二叉树储存

使用一维数组,对于一个编号为k的节点,他的左儿子编号为2k,右儿子编号为2k+1。


特性

最小堆:所有父节点都比子节点小的完全二叉树。
最大堆:所有父节点都比子节点大的完全二叉树。
插入新元素所需时间 O(logN)。
n个元素建立堆,则最后一个非叶节点的编号为n/2

建立一个堆

建立一个完全二叉树,从最后一个节点开始依次判断以这个节点为根的子树是否符合最大(小)堆的特性。
时间复杂度 O(N)

Tags:数据结构
上一篇
下一篇

添加新评论