一、树的介绍
树是一种非线性的数据结构，是以分支关系定义的层次结构，比如人类社会中的族谱、及各种机制、组织的关系都可以用树形象的表示。重点学习二叉树的存储和相关操作，还要讨论树、森林、二叉树的转换关系。
二、树的定义和基本术语
树：是n个结点的有限集，当0==n时称为空树，我们不讨论空树。
根结点：树的最顶层的结点，一棵树有且仅有一个。
子树：一棵树除根结点外，剩余的是若干个互不相交的有限集，每一个集合本身又是棵树，称称为根的子树。
结点的度：树的结点包含一个数据元素及若干个指向其子树的分支，结点拥有的子树称为结点的度。
叶子结点：结构的度为0，被称为叶子结点或终端结点。
分支结点：结构的度不为0，被称为分支结点或非终端结点，也被称为内部结点。
树的度：是指树内各结点度的最大值。
密度：指的是一棵树中，所有结点的总数。
孩子、双亲、兄弟、祖先、子孙：结点的子树称为该结点的孩子，而该结点是孩子结点的双亲，拥有共同双亲的结点互为兄弟，从双亲结点往上，直到根结点都称为孩子结点的祖先结点，以某结点为根的子树中的任一结点都被称为该结点的子孙。
层数、深度、高度：从根结点开始定义，根为第一层、根的孩子为第二层依次类推，树中结点的最大层数被称为树的深度或高度，双亲在同一层的结点互为堂兄弟。
有序树和无序树：将树中结点的各子树看成从左到右是有序次，即不能交换（顺序有意义，表达一些含义），则称该树为有序树，否则称为无序树。
森林：若干个棵互不相交的树的集合称为森林，对树中每个结点而言，其子树集合就是森林。
就逻辑结构而言，任何一棵树都是一个二元组 Tree = (root,F)，其中root是数据元素，称做树的根结点，F是若干棵子树构成的森林。
三、二叉树的定义和性质
二叉树：
是一种特殊的树型结构，也就是每个结点最多有两棵子树（二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，顺序不能颠倒。
满二叉树：
若一棵树的层数为k，它总结点数是2^k-1，则这棵树就是满二叉树。
完全二叉树：
若一棵树的层数为k，它前k-1层的总结点数是2^(k-1)-1，第k层的结点按照从左往右的顺序排列，则这棵树就是完全二叉树。
二叉树的性质：
性质1：
在二叉树的第i层上，最多有2^(i-1)个结点。
性质2：
深夜为k的二叉树，最多有2^k-1个节点。
性质3：
对于任何一棵二叉树，如果叶子结点的数量为n0，度为2结点的数量为n2，则n0=n2+1;
性质4：
具有n个结点的完全二叉树的高度为(log2n)+1。
性质5：
有一个n个结点的完全二叉树，结点按照从上到下从左到右的顺序排序为1~n。
1、i > 1时，i/2就是它的双亲结点。
2、i*2是i的左子树，当i*2>n时，则i没有左子树。
3、2*i+1是i的右子树，2*i+1>n时，则i没有右子树。
三、二叉树的遍历
前序遍历：
1、判断二叉树是否为空，若二叉树为空，则不操作。
2、访问根结点
3、前序遍历左子树
4、前序遍历右子树
中序遍历：
1、判断二叉树是否为空，若二叉树为空，则不操作。
2、中序遍历左子树
3、访问根结点
4、中序遍历右子树
后序遍历：
1、判断二叉树是否为空，若二叉树为空，则不操作。
2、后序遍历左子树
3、后序遍历右子树
4、访问根结点
层序遍历：
按照从上到下、从左到右的顺序遍历二叉树，需要与队列结构配合，普通的顺序队列即可，不需要链式队列或循环队列。
