二叉树

树

非线性表结构

父节点 子节点 兄弟节点:
节点 储存数据 同时储存 子节点的指针,同一节点下的 所有子节点 互为兄弟节点

根节点:没有父节点 的节点

叶子节点:没有子节点 的节点

节点的
高度(Height):当前节点到叶子节点的边数(叶子节点为0,根节点为 层数-1)
深度(Depth):根节点到这个节点的边数(根节点为0,叶子节点为 层数-1)
层(Level):节点的深度 +1(根节点为1,叶子节点为 深度+1)

深度 从上往下数(如水深),初始0; 高度 从下往上数(如楼房),初始0.
层数 同深度,但初始为1
树的高度:根节点的高度

二叉树

由一个空节点 或 两颗不相交二叉树组成(递归定义)

满二叉树 除了叶子节点 每个节点都有左右两个节点组成

完全二叉树 除了最后一层,其他层都是满节点,叶子节点都在左边.

如何储存一个二叉树

链式储存法 基于链表,每个节点三个字段,一个存数据,两个存左右节点的指针.

顺序储存法
完全二叉树:
1.基于数组,根节点放在i=1的位置,一层一层从左往下,依次放入数组.
2.此时,如果节点X在i位置,左子节点就是2 * i,右子节点就是2 * i + 1.

非完全二叉树:
按照上面 (2.)的方式放入数组,