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

性质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 - 1532 = 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 数据结构】优先级队列

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

标签: Java