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

这里有个问题，前面学习的 Stack 和 ArrayList 需要判断满的情况并扩容，那么二叉树可能出现满的情况吗？显然不会，因为二叉树是由节点构造而成的，但是如果每层的节点数都达到了最大值，那么这棵树就是满二叉树。换句话说，如果一颗二叉树的层数为k，且总结点的个数是2^k-1，那么就是满二叉树。满二叉树图例：

第二个概念：完全二叉树，篮球哥这里用简短的话来描述，每一层的节点都是从左往右的，依次排列，中间不能空，完全二叉树是一种效率很高的数据结构，后续讲优先级队列会讲解到，理论看不明白没关系，我们直接看图：

2.3 二叉树的性质

性质1: 如果规定根节点的层数为1，那么一颗非空的二叉树的第 k 层上最多有 2^(k-1) 个节点 k>0。

性质2: 如果规定只有根节点的二叉树的深度为 1，则深度为 k 的二叉树的最大节点数是 2^k - 1（k >= 0）。

性质3: 对于任何一棵二叉树，如果叶子(度为0)节点的个数为 n0，度为2的非叶子节点的个数为 n2，则 n0 = n2 + 1。

性质4: 具有 n 个节点的完全二叉树的深度 k 为 log(n+1) 上取整。（以2为底）

性质5: 对于具有n个节点的完全二叉树，如果从上至下，从左至右的顺序对所有的节点从 0 开始进行编号，如果父节点下标为 i，左孩子节点下标为：2 * i + 1 且 < n，右孩子下标为：2 * i + 2 且 < n，已知孩子节点下标，求父节点：(i - 1) / 2 = 父节点下标，若 i = 0，则 i 为根节点编号。

2.4 二叉树性质相关习题

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）

A.不存在这样的二叉树 B.200 C.198 D.199

题解： 这道题我们可以运用上面的二叉树的性质3，任意一颗二叉树中，度为2比度为0的节点多一个，那题目告诉我们有 199 个度为 2 的节点，所以度为 0 的节点就是 199 + 1，本题选 A

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（）

A.n B.n+1 C.n-1 D.n/2

题解：因为二叉树不存在度大于 2 的节点，因此我们可知，度为0的节点 + 度为1的节点 + 度为2的节点 = 2n。设度为 0 的节点为 n0，度为 1 的节点为 n1，度为 2 的节点为 n2，所以：n0 + n1 + n2 = 2n。得出了这个公式，后面就好办了，我们看图：

3.一个具有767个节点的完全二叉树，其叶子节点个数为（）

A.383 B.384 C.385 D.386

题解：这道题跟上一道题思路类似，同样可以设：度为 0 的节点为 n0，度为 1 的节点为 n1，度为 2 的节点为 n2，那么是不是得出：767 = n0 + n1 + n2，后面岂不是好办了吗？直接看图：

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（）

A.11 B.10 C.8 D.12

这个题就比较简单了，运用上面二叉树的性质2，即：531 = 2^k - 1，532 = 2^k

k等于多少？当k等于9时，2^9 = 512，即k=9当前完全二叉树最大节点数为512小于531，不满足题意，当k等于10时，2^10 = 1024，满足题意，所以本题选 B！

3、实现二叉树的基本操作

3.1 了解二叉树的存储结构

二叉树的存储结构分为顺序存储和链式存储，顺序存储后续讲解优先级队列会讲，链式存储跟前面的链表还是有一定区别的。

二叉树的链式存储也是由一个个节点构成的，通常采用二叉链和三叉链(平衡二叉树...)

// 孩子表示法
public class TreeNode {
    private char val; //数据域
    private TreeNode left; //左孩子的引用，以左孩子为根的整棵树
    private TreeNode right; //右孩子的引用，以右孩子为根的整棵树
}

// 孩子双亲表示法
public class TreeNode {
    private char val; //数据域
    private TreeNode left; //左孩子的引用，以左孩子为根的整棵树
    private TreeNode right; //右孩子的引用，以右孩子为根的整棵树
    private TreeNode parent; //当前节点的根节点的引用
}

3.2 简单构造一棵二叉树

由于目前的学习深度不够，为了降低成本，我们需要先学习简单的二叉树的操作，熟练掌握这些操作之后，下期我们在讲解二叉树的练习题时会讲到如何构造一颗二叉树，比如将字符串转换成二叉树，而这里我们采用列举的方法来构造一颗二叉树。

如图：

public TreeNode creationTree() {
    // 这里我们用列举的方法创建一颗树
    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 = C;
    B.left = D;
    B.right = E;
    C.left = F;
    return A;
}

这样我们就简单构造出如上图一样的一颗二叉树了，下面我们将学习二叉树的一些相关操作，测试样例都是在上图的基础上进行测试。

3.3 二叉树的前序遍历

前序遍历就是先访问根节点，在访问左子树，根的右子树，这里我们一定要弄清楚一个点，根的左子树和右子树也可以看成一棵二叉树，根的左子树的根节点的左右子树又是一棵二叉树。

// 前序遍历 -> 根 左子树 右子树
public void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 碰到根节点就打印
    System.out.print(root.val + " ");
    // 遍历左子树
    preOrder(root.left);
    // 遍历右子树
    preOrder(root.right);
}

初学者看不懂这个代码没关系，博主来画递归展开图来详细介绍。

由这个递归展开图相信也能看明白，碰到根节点就打印，然后就去遍历当前根的左子树，如果实在不理解，就把博主的代码粘贴下去画递归展开图，多画几遍，你就能慢慢理解递归了！

按照我们这棵树，此时的前序遍历就是：A B D E C F

3.4 二叉树的中序，后序遍历

有了前序遍历的学习，其实中序后序遍历就很简单了，但是我们还是要了解他们的概念。

中序遍历：根的左子树 -> 根 -> 根的右子树
后序遍历：根的左子树 -> 根的右子树 -> 根

代码实现：

// 中序遍历 -> 左子树 根 右子树
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 + " ");
}

至于递归展开图，博主就不画了，不理解的小伙伴可以自己去画一画，还是那句话，数据结构多画图！

3.5 获取二叉树节点的个数

这道题我们仍然可以采用前序遍历的思想，先看代码，在作解释：

// 获取二叉树中节点的个数
public int size(TreeNode root) {
    // 采用前序遍历的方式来获取这个树的节点个数
    if (root == null) {
        return 0;
    }
    return size(root.left) + size(root.right) + 1;
}

如果以任意一颗树的根节点的角度看，我的左子树为null，我的右子树也为空，那么是不是意味着这颗子树走完了，也就是上述方法结束了，既然我方法结束了，我是不是要归回去，递归从哪来回哪去，那么是不是也要统计一下走完的这个根节点，也即加1，这个代码采用的是子问题思想，如果还不熟悉递归，一定要下去画递归展开图，就像博主画上面前序遍历那样。

3.6 获取二叉树叶子节点个数

// 获取叶子节点的个数
public int getLeafNodeCount(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 叶子节点的左孩子和右孩子都为null
    if (root.left == null && root.right == null) {
        return 1;
    }
    return getLeafNodeCount(root.left)
            + getLeafNodeCount(root.right);
}

在二叉树的性质，我们提到过，叶子节点的左子树为空，右子树也为空，如果采用子问题思路，可以写出如上的代码。如果不理解这个递归，一定要画递归展开图哦，多画几次就理解了！

3.7 获取第k层的节点个数

这个方法其实很简单，前面我们会求节点个数，那么第 k 层的节点个数，是不是就是第 k-1 层的子节点个数呢？所以当我们递归到第 k 层的时候，我们就不用往后递归了。

// 获取第K层节点的个数
public int getKLevelNodeCount(TreeNode root, int k) {
    // 第k层节点的个数，也就是第k-1层的子节点个数
    if (root == null) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    return getKLevelNodeCount(root.left, k - 1)
            + getKLevelNodeCount(root.right, k - 1);
}

3.8 获取二叉树的高度

二叉树的高度，如果用子问题方法来解决的话，那是不是以任意一个根节点为树的高度都是左子树右子树的高度较大值+1 ？

// 获取二叉树的高度
public int getHeight(TreeNode root) {
    // 求左子树的高度和右子树的高度，返回他们的较大值
    if (root == null) {
        return 0;
    }
    int leftH = getHeight(root.left);
    int rightH = getHeight(root.right);
    return leftH > rightH ? leftH + 1 : rightH + 1;
}

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

这道题仍然可以采用遍历二叉树的思想，我们要注意的是，如果找到了这个节点，是不是就不用递归了？换句话说，如果我在任意一棵左子树中找到了val，我还需要去右子树找吗？肯定是不需要的，如果左子树右子树都找完了，还是找不到，就返回 null 了。

// 检测值为value的元素是否存在
TreeNode find(TreeNode root, char val) {
    if (root == null) {
        return null;
    }
    if (root.val == val) {
        return root;
    }
    // 递归左子树和右子树
    TreeNode l = find(root.left, val);
    if (l != null) {
        //如果我的左子树返回值不为null,表示在左子树找到了val值对应的节点
        //直接返回该节点,不用再去递归右子树了！
        return l;
    }
    TreeNode r = find(root.right, val);
    if (r != null) {
        //如果我的右子树返回值不为null,表示在右子树找到了val值对应的节点
        return r;
    }
    return null;
}

3.10 层序遍历

解决这个方法我们来换一种思路，采用非递归的方式，思路是这样的，定义一个队列，先把根节点入队，如果队列不为空，将队头的元素出队放入临时变量中，接着入队临时变量不为空的左右子节点，左右节点为 null 则不入队，上述循环，当队列为空，层序遍历结束。

//层序遍历
public void levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        //出队头元素
        TreeNode tmp = queue.poll();
        System.out.print(tmp.val + " ");
        if (tmp.left != null) {
            queue.offer(tmp.left);
        }
        if (tmp.right != null) {
            queue.offer(tmp.right);
        }
    }
}

3.11 判断一棵二叉树是否为完全二叉树

这个方法实现思路跟上述差不多，具体就是左右子树为null的时候也要入栈，当发现出队出到了null，如果是完全二叉树，队列的后续节点应该都为空，否则则不是完全二叉树！

// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode tmp = queue.poll();
        if (tmp != null) {
            queue.offer(tmp.left);
            queue.offer(tmp.right);
        } else {
            // 走到这里表示碰到了null节点，因为是完全二叉树，而我们又是层序遍历
            // 所以此时如果是完全二叉树的情况，队列剩下的元素都是null
            // 在遍历队列剩余的元素中，一旦发现不为有一个元素不为null，都不是完全二叉树
            while (!queue.isEmpty()) {
                tmp = queue.poll();
                if (tmp != null) {
                    return false;
                }
            }
        }
    }
    return true;
}

以上就是二叉树的一些基本操作了，有了二叉树的基础，我们后面学习优先级队列或者二叉搜索树会更轻松，初学者刚接触二叉树可能有点难，但不用担心，慢慢来就好，多画图。

下期预告：【Java 数据结构】优先级队列

好博客就要一起分享哦！分享海报

此处可发布评论

评论（0）展开评论

暂无评论，快来写一下吧

展开评论

您可能感兴趣的博客