数据结构-二叉树详解（原理+基本操作Java实现）-蒲公英云

二叉树的概念及特点

二叉树的概念

二叉树（Binary Tree）是n （n>=0）个节点的有限集合，该集合可以为空集（称为空二叉树），或者由一个根节点和两个互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

二叉树的特点：

1、每个节点最多有两棵子树，即不存在超过度为2的节点。

2、二叉树的子树有左右之分，且左右不能颠倒。

如下图所示，下图就是一个二叉树

特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

如下图所示

2.完全二叉树：完全二叉树是由满二叉树引出的。满二叉树要求每一层的节点数都达到最大值，完全二叉树仅要求除最后一层外的节点数达到最大值，也就是说最后一层可以不满。我们可以把满二叉树看错特殊的完全二叉树。

如下图所示

二叉树的性质

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

2.若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1。

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

4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1)

5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

（1）若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

（2）若2i+1=n否则无左孩子

（3）若2i+2=n否则无右孩子

二叉树的基本操作

树结点类和构造方法

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');
        A.left=B;
        A.right=D;
        B.left=C;
        D.left=E;
        D.right=F;
        return A;
    }

遍历

前序遍历

public void preOrder(TreeNode root) {
        if (root==null){
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

中序遍历

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

后序遍历

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

获取树中节点的个数：遍历思路

public static int nodeSize;//定义一个全局变量方便保存结点个数
public void size(TreeNode root) {
        if (root==null){
            return;
        }
        nodeSize++;//不是空就++
        size(root.left);
        size(root.right);
    }

获取节点的个数：子问题的思路

int size2(TreeNode root) {
        if (root==null){
            return 0;
        }
        int leftSize=size2(root.left);//先求左子树的结点个数
        int rightSize=size2(root.left);//然后求右子树结点的个数
        return leftSize+rightSize+1;//返回左子树和右子树加上1
    }

也许有的小伙伴不明白为什么要加一，加一就是加上本根结点

获取叶子节点的个数：遍历思路

遍历思路跟上面一样，定义全局变量，满足条件就++，缺点就是只能求一棵树，两棵树就不好求，建议大家用子问题的思路

public static int leafSize = 0;//和上面一样，方便保存叶子结点个数 
    void getLeafNodeCount1(TreeNode root) {
        if (root==null){
            return;
        }
        if (root.left==null&&root.right==null){//满足if里面的条件就说明是叶子结点
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

获取叶子节点的个数：子问题

如下代码，满足条件就返回1，否则返回零，通过左子树加右子树累加起来，最后返回总数目

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

获取第K层节点的个数

利用一直递归k-1求得左子树和右子树的本层结点个数，最后返回它们的和

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

获取二叉树的高度

利用递归方法返回左右子树最大高度加上根节点本身

int getHeight(TreeNode root) {
       if (root==null){
           return 0;
       }
       int leftHigh=getHeight(root.left);
       int rightHigh=getHeight(root.right);
       return Math.max(leftHigh,rightHigh)+1;
    }

检测值为value的元素是否存在

TreeNode find(TreeNode root, char val) {
        if(root == null) {
            return null;
        }
        if(root.val == val) {
            return root;
        }
        TreeNode ret1 = find(root.left,val);
        if(ret1 != null) {
            return ret1;//如果左子树不为空，就说明找到了，返回
        }
        TreeNode ret2 = find(root.left,val);
        if(ret2 != null) {
            return ret2;//如果右子树不为空，就说明找到了，返回
        }
        return null;
    }

判断一棵树是不是完全二叉树

boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()) {
            TreeNode node = qu.poll();
            if(node != null) {
                qu.offer(node.left);
                qu.offer(node.right);
            } else {
                break;
            }
        }
        if(!qu.isEmpty()) {
            TreeNode node = qu.poll();
            if(node != null) {
                return false;
            }
        }
        return true;
    }