树结构是以分支关系定义的一种层次结构，应用树结构组织起来的数据，逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。

树Tree是由n个节点组成的有限集合。在任意一颗非空树中：

每个圆圈表示树的一个节点，其中节点A被称为树的根节点。

每一棵子树本身也是树。

二叉树是一种特殊的树结构，前面所说的树的特性及术语同样适用于二叉树。

二叉树Binary Tree或者为空，或者由一个根节点加上根节点的左子树和右子树组成。

要求左子树和右子树互不相交，且同为二叉树。

显然，这个定义式是递归形式的。

二叉树的每个节点至多有两个孩子节点，其中左边的孩子节点被称为左孩子，右边的孩子节点被称为右孩子。

如果二叉树内的任意节点都是叶子节点或有两棵树，同时叶子节点都位于二叉树的底层，则其被称为满二叉树。 若二叉树最多只有最下面两层节点的度小于2，并且底层节点（叶子节点）依次排列在该层最左边的位置上，则其被称为完全二叉树。

如图：

二叉树非常特殊，需要我们掌握它的一些性质：

二叉树一般采用多重链表的形式存储，直观地讲就是将二叉树的各个节点用链表节点的形式连接在一起。 每个节点都包含三个域：

二叉树的节点定义如下：

对于一棵二叉树而言，只要得到了它的根节点指针（引用），就可以通过链表结构访问到二叉树中的每一个节点。 所以在定义二叉树类时，通常只需要保存二叉树的根节点，而不需要记录二叉树中每一个节点的信息。

二叉树的遍历Traversing Binary Tree就是通过某种方法将二叉树中的每个节点都访问一次，并且只访问一次。 在实际应用中，经常需要按照一定的顺序逐一访问二叉树中的节点，并对其中的某些节点进行处理。 二叉树的遍历操作是二叉树应用的基础。 二叉树的队列分为两种：

基于深度优先搜索的遍历 访问根节点的函数visit()可依据实际情况自行定义，它可以是读取节点中数据的操作，也可以是其他复杂的操作。

基于深度优先搜索的遍历算法一般有三种：先序遍历DLR、中序遍历LDR和后序遍历LRD。 其中D表示根节点，L表示左子树，R表示右子树。 因为二叉树本身就是递归结构，所以这3种遍历算法也都是以递归形式定义的。 先序遍历DLR：

中序遍历LDR：

后序遍历LRD：

按层次遍历

按层次遍历二叉树是一种基于广度优先搜索思想的二叉树遍历算法。按层次遍历二叉树针对二叉树的每一层进行。 若二叉树非空，则先访问二叉树的第1层节点，再依次访问第2层、第3层节点，直到遍历完二叉树底层节点。 对二叉树中每一层节点的访问都按照从左到右的顺序进行。 在遍历时，需要一个队列作为辅助工具，具体步骤如下：

方便起见，该队列是用Java容器类LinkedList的泛型实现，这样可以指定队列中的每个数据元素都是BinaryTreeNode类型的。当然也可以使用之前创建的MyQueue类实现这个辅助队列，但在使用之前需要对Myqueue类加以改造，使其每个队列节点的数据域都是BinaryTreeNode类型的。

前面介绍了二叉树的遍历方法。但这需要存在一棵二叉树为基础。 最常见的创建二叉树的方式就是利用二叉树遍历的思想，在遍历过程中生成二叉树的节点，进而建立起整棵二叉树。

函数CreateBiTree()可以按照先序序列创建一棵二叉树。该函数的参数是一个LinkedList类型的对象nodeList。保存了每个节点的元素，用来初始化二叉树节点。 这些元素在nodeList中以先序序列的方式排列并指定了该二叉树双亲结点与孩子节点之间的关系。 函数CreateBiTree()先从nodeList中取出第一个元素，如果该元素不为null，则创建一个BinaryTreeNode类型的节点node，并将取出的元素作为node中的数据元素。 再递归地创建以node节点为根节点的二叉树的左子树和右子树。如果从**nodelist**中取出的第1个元素为**null**，则说明本层递归调用中要创建的二叉树（或二叉树的某棵子树）为空，直接返回**null**即可。 在上面的代码中，将创建二叉树的函数CreateBiTree()以及二叉树遍历函数PreOrderTraverse()、InOrderTraverse()、PostOrderTraverse()都进行了封装，使得它们对外提供的接口可以不以二叉树的根节点作为返回值或参数。这样二叉树根节点作为私有成员被隐藏起来，代码结构也更加符合面向对象的程序设计思想。

二叉排序树也称二叉查找树，是一种特殊形式的二叉树：

在二叉排序树中查找元素时，首先将给定的关键字与根节点的关键字比较，若相等则查找成功，否则将根据给定的关键字与根节点的关键字之间的大小关系，在左子树或右子树中继续查找。

在二叉树中搜索key=11，搜索步骤如下：

上面的代码中，并没有使用递归，而是通过不断修正while循环，来获取符合条件的最低公共祖先。while中第一个if的判断条件为curNode.data > value1 && curNode.data > value2 && curNode.leftChild.data != value1 && curNode.leftChild.data != value2

对于第一点，也就是前两句if条件。执行的语句是修改curNode指向的对象，也就是修改while循环中下一轮循环的方向。如果判断节点介于value1和value2之间，则直接返回。 对于第二点，也就是后两句if条件。最低公共祖先一定是value1和value2节点的祖先。当判断节点为其中一个节点的双亲节点时，可以直接返回该节点。

该算法适用的前提是value1和value2在二叉排序树中真实存在。 该算法的核心思想是在二叉排序树中寻找value1和value2之间的值，如果value1或value2在二叉排序树中不存在，那么得到的结果是没有意义的。 更加完善的做法是预先判断value1和value2是否在二叉排序树中。