数据结构 ——数状存储的基本概念
一、树状存储基本概念
1、 深度（层数）：计算一个节点的深度，从根节点算起（从1开始计数），到该节点所经过的节点数（包括此节点）为树的深度，如下图，D的深度为3，G为4
- 度（子树个数）：一个节点的度是该节点的子节点（或子树）的个数。树的度是指树中所有节点的度的最大值
如上图，树的度为2 - 叶子节点：叶子节点是指没有子节点的节点，即度为0的节点。如上图D、G、F
- 孩子节点：某个节点的直接下属节点称为该节点的孩子。
- 兄弟节点：具有同一个父节点的多个节点之间互称为兄弟。
- 堂兄弟节点：具有同一祖父节点但不同父节点的节点之间互称为堂兄弟。
2、二叉树
二叉树是一种特殊的树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树有以下几种特殊形式：
- 满二叉树：一颗二叉树如果除了叶子节点外，每个节点都有两个子节点，并且所有叶子节点都在同一层次上，那么这个二叉树就是满二叉树。或一个深度为k（k>=1）的树上有2^k-1个节点的二叉树。
- 完全二叉树：一颗树除了最后两层可以存在有不满足两个节点的点之外（且只有一个节点的话，该节点必须为左孩子），其它节点必须有两个子节点。如下图：
3.存储方式
顺序存储：利用数组存储二叉树。通常按层次顺序存储，从根节点开始，依次存入数组的相应位置。只能存储二叉树
链式存储：利用链表存储二叉树。每个节点使用一个结构体表示，结构体包含数据域和两个指针域，分别指向左子节点和右子节点。
