6.1 树的概念

树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树

树的术语：

（1）节点的度：各个节点所含有的子树的个数

（2）树的度：最大的节点的度

（3）叶节点：度为0的节点

（4）父节点：一个节点含有子节点，则这个节点为父节点

（5）孩子节点：一个节点含有的子树的根节点称为该节点的子节点。

（6）兄弟节点：具有相同父节点的节点成为兄弟节点。

（7）节点的层次；

（8）树的高度或深度：树节点的最大层次。

（9）堂兄弟节点：父节点在同一层的节点互为堂兄弟。

（10）节点的祖先；子孙；森林等

树的种类：

（1）无序树

（2）有序树

        二叉树，每个节点最多含有两个子树的树

        完全二叉树：深度为d的树，除了最后一层外，其它各层的节点数目已经达到了最大值。

        满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树

        平衡二叉树：任何节点的两棵子树的高度差不大于1。

        排序二叉树：二叉搜索树、有序二叉树.

霍夫曼树：带权路径最短的二叉树，称为了哈夫曼树或最优二叉树。

B树：一种对读写操作进行优化的自平衡的二叉树。

树可以和我们的顺序存储与链式存储相互结合。

6.2 二叉树

二叉树是指：每个节点最多有两个子树的结构

二叉树的性质：

（1）在二叉树的第i层上最多有 2^(i-1) 棵树

（2）深度为k的二叉树最多有  2^k-1 个节点

（3）具有n个结点的完全二叉树的深度必为 log2(n+1)

（4）具有n个结点的完全二叉树的深度必为 log2(n+1)

（5）对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外

6.3 二叉树的节点表示以及树的创建

树的遍历包括了

前序遍历（根节点，左节点，右节点）

中序遍历（左节点，根节点，右节点）

后序遍历（左节点，右节点，根节点）

层次遍历（从上到下，从左到右）