数据结构与算法 - 二叉树
啥是树
"树"这种数据结构和我们生活中的树很像。里面的每个元素我们都称为节点,用线来连线相邻节点之间的关系,我们叫做父子节点。
树的结构
跟 HTML 的结构是一样的。
比如下面这幅图,A 节点就是 B 节点的父节点,B 节点就是 A 的子节点。B C D 的节点都是同一个节点,所以他们之间互称为兄弟节点。我们把没有父节点的节点叫做跟节点,比如图中的 E。没有子节点的叫做叶子节点或者叶节点,比如图中的 G H I J K L 。
树的概念
树的高度、深度和层。
高度 从下往上测量的,就像我们要测量一个10层高的楼层,都是从地面开始计算,在这里树的结构也是一样的,从最底层开始计算,计算的起点是0。
深度从上向下测量,比如测量水中的深度,从水平面向下测量,树的结构也是这样的,从跟节点开始计算,计算的起点是0。
层 和深度计算的基本一样,只不过层是从 1开始计算。
二叉树
二叉树,每个节点最多有两个叉,也就是 2 个子节点,分别是左子节点和右子节点。不过,二叉树并不要求每个节点,都有 2 个子节点。所以下面的都是
不过上图中的 2 号 3号比较特殊些。
2 号二叉树中,叶子节点全部都在最底层,除了叶子节点之外,每个节点都是 2 个子节点,这种的叫做满二叉树。
3 号二叉树中,叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都达到最大,这种的叫做完全二叉树。
存储二叉树
二叉树有 2 种方法可以存储,分别是基于指针或引用的二叉链式存储法和基于数组的顺序存储法。
链式存储法比较简单和直观,是常用的二叉树方式。每个节点都有 3 个字段,一个存储数据,另外 2 个是指左右子节点的指针。我们只要拎住根节点,就可以通过左右子节点的指针,把整颗树串起来。
顺序存储法基于数组的。
根节点存储在 i = 1 的位置。
左子节点存储在 2 * i
(2 * 1 = 2) 的位置
右子节点存储在2 * i + 1
(2 * 1 + 1 = 3) 的位置
上图中,B 节点的左子节点存储在 2 * i = 2 * 2 = 4
的位置
右子节点的存储在 2 * i + 1 = 2 * 2 + 1 = 5
的位置。
总结: 节点 X 存储在数组中的下标为 i 的位置,左子节点的位置就是下标为 2 * i,右子节点的位置就是下标为 2 * i + 1 的位置。返过来,下标为 i/2 的位置就是它的父节点,通过这种方式,我们只要知道根节点的存储位置,就可以通过下标计算,把整颗树串起来。
刚刚举例的是一个完全二叉树,所以只浪费了一个下标为 0 的存储位置,如果是非完全二叉树,会浪费更多的数组存储空间。比如图下。
遍历二叉树
前序遍历、中序遍历、后序遍历是遍历二叉树的三种经典方法。
前序遍历是指对于树的任意节点来说,先打印这个节点,然后在打印它的左子节点,最后打印右子节点。
中序遍历是指对于树的任意节点来说,先打印它的左子树,在打印它的本身,最后在打印右子树。
后序遍历是指对于树的任意节点来说,先打印它的左子树,在打印它的右子树,最后在打印这个节点本身。
未完待续…