4.3.1 树、二叉树基本概念
目录
树的基本概念
二叉树基本概念
二叉树存储结构
树的基本概念
树：一个元素可以有≥2个直接后继元素。 非空树有且只有一个根结点。
- 双亲，孩子，兄弟：结点的根节点称为结点的双亲。结点的子结点称为该结点的孩子。相同双亲的结点互为兄弟。
- 结点的度：结点的子树个数。
- 叶子结点：度为0的结点。
- 内部结点：度不为0的结点。
- 结点的层次：根为第一层，根的孩子为第二层，依次类推。
- 树的高度：树的最大层次为数的高度。
- 有序（无序）树：树中结点看作从左到右有序，不能交换顺序，称为有序树。否则称为无序树。
- 森林：m(m≥0)颗互不相交的树形成的集合。
二叉树基本概念
二叉树：树中每个结点要区分左子树、右子树。二叉树中结点最大的度为2。
满二叉树：深度为k的二叉树，其结点个数为2^k-1。
完全二叉树：其结点与满二叉树中1~n的结点编号一一对应。
高度为h的二叉树中，除了最后一层，其余各层都是满的。最后一层的结点必须是从左到右放置。因而有n个结点的完全二叉树高度为
二叉树存储结构
二叉树顺序存储，对于结点i，左孩子存放位置为2i, 右孩子存放位置是2i+1。 顺序存储适用于完全二叉树，但一般二叉树用顺序存储时会有很多位置未被使用。
二叉树链式存储，结点中需要包含数据元素、左子树、右子树，即一个结点含有3个或两个指针。
typedef struct BiTnode{
char data;
struct BiTnode *lchild, *rchild;
} BiTnode;