前序遍历序列：A B D E H I F C G 后序遍历序列：D H I E F B G C A 层序遍历序列：A B C D E F G H I
小问题： （1）实现树的存储结构，关键是什么? 如何表示树中结点之间的逻辑关系。 （2）树中结点之间的逻辑关系是什么? 一对多的关系； 存储结构的关键：如何表示结点的双亲和孩子；
顺序存储： 本质上是静态指针 双亲表示法 双亲、孩子表示法 链式存储： 多重链表示法 孩子链表表示法 孩子兄弟表示法
二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 特点： ⑴ 每个结点最多有两棵子树； ⑵ 二叉树是有序的，其次序不能任意颠倒。 注意：二叉树和树是两种树结构。！！！
特殊二叉树： 1 .所有结点都只有左子树的二叉树称为左斜树； 2 .所有结点都只有右子树的二叉树称为右斜树； 3.左斜树和右斜树统称为斜树。
在斜树中，每一层只有一个结点；斜树的结点个数与其深度相同。4.满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 1.叶子只能出现在最下一层； 2.只有度为0和度为2的结点。 满二叉树在同样深度的二叉树中结点个数最多; 满二叉树在同样深度的二叉树中叶子结点个数最多;
5.完全二叉树： 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。 在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。
叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。深度为k的完全二叉树在k-1层上一定是满二叉树。