对于什么是树，以及树的概念，我们在这里不做赘述了，大家在数据结构的课程里都应该学过，这里我推荐mooc慕课中浙江大学陈越老师的《数据结构》课程，非常便于理解数据结构的知识，而且对于算法的讲解很透彻。

今天我们主要讲的是如何设计一个二叉树类，大家都知道Java中是没有结点以及指针类型的，实现起来有时会让我们摸不到头脑，这一讲也是为了以后深入了解二叉树相关算法和十分重要的二叉树的遍历作为提前的知识储备，比较简单，很容易理解：）

二叉树的抽象数据类型

首先我们要了解二叉树基本实现所需要的抽象数据类型，从两个方面介绍

①.数据集合：为二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。

②.操作集合：

（1）双亲结点parent()：

（2）左孩子结点leftChild()

（3）右孩子结点rightSibling()

（4）左插入结点insertLeftNode(x)

（5）右插入结点insertRightNode(x)：

（6）左删除子树deleteLeftTree()

（7）右删除子树deleteRightTree()

（8）遍历二叉树traverse(vs)---最重要也就是这个啦

二叉树的存储结构

1.顺序存储结构

（a）为非完全二叉树，既然我们要存储（a），首先我们要把它变成完全二叉树，也就是将空余部分补上，因为二叉树本身就是有顺序的，树根为0，所以A为0 B为1 C为2 我们顺序把结点存入数组，空出来的地方就为空

2.链式存储结构

二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。

二叉链存储结构的每个结点包含三个域 。

data：为数据域  leftChild：为左孩子的指针域  rightChild：为右孩子的指针域

举个小栗子~

（a）不带头结点的二叉树，可以看到，没有指针域的结点，左边或者右边为空

（b）带头结点的二叉树，头结点只负责指向我们的树根结点

设计二叉树

二叉树由三个部分组成：结点、左孩子、右孩子，因此我们要设计的二叉树类由两个部分组成：二叉树类和二叉树结点类。

二叉树结点类

首先我们声明三个私有的成员变量：数据元素（即结点的值）、左孩子和右孩子，生成get/set方法，为了方便初始化和传值，我们分别声明一个无参的构造方法和有参的构造方法。具体代码如下。

二叉树类

当我们有了二叉树结点类，我们就可以创建一个二叉树了，我们把结点的数据元素传给我们的二叉树结点类，并且区分好左右，这样我们的二叉树就建立好了。

总结

理解好二叉树的存储结构至关重要，也是为了我们接下来学习遍历二叉树而大号基础。

下一讲，我们就开始研究如何遍历二叉树的算法！直奔主题！

PS：有什么问题或者不解的地方可以评论，我都会一一就行回复的，如果有错误或者言语不明的地方，还请大神多多指点！