树的概念
树是一种非线性的数据结构，它是由n (n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点:
有一个特殊的节点，称为根节点，根节点没有前驱节点
除根节点外，其余节点被分成M(M>0)个互不相交的集合T1、T2、.....Tm，其中每一个集合Ti(1 <= i<=m)又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继
树是递归定义的
子树
子树是不相交的
除了根节点没有前驱节点，其余的每个节点都有且只有一个父节点
假设树结构中边的个数为x，树节点的个数为n，他们之间的关系是x=n-1
节点的"度"：该节点包含的子树个数
-
树的"度"：树中最大节点的度
image.png 叶子节点：就是度为0的节点（比如上图中的M,J,K节点）
非叶子节点：就是度不为0的节点，该节点存在子树
根节点：没有前驱节点的节点，一个数只有一个根节点（比如上图的D节点）
节点的层次：从根节点开始计算，对于上图来说，D根节点为第一层，I,J,K节点为第二层，M节点就是第三层
树的高度：当前树中节点层次最大的即为树的高度（上图树的高度就是3）
二叉树概念
树中节点最大的度，为2的数就叫做二叉树，也就是数的度为2的树
在二叉树中，一个节点最多有两颗子树，二叉树节点的度<=2
-
二叉树的有左右之分，且子树的次序不能颠倒，因此二叉树是有序树
image.png
二叉树性质
在深度为K的二叉树中，最多存在2^k -1个节点
在第K层中，该层最多有2^(k-1)个节点
假设树结构中边的个数为x，树节点的个数为n，他们之间的关系是x=n-1，通过这个可以推出，度为2的节点（N2）和度为0的节点（N0）之间的关系：
N0=N2+1
满二叉树和完全二叉树
- 满二叉树:一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k -1，则它就是满二叉树。
- 完全二叉树:完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。（从视觉上来看，完全二叉树就是满二叉树缺少了右下角）
二叉树的创建
通过输入字符串序列如
8 7 5 1 -1 -1 -1 4 -1 -1 6 3 -1 -1 2 -1 -1
来创建二叉树
1、先创建两个类分别表示结点和树
/**
* 1、设计一个类表示二叉树结点
*/
class Node{
private int value;
private Node left;
private Node right;
public Node(){
}
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
/**
* 2、设计一个类表示二叉树
*/
class Tree{
//树的深度
private int index;
private int leafVal;
private Node head;
public Node getHead() {
return head;
}
public int getLeafVal() {
return leafVal;
}
public void setLeafVal(int leafVal) {
this.leafVal = leafVal;
}
public void setHead(Node head) {
this.head = head;
}
/**
* 打印
*/
private void Print(int content){
System.out.print(" "+content+" ");
}
}
2、创建二叉树
class Tree{
/**
* 二叉树的创建
*/
public void Create(String nodeStr){
if(nodeStr == null || nodeStr.length() == 0)
return;
String[] strings = nodeStr.split(" ");
int[] nums = new int[strings.length];
for (int i = 0;i<nums.length;i++){
int num = Integer.parseInt(strings[i].trim());
nums[i] = num;
}
index = 0;
head = CreateBinaryTree(nums);
}
}
3、二叉树的遍历
对于二叉树来说，一共有四种遍历方式
深度优先遍历（dfs）：前序遍历，中序遍历，后序遍历
广度优先遍历（bfs）: 层序遍历
前序遍历：先访问根节点，然后递归访问左子树，在递归访问右子树（根左右，就是第一次访问该节点就打印,并且第一个节点一定是根节点）
/**
* 先序遍历：从二叉树的根结点出发，当第一次到达结点时就输出结点数据。
*/
public void DLR(Node node){
Print(node.getValue());
if(node.getLeft() != null){
DLR(node.getLeft());
}
if(node.getRight() != null){
DLR(node.getRight());
}
}
中序遍历：先递归访问根的左子树，然后是根节点，最后是右子树（左根右，就是第二次访问到该节点时就打印，左子树节点都在根节点左侧，右子树节点在根节点右侧）
/**
* 中序遍历：从二叉树的根结点出发，当第二次到达结点时就输出结点数据。
*/
public void LDR(Node node){
//找到最左边的结点
if(node.getLeft() != null){
LDR(node.getLeft());
}
Print(node.getValue());
if(node.getRight() != null){
LDR(node.getRight());
}
}
后序遍历：先递归访问左子树，在递归访问右子树，最后是根节点（左右根，就是第三次访问到该节点时就打印）
/**
* 后序遍历：从二叉树的根结点出发，当第三次到达结点时就输出结点数据。
*/
public void LRD(Node node){
if(node.getLeft() != null){
LRD(node.getLeft());
}
if(node.getRight() != null){
LRD(node.getRight());
}
Print(node.getValue());
}
层序遍历：将二叉树层层访问
/**
* 层序遍历：按照树的层次自上而下的遍历二叉树。
*/
public void BFS(Node node){
Queue<Node> nodes = new LinkedList<>();
nodes.add(node);
while (!nodes.isEmpty()){
Node poll = nodes.poll();
Print(poll.getValue());
if(poll.getLeft() != null){
nodes.offer(poll.getLeft());
}
if(poll.getRight() != null){
nodes.offer(poll.getRight());
}
}
}
前序遍历：
8 7 5 1 -1 -1 -1 4 -1 -1 6 3 -1 -1 2 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
中序遍历：
0 -1 0 -1 0 2 0 -1 0 -1 0 3 0 6 0 -1 0 -1 0 4 0 -1 0 -1 0 -1 0 1 0 5 0 7 0 8 0
后序遍历：
0 0 -1 0 -1 0 2 0 -1 0 -1 0 3 0 6 0 -1 0 -1 0 4 0 -1 0 -1 0 -1 0 1 0 5 0 7 0 8
层序遍历：
8 7 0 5 0 1 0 -1 0 -1 0 -1 0 4 0 -1 0 -1 0 6 0 3 0 -1 0 -1 0 2 0 -1 0 -1 0 0 0
