数据结构与算法--二叉树的顺序存储&链式存储_二叉树的顺序存储和链式存储

1. 树的相关概念

根节点（Root）：树的顶部节点

子节点（Child）：离开根节点时直接连接到另一个节点的节点。

叶子节点（Leaf）：没有子节点的节点

边（Edge）：一个节点与另一个节点之间的连接。

路径（Path）：连接节点与子代节点的节点和边的序列。

节点高度（Height）：节点和叶子之间最长路径上的边的数量

注意：叶子节点的高度为0，如果树只有一个节点，那么这个节点的高也是0
1

深度（Depth）：从该节点到树的根节点的边数总和。

注意：
需要注意的是根节点的深度（Depth）是0.
从高度和深度的对比，它们的方向刚好是相反的。
1
2
3

度：节点的子树数目

层级（Level）：该节点到树的根节点的最长路径的边数总和+1。

双亲节： 树的双亲节点是一个节点，如上图中，4的双亲节点是2

二叉树： 二叉树是一个每个最结最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。二叉树节点的度最大也就是2，而普通的树，节点的度是没有限制的。

完美/满二叉树:

1. 所有的几点都包含两个子节点
2. 所有的叶子节点的Height或者Level都相等

完全二叉树：最后一层都是满的（都有两个子节点），并且最后一层的节点是从左往右排列的。

通俗的讲：节点按层从左往右排列。最后一层排满了就是完美二叉树，没有满则是完全二叉树。
完美二叉树一定是完全二叉树，完全二叉树不一定是完美二叉树。
1
2