理解树结构

树结构通常用来存储逻辑关系为 “一对多” 的数据。

的这些元素具有的就是 “一对多” 的逻辑关系，例如元素 A 同时和 B、C、D 有关系，元素 D 同时和A、H、I、J有关系等。 观察这些元素之间的逻辑关系会发现，它们整体上很像一棵倒着的树（将图 1b) 倒过来），这也是将存储它们的结构起名为“树”（或者 “树形”）的原因。

存储具有 “一对多” 逻辑关系的数据，数据结构推荐使用树存储结构。

与树相关的术语

数据结构中的树，首先是对现实世界中树的一层简化：

抽象后的树结构如下：
把这棵抽象后的树颠倒一下，就得到了计算机中的树结构：

• 树的根节点,叶子节点(不能分叉的节点)
• 树的深度
  
• 树的度：整个树里(包括根节点在内)，节点分叉最多的度！就是树的度！
• 孩子节点、父节点（类似族谱去理解）
• 子树 （族谱，比如儿子的新家庭，那么儿子下面就构成了一个新的子树）
  

理解二叉树结构

二叉树，就是度不超过2的树！
它可以没有根结点，作为一棵空树存在

如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。如下图：

注意，二叉树不能被简单定义为每个结点的度都是2的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的。对应到图上来看，也就意味着 B 和 C、D 和 E、F 和 G 是不能互换的。（按照顺序从左到右！）

满二叉树

一个树，如果每一层的节点数都达到最大值2，则这个二叉树为满二叉树！

完全二叉树

叶结点只能出现在最下层和次下层，并且最下面一层的节点，都集中在该层最左边的若干位置的二叉树！

二叉树的存储方式！

二叉树的存储方式分为两种

一个是顺序存储

顺序存储：数组方式存储，表现上是一个一维数组，逻辑上是一颗二叉树

• 圆圈顶部的数字对应了数组中的索引
• 圆圈内部的值对应的数数组元素的值

规律思考：

1. 父节点i(这个i指的是顺序存储的索引)和左孩子节点的编号下标有什么关系？
   0-1 1-3 2-5 存在 2ⁱ+1 的数学规律！
2. 父节点i和右孩子节点的编号下标有什么关系？
   那么知道了父节点和左孩子节点的规律，那么右孩子其实就是多一个位置 那么就是2ⁱ+2
3. 通过子节点的索引i找到父节点的规律？
   1,2-0 3,4-1 5,6-2 如果子节点-1然后整除（除完取整）比如（1-1/2 = 0;2-1/2 = 0.x0.x取整也为0）所以父节点就是在数组中索引为0的，其他的也是一样的！

另一个是链表存储（这个我还没有学）

链表存储：采用链表的方式进行存储，链表包含逻辑关系，左指针，右指针。从表现到逻辑都是一颗二叉树。