一、树型结构
1.1 概念（了解）
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
1.有一个特殊的结点，称为根结点，根结点没有前驱结点
2.除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <=m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
3.树是递归定义的
注意：属性结构中，子树之间不能有交集，否则就不是树形结购
1.2 概念（重要）
节点的度 ：一个节点含有字树的个数成为该节点的度；如上图：A的度为6
树的度：一棵树中，所有节点度的最大值成为树的度；如上图：树的度为6
叶子节点或终端节点：度为0的节点称为叶节点；如上图：B、C、I、P...等节点为叶节点
双亲节点或父节点：若一个节点含有子节点，则这个节点成为其子节点的父节点；如上图A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点成为该节点的子节点
根节点：一棵树中，没有双亲节点的节点；如上图：A
节点的层次：从根开始定义起，根的子结点为第二层，以此类推
树的高度或深度：树中节点的最大层次：如上图：树的高度为4
以下概念作为了解
非终端节点或分支节点：度不为0的节点；如上图：D、E、F...等节点的分支节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C、D是兄弟节点
堂兄弟节点：双亲在同一层的节点互为堂兄弟节点；如上图：H、I互为堂兄弟节点
节点的祖先：从根到该结点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m（m>=0）棵互不相交的树组成的集合成为森林
1.3 树的表示形式
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等。其中最常用的是孩子兄弟表示法。
class Node{ int value; //树中存储的数据 Node firstChild; //第一个孩子的引用 Node nextBrother; //下一个兄弟的引用 }
1.4 树的应用
文件系统管理（目录和文件）
二、二叉树
2.1 概念
一棵二叉树是结点的一个有限集合，该集合：
1.或者为空
2.或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成
从上图可以看出：
1.二叉树不存在度大于2的结点
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注：对于任意的二叉树都是由一下几种情况复合而成的：
2.2 两种特殊的二叉树
1.满二叉树：一棵二叉树，如果每层的节点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为n，且结点数是2ⁿ - 1，则它就是满二叉树。
2.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个完全结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0到n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
2.3 二叉树的性质
1. 若规定根节点的层数为1，则一棵非空二叉树的第n层上多有2ⁿ﹣¹（i>0）个结点
2.若规定只有根节点的二叉树的深度为1，则深度为n的二叉树的最大结点数是2ⁿ-1（k>0）
3.对任何一棵二叉树，如果其叶节点个数为n0,度为2的非叶节点个数为n2,则有n0=n2+1
4.具有n个结点的完全二叉树，如果按照从上至下从左往右的顺序对所有节点从0开始编号，则对于序号为i的节点有：
1.若i>0,双亲序号:(i-1)/2; 若i=0,i为根结点编号，无双亲节点
2.若2i+1<n，左孩子序号：2i+1，否则无左孩子
3.若2i+2<n，右孩子序号：2i+2，否则无右孩子
