一.什么是树

都说艺术来源于生活，技术同样也是来源于生活。什么是树，它是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

1.树的特点

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

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

树是递归定义的。

这种数据结构就像是一棵倒立的树，但是请注意，子树之间不能有交集，否则就不是属性结构。

1.类似这种，节点之间有相互连接的就不能称为树形结构。

2.除了根节点外，每个节点有且只有一个父亲节点。

3.一棵树有N个节点，那么他就有N-1条边。

2.有关树形结构的概念

如图，是一个完全二叉树。

1.结点的度：指的是一个节点含有子树的个数（就是一个节点有节点孩子节点），就像A节点的度为2

2.树的度：一棵树中，所有结点度的最大值称为树的度。如图，树的度为2.

3.叶子结点：一棵树的最后一个节点，没有孩子的节点，如图中的 D,G,H,K.

4.双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点 如图A是B的父亲节点。

5.孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

6.根结点：一棵树中，没有双亲结点的结点；如上图：A

7.结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推.

8.树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

3.树的表现形式

4.应用

文件系统管理（目录和文件）

二.二叉树（主要）

2.1 概念

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

1. 或者为空

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

从上图可以看出：
3. 二叉树不存在度大于2的结点
4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

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

2.2两种特殊的二叉树

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

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

2.3二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2的i次方-1 (i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2的k次方-1 (k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

4. 具有n个结点的完全二叉树的深度k为log以2为底的(n+1) 上取整

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
   若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
   若2i+1<n，左孩子序号：2i+1，否则无左孩子
   若2i+2<n，右孩子序号：2i+2，否则无右孩子

2.4二叉树的性质

在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。

LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。

LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点。

方法的实现：

2.5二叉树的基本操作

1.获取树中节点个数

 int size(TreeNode root){if (root==null){return 0;}return size(root.left)+size(root.right)+1;}

代码思路：用子问题解决。每一棵树的节点分为 左子树节点+右子树节点+根节点（1）.
转换成代码如上面代码块所示。也可以定义一个计数器来计算。

计数器代码实现：

 public int nodeSize=0;int size2(TreeNode root){if (root==null){return 0;}nodeSize++;size2(root.left);size2(root.right);return nodeSize;}

2.获取叶子节点的个数

代码展示：

int getLeafNodeCount(TreeNode root){if (root==null){return 0;}if (root.left==null&&root.right==null){return 1;}return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);}

代码思路：

3.检查两棵树是否相同

public boolean isSameTree(TreeNode p, TreeNode q) {//1.首先判断某一个节点是否为空if(p!=null&&q==null||p==null&&q!=null){return false;}//2.判断两个都为空的话返回trueif(p==null&&q==null){return true;}//3.如果两个不为空的情况下我们在判断值是否相同if(q.val!=p.val){return false;}//4.因为‘&&’，最终返回的只要是有false，就是falsereturn isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}

代码思路：

4.判断一棵树是不是另一棵树的子树

 public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if (root==null||subRoot==null){return false;}//1.判断是不是根节点if (isSameTree(root,subRoot)){return true;}//2.判断是不是他的左子树if (isSubtree(root.left,subRoot)){return true;}if (isSubtree(root.right,subRoot)){return true;}return false;}public boolean isSameTree(TreeNode p, TreeNode q) {//首先判断两棵树的结构是否为空if((p!=null&&q==null)||(p==null&&q!=null)){return false;}//如果两棵树都为空if(p==null&&q==null){return true;}//判断值是否一样if(p.val!=q.val){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
}

这里我们用到上一个题目判断是否为相同的树这道题，基本的代码思路就是先让根节点和subRoot进行判断。然后再判断是不是他的左子树或者是他的右子树。如果都没有最终返回false。

5.翻转二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {if(root==null){return null;}if(root.left==null&&root.right==null){return root;}TreeNode tmp=root.left;root.left=root.right;root.right=tmp;invertTree(root.left);invertTree(root.right);return root;}
}

代码思路：

6.二叉树的构建及遍历

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

import java.util.Scanner;
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}}// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static int i=0;public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();TreeNode root = createTree(str);inorder(root);}}public static TreeNode createTree(String str){TreeNode root=null;if(str.charAt(i)!='#'){root=new TreeNode(str.charAt(i));i++;root.left=createTree(str);root.right=createTree(str);}else{i++;}return root;}public static void inorder(TreeNode root){if(root == null) {return;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}
}

代码思路：

创建二叉树的时候我们要切记在递归过程中递的时候只是创建，归的时候才将他们联系起来。