之前就说过我们的数据结构分为两种，分别是线性结构和非线性结构，我们今天要学的第一种线性结构就是树型结构。

1. 树型结构

树型结构并非我们熟悉的重点，所以在这里只做了解。

概念：

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

1. 有一个特殊的结点，称为根结点，根结点没有前驱结点

2. 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <=m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

3. 树是递归定义的

比如生活中见到的树：

数据结构中的 “ 树 ” 和现实中的树有点区别，数据结构中的 “ 树 ” 是倒着树，我们自己动手画一棵：

我们来看一看非树的情况：

我们可以得到如下结论：

1. 子树是不相交的

2.除了根结点外，每个结点有且仅有一个父亲结点

3.一颗N个结点的树，有N - 1 个边（这个后面还会用到）

书上有的很多关于树的概念这里就不介绍了，可以直接看书。例如：

结点的度：一个结点含有子树的个数称为该结点的度；

树的度：一棵树中，所有结点度的最大值称为树的度；

叶子结点或终端结点：度为0的结点称为叶结点；

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；

等等。

1.2 树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

代码示例：

class Node {
    int value; // 树中存储的数据
    Node firstChild; // 第一个孩子引用
    Node nextBrother; // 下一个兄弟引用
}

图示：

1.3 树的应用

比如我们电脑文件管理就是一个树结构的：

2. 二叉树

我们上面的文件管理有多个子节点，我们统称为多叉树，当树的度不大于2时，我们称之为二叉树，例如：

二叉树不仅仅是考试的重难点也是未来面试的一个重难点。

2.1 概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空

2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

从上图可以看出：

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2 特殊的二叉树

1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

关于二叉树的更多性质可以查看下图

好了，了解以上知识，就算碰到二叉树的门槛了，关于二叉树的具体实现，还得接着往下看

3. 二叉树的实现

上代码：

class TreeNode {//结点的实现
        int val;//data域
        public TreeNode left;//左子节点的引用
        public TreeNode right;//右子节点的引用
        public TreeNode(int val) {
            this.val = val;
        }
}

每个结点都存在三个域，数据域和左右子节点，其叶子节点也存在左右子节点，只不过其左右子节点均为null，所以左右子节点均为null的也叫做叶子节点。

我们再来看看二叉树的概念：

1. 空树

2. 非空：根节点，根节点的左子树、根节点的右子树组成的

4. 二叉树的基本操作

在我们真正去实现二叉树的时候一般都是使用LinkedList去实现，我们模拟也是用LinkedList去模拟的。

我们的模拟主要有如下几个

// 获取树中节点的个数

int size(Node root);

// 获取叶子节点的个数

int getLeafNodeCount(Node root);

// 获取第K层节点的个数

int getKLevelNodeCount(Node root,int k);

// 获取二叉树的高度

int getHeight(Node root);

// 检测值为value的元素是否存在

Node find(Node root, int val);

//层序遍历

void levelOrder(Node root);

// 判断一棵树是不是完全二叉树

boolean isCompleteTree(Node root);

还有最最基础的前中后序遍历。

我们先来第一个前序遍历。

1. 前序遍历

思路如下：

我们简易的口诀就是根、左、右；如图：

我们用数字来表示路径，从最开始的根走，找到第二层的根并且把其根全部走完，再走左，把左全部走完最后走右，每一根左右下面都还有一层根左右。

动图表示：

芝士代码：

 // 前序遍历
    void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    };

2. 中序遍历

思路：

类似于前序遍历，但是我们的路径发生改变，路径为左、根、右。

每一层的左、根、右都还有左、根、右。

动图表示：

芝士代码：

 // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+ " ");
        inOrder(root.right);
    };

3. 后序遍历

思路：

一样类似于前序遍历，但是我们的路径发生改变，路径为左、右、根。

每一层的左、右、根都还有左、右、根。

动图表示：

芝士代码：

 // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+ " ");
    };

当然拉我们做二叉树问题的大部分思路都是递归去解决，也有问题可以用其他方法解决，余下的二叉树模拟方法，包括一些oj题还有层序遍历我放在下一章来讲解。