二叉树基础(上)

Sunday, May 5, 2019

树的特点

树有三个相似的概念:高度,深度,层

file

file

二叉树

每个节点最多有两个子节点,分别是左子节点和右子节点。

file

编号2是满二叉树。编号3是完全二叉树,叶子结点在最底下两层,最后一层的叶子结点都靠左排列,除了最后一层,其它层的节点个数都要达到最大,这种就是完全二叉树。

file

如何表示(存储)一颗二叉树

一种是基于指针或者引用的二叉链式存储法,一种是基于数组的顺序存储法。

链式存储法

file

顺序存储法

file

如果是非完全二叉树,会浪费比较多的数组存储空间

file

如果是一颗完全二叉树,用数组最节省内存,这也是为什么完全二叉树会单独拿出来说明,为什么最后一层子节点要靠左的原因。

二叉树遍历

经典的遍历方法有三种

  • 前序遍历
  • 中序遍历
  • 后序遍历

file

二叉树的前中后序遍历实际就是一个递归的过程。二叉树的遍历的时间复杂度是O(n),跟节点个数n成正比

数据结构-算法

二叉树基础(下)

散列表(下)