【数据结构与算法】9. 二叉树的基本操作

爱敲代码的小杨.

发布于 2024-10-15 01:23:15

10400

代码可运行

文章被收录于专栏：JavaJava

运行总次数：0

代码可运行

前面我们了解了二叉树的基本概念，以及二叉树的三种遍历方式，今天我们来学习二叉树的基本操作

1. 二叉树的基本操作

1.1 获取树中节点的个数

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回0
不为空，返回左子树的个数+右子树的个数+根节点

size方法：

    /**
     * 获取树种节点的个数
     * 子问题
     * @param root
     * @return
     */
    public int size(TreeNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 左子树的个数+右子树的个数+1
        int nums = size(root.left) + size(root.right) + 1;
        return nums;
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree(); // 创建二叉树
        int num = binaryTree.size(root); // 调用size方法
        System.out.println("二叉树的节点个数:" + num);
    }
}

1.2 获取叶子节点的个数

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回0
如果不为空，根节点左子树和右子树为空，则返回1（只有根节点）
如果都不为空，则返回左子树的个数+右子树的个数

getLeafNodeCount方法：

    /**
     * 获取叶子节点的个数
     * @param root
     * @return
     */
    public int getLeafNodeCount(TreeNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 只有头节点
        if (root.left == null && root.right == null) {
            return 1;
        }
        int i = getLeafNodeCount(root.left);   // 左子树的个数
        int j = getLeafNodeCount(root.right);  // 右子树的个数
        return (i + j);
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree(); // 创建二叉树
        int num = binaryTree.getLeafNodeCount(root); // 
        System.out.println("叶子节点的个数" + num);
    }
}

1.3 获取第K层节点的个数

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回0
不为空，如果层数为1并且根节点不为空，则返回1
如果层数大于1，则返回根节点的左子树和右子树的k-1层之和

getKLevelNodeCount方法：

    /**
     * 获取第k层节点的个数
     * @param root 树的头节点
     * @param k 第k层
     * @return
     */
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int i = getKLevelNodeCount(root.left, k - 1);
        int j = getKLevelNodeCount(root.right, k - 1);
        return i + j;
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree(); // 创建二叉树
        int k = 2;
        int num = binaryTree.getKLevelNodeCount(root, k);
        System.out.println("第" + k +"层的节点个数:" + num);
    }
}

1.4 获取二叉树的高度

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回0
如果不为空，则计算根节点的左子树和右子树的高度
返回子树的最高层+1

getHeight方法：

    /**
     * 获取二叉树的高度
     * @param root
     * @return
     */
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int i = getHeight(root.left); // 左子树的高度
        int j = getHeight(root.right); // 右子树的高度
        return Math.max(i, j) + 1;
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree(); // 创建二叉树
        int height = binaryTree.getHeight(root);
        System.out.println("二叉树的高度：" + height);
    }
}

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

实现方法：

判断根节点是否为空（如果根节点为空则这棵树为空树），返回null；
如果不为空，判断根节点的值是否为要查找的值；如果是，则返回根节点的值；
递归在左子树中查找值，如果在左子树中找到了值，则返回找到的节点；
如果没在左子树找到值，则递归在右子树中查找值，如果在右子树中找到了值，则返回找到的节点；
如果左右子树都没有找到值，则返回null

find方法：

    /**
     * 判断val是否存在
     * @param root 头节点
     * @param val 要查找的值
     * @return
     */
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        // 判断根节点是否是要找的数据
        if (root.val == val) {
            return root;
        }
        TreeNode leftVal = find(root.left, val);
        if (leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = find(root.right, val);
        if (rightVal != null) {
            return rightVal;
        }

        return null;
    }

测试代码：

public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree();

        BinaryTree.TreeNode num = binaryTree.find(root, 'A');
        if (num == null) {
            System.out.println("没有找到要查找的值");
            return;
        }
        System.out.println(num.val);
    }
}

1.6 完整代码

public class BinaryTree {
    // 节点类
    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; // 返回根节点
    }

    // 前序遍历
    void preOrder(TreeNode root) {
        // 判断是否为空树
        if (root == null) {
            return;
        }
        // 打印当前节点的值
        System.out.print(root.val + " ");
        // 递归左子树
        preOrder(root.left);
        // 递归右子树
        preOrder(root.right);

    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归左子树
        inOrder(root.left);
        // 打印当前节点的值
        System.out.print(root.val + " ");
        // 递归右子树
        inOrder(root.right);

    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归左子树
        postOrder(root.left);
        // 递归右子树
        postOrder(root.right);
        // 打印当前节点的值
        System.out.print(root.val + " ");
    }

    /**
     * 获取树种节点的个数
     * 子问题
     * @param root
     * @return
     */
    public int size(TreeNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 左子树的个数+右子树的个数+1
        int nums = size(root.left) + size(root.right) + 1;
        return nums;
    }

    /**
     * 获取叶子节点的个数
     * @param root
     * @return
     */
    public int getLeafNodeCount(TreeNode root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 只有头节点
        if (root.left == null && root.right == null) {
            return 1;
        }
        int i = getLeafNodeCount(root.left);   // 左子树的个数
        int j = getLeafNodeCount(root.right);  // 右子树的个数
        return (i + j);
    }

    /**
     * 获取第k层节点的个数
     * @param root 树的头节点
     * @param k 第k层
     * @return
     */
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int i = getKLevelNodeCount(root.left, k - 1);
        int j = getKLevelNodeCount(root.right, k - 1);
        return i + j;
    }

        /**
         * 获取二叉树的高度
         * @param root
         * @return
         */
        public int getHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int i = getHeight(root.left); // 左子树的高度
            int j = getHeight(root.right); // 右子树的高度
            return Math.max(i, j) + 1;
        }

    /**
     * 判断val是否存在
     * @param root 头节点
     * @param val 要查找的值
     * @return
     */
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        // 判断根节点是否是要找的数据
        if (root.val == val) {
            return root;
        }
        TreeNode leftVal = find(root.left, val);
        if (leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = find(root.right, val);
        if (rightVal != null) {
            return rightVal;
        }

        return null;
    }
}