二叉树

1. 二叉树

二叉树是一个有限结点的集合，该集合或者为空集，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成， 简单理解：每个结点最多可有两棵子树（即0，1，2棵）

特点

每个结点最多有两颗子树
左右子树是有顺序不能任意颠倒
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

2. 类型

斜树
满二叉树
完全二叉树

斜树: 所有节点都只有左子树的二叉树叫做左斜树，所有节点都只有右子树的二叉树叫做右斜树。(本质就是链表)

满二叉树: 二叉树中所有非叶子结点的度都是2，且叶子结点都在同一层次上

完全二叉树: 与满二叉树除了最后一层结构相同，最后一层可以不同

3. 基本运算

3.1 创建二叉树

一般是给出数组，然后把数组变成二叉树，并且创建的是二叉查找树（当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大）

节点类

public class TreeNode {
	
	private int value;
	private TreeNode leftTreeNode;
	private TreeNode RightTreeNode;
	
	public TreeNode(int value) {
		this.value = value;
	}

	//Getters/Setters
}

根结点类

public class TreeRoot {
	
	private TreeNode treeNode;

	public TreeNode getTreeNode() {
		return treeNode;
	}

	public void setTreeNode(TreeNode treeNode) {
		this.treeNode = treeNode;
	}
}

创建树的方法

public void creatTree(TreeRoot treeRoot,int value){
	
	//第一次访问,若根为空，则设置第一个值为树根
	//一定要有树根，第一次就是和树根比
	if(treeRoot.getTreeNode() == null){
		treeRoot.setTreeNode(new TreeNode(value));
	}else{
		
		//保存临时结点
		TreeNode tempNode = treeRoot.getTreeNode();

		while(tempNode != null){
			
			//当前值大于当前结点，往右走
			if(value > tempNode.getValue()){
				
				//当前结点的右节点为空，即插入
				if(tempNode.getRightTreeNode() == null){
					tempNode.setRightTreeNode(new TreeNode(value));
					return ;
				}else{
					//当前结点的右节点不为空，先去右节点
					tempNode = tempNode.getRightTreeNode();
				}
			//当前值小于等于当前结点，往左走
			}else{
				//当前结点的左节点为空，即插入
				if(tempNode.getLeftTreeNode() == null){
					tempNode.setLeftTreeNode(new TreeNode(value));
					return ;
				}else{
					//当前结点的左节点不为空，先去左节点
					tempNode = tempNode.getLeftTreeNode();
				}
			}
		}
	}
}

3.2 遍历

先序遍历：先访问根节点，然后访问左节点，最后访问右节点(根->左->右)
中序遍历：先访问左节点，然后访问根节点，最后访问右节点(左->根->右) 二叉搜索树中序遍历是排序的
后序遍历：先访问左节点，然后访问右节点，最后访问根节点(左->右->根)

先序

public void preTree(TreeNode treeNode){
	
	if(treeNode != null){

                //访问根节点
		System.out.println(treeNode.getValue());
		
                //访问左节点
		preTree(treeNode.getLeftTreeNode());
		
		//访问右节点
		preTree(treeNode.getRightTreeNode());
	}
}

中序

public void inTree(TreeNode treeNode){
	
	if(treeNode != null){
		
		//访问左节点
		inTree(treeNode.getLeftTreeNode());
		
		//访问根节点
		System.out.println(treeNode.getValue());
		
		//访问右节点
		inTree(treeNode.getRightTreeNode());
	}
}

后序

public void postTree(TreeNode treeNode){
	
	if(treeNode != null){
		
		//访问左节点
		postTree(treeNode.getLeftTreeNode());
		
		//访问右节点
		postTree(treeNode.getRightTreeNode());
        
        //访问根节点
		System.out.println(treeNode.getValue());
	}
}

测试

public static void main(String[] args) {
	
	int[] arrs = {6,2,3,4,5,7,9,10};
	
	TreeRoot treeRoot = new TreeRoot();
	
	for(int arr : arrs){
		createTree(treeRoot,arr);
	}
	
    //先序遍历
	preTree(treeRoot.getTreeNode());
}

6 2 3 4 5 7 9 10

4.重建二叉树（以先中序为例）

二叉树先序，中序，后序的序列都无法唯一确定树形，但若知道先中序或者中后序就可以确定树形，先后序也不行

先序确定根节点
中序确定左右子树

4.1 原理

先序：ABDGCEF 中序：DGBAECF

由先序可知根节点为A，再从中序可知DGB、ECF分别为根节点的左右子树
同理可知左子树中D为当前树的根节点，右子树中C为当前树的根节点
再继续往下构建，可得出叶子节点

手动画了一幅图，凑合着看吧

对应代码

节点

public class TreeNode {
	public int val;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int x) { 
		val = x; 
	}
}

主类

//剑指offer第四题
//传入数组的序列
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
		
    	//判断是否空数组
    	if(pre.length == 0 || in.length == 0){
    		return null;
    	}
    	
    	//创建当前树的根节点
    	TreeNode treeNode = new TreeNode(pre[0]);
    	for(int i = 0;i < pre.length;i++){
    		//找出根在中序的位置
    		if(pre[0] == in[i]){
    			
    			//左子树继续构建
    			treeNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
    			//右子树继续构建
    			treeNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length),Arrays.copyOfRange(in, i+1, in.length));
    			//找到位置就停止循环
    			break;
    		}
    	}
    	//返回当前树的根节点
    	return treeNode;
    }
}

参考
寒江独钓