二叉树

树的基本概念

树是一种 非线性的 数据结构 n(n>0) 个有限节点组成一个具有层次关系的集合 像一颗倒挂的树

根朝上 叶朝下

这里重要的是 树中的几个概念

1. 结点的度 ：一个结点含有子树的个数 比如上面的图 A的度为 6
2. 树的度 ： 一颗树中 ，所有结点度的最大值成为树的度 如上图 树的度是 6
3. 叶子节点或终端节点： 度为0的结点称为叶节点；如上图 J、F、K、L、H、I
4. 双亲结点或父结点： 若一个结点含有子节点 则这个结点称为其子结点的父节点 如上图 A是B的父节点
5. 孩子结点或子节点： 一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
6. 根结点： 一棵树中没有双亲结点的结点 如 A
7. 结点的层次： 从根开始定义，根为第一层，根的子节点为第二层
8. 树的高度或深度： 树中结点的最大层次；如上图 树的高度为4

树的表现形式

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

class TreeNode{
    public int val;//存储数据
    public TreeNode left;//链接第一个孩子
    public TreeNode right;//链接第二个孩子
    
    public TreeNode(int val){//有参构造
        this.val = val;
    }
}

这里写的是一个树结点

二叉树

概念

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

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

注意 二叉树 有左右之分 次序不能颠倒 ，因此 二叉树是有序树

两种特殊的二叉树

1. 满二叉树：每一层的结点数都达到最大值 ，则这颗二叉树就是满二叉树，如果说一颗二叉树的层数为K，则 节点总数是 $2^k-1$
2. 完全二叉树：效率很高的一种数据结构，对于深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从0至n-1的结点————对应时称之为完全二叉树，所以 满二叉树也是一种特殊的二叉树

这里 白话 就是每一个结点都是从左到右依次排满的

二叉树的性质

1. 根结点的层数为1，则一颗非空二叉树的第i层上最多有$2^{i-1}$
2. 若只有根节点的二叉树深度为1，则深度为k的二叉树最大结点个数为 $2^k-1$
3. 对任何一颗二叉树，如果其叶节点个数为n0，度为2的非叶结点为n2，则有 n0 = n2 + 1；
4. 对于具有n个结点的完全二叉树的深度k为$log_2(n+1)$向上取整
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：
6. 若i>0，双亲序号：$(i-1)/2$；i=0，i为根结点编号，无双亲结点
7. 若2i+1<n,左孩子序号 2i+1 ，否则无左孩子
8. 若2i+1<n,左孩子序号 2i+2 ，否则无右孩子

二叉树的存储

public class BinaryTree{
    public static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        
        public TreeNode (int val){
            this.val = val;
        }
    }
    private TreeNode root ; //根节点
    
}

二叉树的遍历

1. 前中后序遍历
   • 前序遍历--访问根节点-->根的左子树-->根的右子树
   • 中序遍历--左根右
   • 后序遍历--左右根

void preOrder(Node root);

void inOrder(Node root);

void postOrder(Node root);

• 前序遍历--根左右 123456
• 中序遍历--左根右 321546
• 后序遍历--左右根 325641

二叉树的基本操作

public class BinaryTree {
	//树节点内部类
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    
    //有返回值的前序遍历
    public List<TreeNode> preOrder(TreeNode root){
        List<TreeNode> tree = new LinkedList<>();
        if(root == null) return null;
        tree.add(root);
        preOrder(root.left);
        preOrder(root.right);
        return tree;
    }
    //不用递归实现前序遍历 （利用栈的特性去做这个）
    public List<TreeNode> preOrder2(TreeNode root){
        if(root == null) return null;
        List<TreeNode> tree = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur!=null || !stack.isEmpty()){
        	while(cur!=null){
            	tree.add(cur);
            	stack.push(cur);
            	cur = cur.left;
       	 	}
       	 	top = stack.pop();
        	cur = top.right();
        }
    }
    
    //中序遍历
    public List<TreeNode> inOrder(TreeNode root){
        List<TreeNode> tree = new LinkedList<>();
        if(root == null) return null;
        inOrder(root.left);
        tree.add(root);
        inOrder(root.right);
        return tree;
    }
    
    //后序遍历
    public List<TreeNode>  postOrder(TreeNode root){
        List<TreeNode> tree = new LinkedList<>();
        if(root == null) return null;
        postOrder(root.left);
        postOrder(root.right);
        tree.add(root);
        return tree;
    }
   	//获取树中结点个数 递归
    public int size = 0;
    public int size(TreeNode root){
        if(root == null) return 0;
        size++;
        size(root.left);
        size(root.right);
        return size;
    }
    //子问题思想 也是递归 
    public int nodeSize(TreeNode root){
        if(root == null) return 0;
        return nodeSize(root.left) + nodeSize(root.right)+1;		 
    }
    
    //求叶子结点的个数
    public int LeafSize = 0;
    public int getLeafCount(TreeNode root){
        if(root == null)return 0;
        if(root.left == null && root.right==null){
            LeafSize++;
        }
        getLeafCount(root.left);
        getLeafCount(root.right);
        return LeafSize;
    }
    //子问题思想
    public int getLeafNodeCount(TreeNode root){
        if(root == null)return 0;
        return (root.left == null && root.right == null)?gerLeafNodeCount(root.left) + gerLeafNodeCount(root.right) +1 : gerLeafNodeCount(root.left) + gerLeafNodeCount(root.right);
    }
    //获取第K层结点的个数  利用好这个k
    public int gerKLevelNodeCount(TreeNode root,int k){
        if(root == null)return 0;
        if(k == 1){
            return 1;
        }
        return gerKLevelNodeCount(root.lefr,k-1)+gerKLevelNodeCount(root.right,k-				1)
	}
    
    //获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return (leftHeight > rightHeight)?leftHeight+1:rightHeight+1;
    }

    //检测value的元素是否存在
    public TreeNode find(TreeNode root,int val){
        if(root == null)return null;
        if(root.val = val){
            return root;
        }
        TreeNode trueLeft = find(root.left,val);
        if(trueLeft!=null)return trueLeft;
        TreeNode trueRight = find(root.right,val);
        if(trueRight!=null)return trueRight;
        return null;
    }