树：是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。由n（n>0）个有限结点组成一个具有层次关系的集合。
特点：
每个结点有零个或多个子结点；没有父结点的节点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；一些相关概念：
结点的度：结点所拥有的子树的数目称为该结点的度。（叶子结点：度为0的结点。 分支结点：度不为0的结点）；树的度：树内各结点的度的最大值；关于深度和高度（深度：自根而下，高度：自叶而上）结点 n 的深度：从根结点到结点n的唯一路径长；结点n的高度：从结点n到叶结点的最长路径长； 树的高度和深度（一些教材的说法不一，具体可以参考树的深度和高度解释）树的高度：有些教材：树的高度定义就是深度；有些教材：树的高度则是看一共有几层（严蔚敏版根结点为第一层）；树的深度：树从根结点开始往下数，叶子结点所在的最大层数称为树的深度。有序树：树中任意节点的 子结点之间有顺序关系，这种树称为有序树；无序树：树中任意节点的 子结点之间没有顺序关系，这种树称为无序树,也称为自由树。 eg：下面两棵树表示同一棵树则为无序树，表示两棵树则为有序树：二叉树是有序树。二叉树得度可能为0、1、2（不一定是度为 2 的树）。 特点：
二叉树的第 i 层 14上至多有 2 i − 1 2^{ i-1} 2i−1 个结点。深度为 k 的二叉树至多有 2 k − 1 2^k-1 2k−1 个结点。深度为 k，有 2 k − 1 2^k-1 2k−1 个结点；（即：除了叶结点外每一个结点都有左右子结点的二叉树）
给满二叉树的结点编号，从上至下，从左至右， n 个结点的完全二叉树中结点在对应满二叉树中的编号正好是从 1 到 n。（即：若二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，则为完全二叉树。）
一些计算公式： 叶子结点（度为0的结点）n0，度为 2 的结点为 n2，则 n0 = n2+1。 推导： n = n0 + n1 + n2 n = 2 * n2 + n1 + 1 两式相减可得：n0 = n2 + 1
n 个结点的完全二叉树深度为 ⌊ l o g n ⌋ − 1 \lfloor log^n\rfloor -1 ⌊logn⌋−1 n 个结点的完全二叉树，结点按层次编号：
i 的双亲是 ⌊ i / 2 ⌋ \lfloor i/2 \rfloor ⌊i/2⌋，如果 i = 1 时为根（无双亲）i 的左孩子是 2i，如果 2i>n，则无左孩子i 的右孩子是 2i + 1，如果 2i + 1>n 则无右孩子用数组、编号 i 的结点存放在[i-1]处。适合于存储完全二叉树。
左图为二叉链表，右图为三叉链表.二叉链表表示树比三叉链表所需空间少，然而想要达到访问双亲的目的，就需要对树进行遍历。三叉链表比二叉链表多了parent 指针用来记录双亲结点，可以很快达到访问双亲的目的。
二叉树的遍历请看我的另一篇博客：python实现二叉树遍历（前、中、后序）
什么是线索？ n 个结点的二叉链表中有 n+1 个空指针，可以利用其指向中序遍历的前驱或后继结点，叫线索。
ltag 和 rtag 为附加标志，区分是子树（为 0）还是线索（为 1）。
lchild 有左子树，则指向左子树，标志 ltag == 0； 没有左子树，可作为前驱线索，标志 ltag == 1。rchild 有右子树，则指向右子树，标志 rtag == 0； 没有右子树，可作为后继线索，标志 rtag == 1。如下图所示为二叉链表： 中序遍历为：H D I B J E A F C G 右孩子为空指针时，全部指向中序遍历的后继结点（如 I 指向 B、E 指向 A） 左孩子指针为空时指向中序遍历的前驱结点： （中序遍历为：H D I B J E A F C G） 最后结果如图（实现为左孩子指针，虚线为右孩子指针）： （中序遍历为：H D I B J E A F C G）
关于哈夫曼树可以看我的另一篇博客：二叉树之哈夫曼树
例：
森林中第 1 棵树的根作为对应的二叉树的根；其他的树看作第 1 棵树的兄弟。 例：
