数据结构之初始二叉树（2）

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

二叉树的前置知识（概念、性质、、遍历）

通过上篇文章的学习，我们已经知道什么是二叉树，以及其性质和遍历的方式了。接下来主要是实现代码。

目录

伪创建二叉树

遍历二叉树 

获取二叉树中节点的个数 

获取二叉树中叶子节点的个数

获取二叉树中第K层节点的个数

获取二叉树的高度 

在二叉树中找寻元素 

---

伪创建二叉树

为啥叫伪创建二叉树呢？因为我们现在才刚开始学习二叉树，而创建二叉树是一个非常复杂的过程（树的递归定义的）。因此我们就先手动的来创建二叉树。树是有一个一个的结点组成，因此得先把结点创建出来。树的结点我们采用的是简单的孩子表示法：

    // 树的结点
    static class TreeNode {
        public char val; // 数据域
        public TreeNode left; // 左子树
        public TreeNode right; // 右子树
 
        public TreeNode(char val) {
            this.val = val;
        }
    }

创建的二叉树图形如下：

    public TreeNode createBinaryTree() {
        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');
        // 根据图形关系把结点之间相连
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        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);
    }

递归的限制条件：当递归到 root 为 null 时，就开始回退。随着递归的深入，root 不断的接近 null。

中序遍历：

    // 中序遍历
    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+" ");
    }

由于层序遍历还是比较复杂，因此我们后面再学习。

获取二叉树中节点的个数 

思路一：这个同样是遍历二叉树，遇到不为空的结点就++，最后统计的就是树的节点个数。

    // 记录节点个数
    public int treeNodeSize; 
    public void size(TreeNode root) {
        if (root == null) {
            return;
        }
        // 根结点
        treeNodeSize++;
        // 左子树
        size2(root.left);
        // 右子树
        size2(root.right);
    }

思路二：整棵树的节点个数等于 根结点+左子树的节点个数+右子树的节点个数

    // 获取树中节点的个数
    public int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 左子树的节点个数+右子树的节点个数+根结点
        return size(root.left)+size(root.right)+1;
    }

思路一采用的是遍历的方式，思路二采用的是化为子问题的方式。思路二也是更加接近递归的方式。

获取二叉树中叶子节点的个数

思路：首先，我们得知道什么是叶子节点。叶子结点的特点是其左孩子和右孩子都是null。同样这也是采用遍历的方式。

法一：采用子问题思路

    // 获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 遇到叶子结点就返回1
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 返回左子树的叶子节点个数+右子树的叶子节点个数
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

法二：采用遍历思路

    public int leafSize;
    public void getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafSize++;
        }
        // 遍历左子谁
        getLeafNodeCount2(root.left);
        // 遍历右子树
        getLeafNodeCount2(root.right);
    }

获取二叉树中第K层节点的个数

上面是对于第K层的介绍，根结点是作为第一层。 

思路：当K为1时，就可以直接返回这一层的节点个数即可。因此我们就是要递归到K不断的接近1.

法一： 采用子问题思路

    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        // 假定不存在K无效的情况
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        // 左子树的第k-1层的节点个数+右子树的第k-1层的节点个数
        return getKLevelNodeCount(root.left, k-1) +
                getKLevelNodeCount(root.right, k-1);
    }

法二： 采用遍历思路

    public int getLevelNodeSize;
    public void getKLevelNodeCount(TreeNode root, int k) {
        // 假定不存在K无效的情况
        if (root == null) {
            return;
        }
        if (k == 1) {
            getLevelNodeSize++;
        }
        // 遍历左子树的第k-1层
        getKLevelNodeCount2(root.left, k-1);
        // 遍历右子树的第k-1层
        getKLevelNodeCount2(root.right, k-1);
    }

获取二叉树的高度 

思路：获取二叉树的高度和求第K层节点的个数类似。同样根结点算高度为1。接着就是分别递归计算左子树和右子树的高度的最大值。

采用子问题思路

    // 获取二叉树的高度
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 左子树与右子树的最大高度+根结点
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

这个如果不采用子问题思路，而是用遍历思路的话，只能用层序遍历来写，又因为层序遍历过于复杂，因此我们暂时先不写这个代码。

在二叉树中找寻元素 

 思路：这个比较简单，就是遍历去比较即可。

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        // 采用前序遍历的方式：根->左子树->右子树
        // 根
        if (root.val == val) {
            return root;
        }
        // 在左子树中寻找，肯定有一个结果
        TreeNode findLeft = find(root.left, val);
        // 如果不为null，则说明找到了
        if (findLeft != null) {
            return findLeft;
        }
        // 在右子树中寻找，肯定有一个结果，不管结果如何直接返回即可
        return find(root.right, val);
    }

注意：这里在寻找二叉树中的节点时，采用前序遍历的方式是最有效率的。因为前序遍历是首先比较根结点，而我们就是需要比较根结点。 

对于二叉树的基本操作我们就已经学习完了。基于上述基本操作就可以进行一些简单的刷题了，后续也会在刷题中继续完善二叉树的相关操作。

好啦！本期 数据结构之初始二叉树（2）的学习之旅就到此结束啦！我们下一期再一起学习吧！