【Java--数据结构】二叉树

欢迎关注个人主页：逸狼

创造不易，可以点点赞吗~

如有错误，欢迎指出~

树结构

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

常见概念

节点的度：一个节点含有子树的个数，如A的度为6

树的度：一颗树所有节点的度的最大值，如上图中树的度为6

叶子节点（终端节点）：度为0的节点，如P,Q节点

父节点（双亲节点）：有子节点的节点，如A是B的父节点

子节点（孩子节点）：与父节点相反，如B是A的子节点

根节点：没有父节点的节点，如A

节点的层次：从根节点为第1层，往下数，以此类推。

树的高度：树的最大层次数，如上图树的高度为4

树的应用

二叉树

一棵二叉树是结点的一个有限集合，该集合：为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

注意：每个节点最多有两颗子树，且有左右之分。

二叉树的各种情况

满二叉树与完全二叉树

满二叉树：每层的节点都达到最大值。（若满二叉树的层数为k,则节点个数为2^K-1）

完全二叉树：每一层从左到右数，直到最后一个节点的前面必须是满的。(满二叉树是特殊的完全二叉树)

二叉树的性质：

前、中、后、层序遍历

前序遍历：根、左、右

中序遍历：左、根、右

后序遍历：左、右、根

层序遍历：从上到下，从左到右，依次遍历

创建二叉树

二叉树的节点

public class TestBinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val=val;
        }
    }
}

手动搭建一个二叉树

    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;

        return A;
    }

    public void preOrder (TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        //递归遍历左子树
        preOrder(root.left);
        //递归遍历右子树
        preOrder(root.right);
    }

    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    public void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

测试

        TestBinaryTree testBinaryTree=new TestBinaryTree();
        TestBinaryTree.TreeNode root= testBinaryTree.createTree();
        testBinaryTree.preOrder(root);
        System.out.println();
        testBinaryTree.inOrder(root);
        System.out.println();
        testBinaryTree.postOrder(root);

根据前序遍历和中序遍历

或者后序遍历和中序遍历可以创建二叉树

而前序和后序不能

获取整棵树的节点数size

子问题思路

左子树节点数+右子树节点数+1=整棵树的

    //求整个树的节点个数
    public int size(TreeNode root){
        if(root==null){
            return 0;
        }
        int ret=size(root.left)+size(root.right)+1;
        return ret;
    }

遍历思路

每遍历一个节点就++


    //遍历思路
    public int nodeSize;
    public void size2(TreeNode root){
        if(root==null){
            return;
        }
        nodeSize++;
        size2(root.right);
        size2(root.left);
    }

求叶子节点的个数

子问题思路

整棵树的叶子节点个数=左树的+右树的

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

遍历思路

    public  int leafSize;

    public void getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return ;
        }

        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }

计算第k层有多少个节点

已知前提：k是合法的


    public int getKLevalNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevalNodeCount(root.left,k-1)+getKLevalNodeCount(root.right,k-1);
    }

求树的高度

整棵树的高度=Math.max(左树的高度和右树高度)+1

    //求树的高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
//        return Math.max(leftHeight,rightHeight)+1;
        return leftHeight>rightHeight?
                leftHeight+1:rightHeight+1;
    }

找值为val的节点

//    找值为val的节点
    public TreeNode find(TreeNode root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode ret=find(root.left,val);
        if(ret!=null){
            return ret;
        }
        ret=find(root.right,val);
        if(ret!=null){
            return ret;
        }
        return null;
    }