什么是树？
1、基本概念
二叉树是我们生活中最常见的非线性结构。最常见的应用就是我们经常使用的文件分类。如图：
在c盘中存在着很多文件和文件夹，文件夹又可以细分为其他的文件夹和文件。对于图中的c盘，就相当于树的跟，而其他的文件夹就相当于树枝，然后树枝上有分出许多其他的树枝，以此组成一个树形结构。相比于顺序表，链表这样的结构，树形结构能够更好的分类，一般拥有更高的访问效率。
存在树，那么也同样存在非树。如果在存在一个节点指向同一层的结点，就称为非树。如图：
2、结构特征
类似于如链表的头结点，树形结构的根节点是读取树，操作树的最基本入口。
树
树中的A结点和链表的head结点都起着不可替代的作用。
3、基本特性
以下图为例子：
- 结点的度：每一个节点含有子树的个数，例如图中的A结点，存在BCDE这四棵子树，其中B存在FGH这三棵子树。所以A节点的度为4，B结点的度为3。
- 树的度：一棵树的所有的结点的度的集合中，最大值为这整棵树的度（树的结点中的最大的度）
- 叶子结点（终端结点）：度为0的结点。例如图中的M结点、结点等。
- 父结点（双亲结点）：一个结点的上一级结点，成为这个结点的父结点，例如上图中，A是B的父结点。
- 孩子结点（子结点）：和父亲结点类似，一个结点如果含有其下一级，那么这个结点的下一级就称为这个结点的孩子结点。
- 根节点：也就是整棵树的起点，如上图中的A结点。
- 结点的层次：如果根节点的层次为1，那么根节点的子节点BCDE的层次就为2，以此类推。
- 树的深度（高度）：树的结点的最大层次。
- 非终端结点（分支结点）：度不为0的结点。
- 祖先：从根到该结点所经分支上的所有结点。例如，A结点是所有结点的祖先。
- 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
- 森林：由多棵不相交的树组成的系统，称为森林。
4、代码结构
class TreeNode { int val; TreeNode firstChild; TreeNode secondChild; // .......TreeNode fifthchild; // ....... }
在树的三链表示中还存在一个指向父亲结点的指针变量。
特殊的树-二叉树
从上面的介绍不难看出， 二叉树是结点的度的最大值为2的树。代码结构为：
1. class TreeNode { 2. int val; 3. TreeNode leftChild; 4. TreeNode rightChild; 5. }
如果leftChild和rightChild有一个不为空，则这个结点为分支节点。如果leftChild和rightChild都为空，则这个结点为叶结点。val用来表示存放的数据。如图：
- 满二叉树
定义：一棵二叉树，它的每一层的节点数都达到最大值，则称这个二叉树为满二叉树，如果一棵满二叉树层数为k（根节点的层数为1），那么它一共拥有 
个结点，例如：
满二叉树
图中的层数3，节点数为 
。
- 完全二叉树
定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
例如：
完全二叉树
3、二叉树的性质
- 除了根节点外，每一个节点都有都有一条边和其父结点相连，若一个有n个结点，那么就一共有n-1条边。
- 若规定根节点的层数为1，则一棵二叉树的第n层最多含有
（n≥1）个结点。 - 假设一棵树有n个结点，设叶结点（度为1的结点）个数为 n0, 度为2的非叶结点个数为 n2，由第一个性质可知，总的节点数为 == 边的个数+ 1。度为2的结点可以衍生出两条边，度为1 的结点可以衍生出1条边，所以：
n0 + n1 + n2 = 2*n2 + 1*n1 + 0*n0 + 1
n0 = n2 + 1
即： 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
- 具有n个结点的完全二叉树的深度k为
上取整
二叉树的基本操作
1、二叉树结构实现
public class BinaryTree {0 // 二叉树结点的定义 public static class BTNode { int val; BTNode leftChild; BTNode rightChild; public BTNode(int val) { this.val = val; } } // 简单创建一棵树，方便后面遍历 public void test() { BTNode A = new BTNode(1); BTNode B = new BTNode(2); BTNode C = new BTNode(4); BTNode D = new BTNode(3); BTNode E = new BTNode(5); BTNode F = new BTNode(6); A.leftChild = B; A.rightChild = C; B.leftChild = D; C.leftChild = E; C.rightChild = F; } }
实现并创建一棵简单的二叉树
2、前中后序遍历
所谓二叉树遍历，就是顺着某一种固定的路线，来依次对二叉树的每一个节点的数据进行访问，以此打印或者获取二叉树的存储内容。
如何访问？ 对于每一棵树，都有一个根节点作为入口点，然后每一个结点，都存放有对应的左孩子和有孩子的引用变量，以此来访问他们，然后左孩子和有孩子中又存放着其对应的左孩子和右孩子，依次形成递归。结束访问，只需要访问到其孩子的引用为空（null）即可。
根据根节点 的访问先后次序，可以分为以下遍历方式：
NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。
前序遍历：1 2 3 4 5 6
中序遍历：3 2 1 5 4 6
后序遍历：3 2 5 6 4 1
3、层序遍历
层序遍历：按照每一层的层次关系进行遍历，而不是通过递归的父子关系。如上图，
层次遍历的结果为：1 2 4 3 5 6
遍历思路：创建一个队列，首先遍历根节点，将根节点放入队列中，然后出列并输出打印出列结点，随后将出列结点的左孩子（leftChild）和右孩子（rightChild）放入队列中，随后的每一次遍历，都将当前打印的结点的左孩子和右孩子放入队列中，直到队列为空。
因为356结点的左孩子右孩子都为null，也就是没有左孩子和右孩子，那么就直接出队列然后输出打印
public void levelOrder(BTNode root) { Queue<BTNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { BTNode out = queue.poll(); if (out.leftChild != null) { queue.offer(out.leftChild); } if (out.rightChild != null) { queue.offer(out.rightChild); } System.out.print(out.val + " "); } }
注意此处，传入的为二叉树的根节点。
输出结果为：
4、获取树中结点个数size（）
public int size(BTNode root) { if (root == null) { return 0; } return size(root.leftChild) + size(root.rightChild) + 1; }
return 中的1代表当前的结点，然后去访问左子树，和右子树的结点个数。如果某个结点为null，则直接返回0.
5、获取叶子节点的个数
叶子结点及度为0的结点，也就是leftChild和rightChild引用为null的结点。
计数法，可以使用两个函数来实现：
private int count = 0; public int leafCount1(BTNode root) { count = 0; functionLeafCount(root); return count; } public void functionLeafCount(BTNode root) { if (root == null) { return; } if (root.leftChild == null && root.rightChild == null) { count++; return; } functionLeafCount(root.leftChild); functionLeafCount(root.rightChild); }
函数递归：
public int leafCount2(BTNode root) { if (root == null) { return 0; } if (root.leftChild == null && root.rightChild == null) { return 1; } return leafCount1(root.leftChild) + leafCount2(root.rightChild); }
6、获取第k层的结点个数
设根节点的层数为1
public int getLevelCount(BTNode root,int k) { if (root == null) { return 0; } if (k == 1) { return 1; } return getLevelCount(root.leftChild, k - 1) + getLevelCount(root.rightChild, k - 1); }
传入参数k，然后递归每一层将 k - 1，当k == 1 的时候，就是我们所需要的层数
7、获取二叉树高度
二叉树的高度可以简单化为 ：
左子树的高度 + 右子树的高度 + 1
public int getheight(BTNode root) { if (root == null) { return 0; } int leftHeight = getheight(root.leftChild); int rightHeight = getheight(root.rightChild); return Math.max(leftHeight, rightHeight) + 1; }
8、检测值为value的元素是否存在
public boolean exitValueOf(BTNode root, int val) { if (root == null) { return false; } if (root.val == val) { return true; } return exitValueOf(root.leftChild, val) || exitValueOf(root.rightChild, val); }
递归思路，首先判断入口点的值是否等于val，然后再去判断左子树，和右子树是否存在val。
如果root为空，则说明不含val的值的结点，返回false，如果找到了就返回true。
9、判断一棵树是不是完全二叉树
完全二叉树定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
public boolean isCompleteTree(BTNode root) { if (root == null ) { return true; } Queue<BTNode> queue = new LinkedList<>(); boolean startLeaf = false; queue.offer(root); while(!queue.isEmpty()) { BTNode cur = queue.poll(); BTNode left = cur.leftChild; BTNode right = cur.rightChild; if (left == null && right != null) { return false; } if (left == null || right == null) { startLeaf = true; } if (startLeaf && (left != null || right != null)) { return false; } if (left != null) { queue.offer(left); } if (right != null) { queue.offer(right); } } return true; }
