二叉树（Java）

柔光的暖阳◎ 2024-04-07 11:56 34阅读 0赞

#### 目录 ####

*   *  第9章 二叉树
     *   *  9.1 为什么需要树
         *  9.2 树的常用术语
         *  9.3 二叉树
         *   *  9.3.1 二叉树的概念
             *  9.3.2 二叉树的前中后许遍历
             *  9.3.3 二叉树的前中后遍历查找
             *  9.3.4 二叉树的删除节点
         *  本次二叉树教程出自韩顺平的数据结构与算法

### 第9章 二叉树 ###

#### 9.1 为什么需要树 ####

**分析树与其他存储结构的优缺点**

1）数组存储方式的分析

优点：通过下标方式访问元素，速度快，对于有序数组，还可以使用二分查找提高检索速度。

缺点：如果要检索具体某个值，或者插入值（按一定顺序)会整体移动，效率低

2）链式存储方式的分析

优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要插入节点，链接到链表中即可，删除效率也很好）

缺点：在进行检索时，效率依然低下（比如检索某个值，需要从头节点开始遍历）

3）树存储方式的分析

能提高数据存储，读取的效率，比如利用二叉排序树（BinarySort Tree）既可以保证数据的 检索速度，同时也可以保证数据的插入，删除，修改的速度。

#### 9.2 树的常用术语 ####

**树的常用术语**

1）节点

2）根节点

3）父节点

4）子节点

5）叶子节点（没有子节点的节点）

6）节点的权（节点的值）

7）路径（从root节点找到该节点的路线）

8）层

9）子树

10）树的高度（最大 层数）

11）森林：多颗子树构成森林

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jidZhDbY-1662035409016)(C:\\Users\\86139\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220831193440496.png)\]][img-jidZhDbY-1662035409016_C_Users_86139_AppData_Roaming_Typora_typora-user-images_image-20220831193440496.png]

#### 9.3 二叉树 ####

##### 9.3.1 二叉树的概念 #####

1）树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树

2）二叉树的子节点分为左节点和右节点

3）如果该二叉树的所有叶子节点都在最后一层，并且节点总数==在2^n-1，n为层数，则我们称为满二叉树。

4）如果该二叉树的所有叶子节点都在最后一层或者在倒数第二层，而最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fYH93ong-1662035409017)(C:\\Users\\86139\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220831194314378.png)\]][img-fYH93ong-1662035409017_C_Users_86139_AppData_Roaming_Typora_typora-user-images_image-20220831194314378.png]

##### 9.3.2 二叉树的前中后许遍历 #####

**前序遍历：先输出父节点，再遍历左子树和右子树**

**中序遍历：先遍历左子树，再输出父节点，再遍历右子树**

**后序遍历：先遍历左子树，再遍历右子树，最后输出父节点**

![在这里插入图片描述][d6c6809e5ccf4150a9188ee355152d4b.png]

**看输出父节点的顺序，就确定是前中后序遍历啦**

##### 9.3.3 二叉树的前中后遍历查找 #####

**思路分析**

**前序查找思路**

1、先判断当前节点的no是否等于要查找的

2、如果是相等，则返回当前节点

3、如果不等，则判断当前节点的左子节点是否为null，如果不为null，则递归前序查找

4、如果左递归前序查找，找到节点，则返回，否则继续判断。当前的节点的右子节点是否为 null，如果不为null。则继续向右递归前序查找

**中序查找思路**

1、判断当前节点的左子节点是否为null，如果不为null，则递归中序查找

2、如果找到，则返回，如果没有找到，就和当前接单比较。如果是则返回当前节点，否则继续进行右递归的中序查找

3、如果右递归中序查找，找到就返回，否则返回null

**后序查找思路**

1、判断当前节点的左子节点是否为null，如果不为null，则递归后序查找。

2、如果找到，就返回，如果没有找到。就判断当前节点的右子节点是否为null，如果不是null，则右递归进行后序查找，如果找到就返回

3、就和当前节点比较，如果是，就返回当前节点，否则就返回null。

![在这里插入图片描述][fe4c06e43bb5471dab00857118f494ba.png]

package com.ldm.tree;
    
    /**
     * @author 梁东明
     * 2022/8/31
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class BinaryTreeDemo {
        
        public static void main(String[] args) {
        
            //先需要创建一颗二叉树
            BinaryTree binaryTree = new BinaryTree();
            //创建需要的节点
            Node root = new Node(1, "小明");
            Node node2 = new Node(2, "李华");
            Node node3 = new Node(3, "张三");
            Node node4 = new Node(4, "李四");
            Node node5 = new Node(5, "王五");
            //手动创建二叉树，后续学习递归的方式创建二叉树
            root.setLeft(node2);
            root.setRight(node3);
            node3.setRight(node4);
            node3.setLeft(node5);
            binaryTree.setRoot(root);
            //前序遍历
            System.out.println("前序遍历");
            binaryTree.preorder();
            //中序遍历
            System.out.println("中序遍历");
            binaryTree.infixOrder();
            //后序遍历
            System.out.println("后序遍历");
            binaryTree.postOrder();
    
           /* //前序查找
            System.out.println("前序查找");
            Node resNode = binaryTree.preOrderSearch(5);
            if (resNode != null){
                System.out.println("找到了，信息为："+"  编号为："+resNode.getNo()+"\t姓名为："+resNode.getName());
            }else {
                System.out.println("没有找到节点为"+5+"的信息");
            }*/
           /* //中序查找
            System.out.println("中序查找");
            Node resNode = binaryTree.infixOrderSearch(5);
            if (resNode != null){
                System.out.println("找到了，信息为："+"  编号为："+resNode.getNo()+"\t姓名为："+resNode.getName());
            }else {
                System.out.println("没有找到节点为"+5+"的信息");
            }*/
            //后序查找
            System.out.println("后序查找");
            Node resNode = binaryTree.postOrderSearch(5);
            if (resNode != null){
        
                System.out.println("找到了，信息为："+"  编号为："+resNode.getNo()+"\t姓名为："+resNode.getName());
            }else {
        
                System.out.println("没有找到节点为"+5+"的信息");
            }
        }
    }
    
    //定义binaryTree 二叉树
    class BinaryTree{
        
        private Node root;  //定义根节点
    
        public void setRoot(Node root) {
        
            this.root = root;
        }
        //前序遍历
        public void preorder(){
        
            if (this.root != null){
        
                this.root.preOrder();
            }else {
        
                System.out.println("二叉树为null，无法遍历");
            }
        }
        //中序遍历
        public void infixOrder(){
        
            if (this.root != null){
        
                this.root.infixOrder();
            }else {
        
                System.out.println("二叉树为null，无法遍历");
            }
        }
        //后序遍历
        public void postOrder(){
        
            if (this.root != null){
        
                this.root.postOrder();
            }else {
        
                System.out.println("二叉树为null，无法遍历");
            }
        }
        //前序查找
        public Node preOrderSearch(int no){
        
            if (this.root != null){
        
                return root.preOrderSearch(no);
            }else {
        
               return null;
            }
        }
        //中序查找
        public Node infixOrderSearch(int no){
        
            if (this.root != null){
        
                return root.infixOrderSearch(no);
            }else {
        
                return null;
            }
        }
        //后序查找
        public Node postOrderSearch(int no){
        
            if (this.root != null){
        
                return root.postOrderSearch(no);
            }else {
        
                return null;
            }
        }
    
    }
    //先创建节点
    class Node{
        
        private int no;
        private String name;
        private Node left;  //默认为null
        private Node right;  //默认为null
    
    
        /**
         * 构造器
         * @param no   编号
         * @param name 名字
         */
        public Node(int no, String name) {
        
            this.no = no;
            this.name = name;
        }
    
        public int getNo() {
        
            return no;
        }
    
        public void setNo(int no) {
        
            this.no = no;
        }
    
        public String getName() {
        
            return name;
        }
    
        public void setName(String name) {
        
            this.name = name;
        }
    
        public Node getLeft() {
        
            return left;
        }
    
        public void setLeft(Node left) {
        
            this.left = left;
        }
    
        public Node getRight() {
        
            return right;
        }
    
        public void setRight(Node right) {
        
            this.right = right;
        }
    
        @Override
        public String toString() {
        
            return "Node{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    
        //前序遍历
        public void preOrder(){
        
            System.out.println(this); //先输出父节点
            //递归向左子树的遍历
            if (this.left !=null){
        
                this.left.preOrder();
            }
            //递归向左子树的遍历
            if (this.right !=null){
        
                this.right.preOrder();
            }
    
        }
        //中序遍历
        public void infixOrder(){
        
            //递归向左子树的遍历
            if (this.left !=null){
        
                this.left.infixOrder();
            }
            System.out.println(this); //先输出父节点
            //递归向左子树的遍历
            if (this.right !=null){
        
                this.right.infixOrder();
            }
        }
        //后序遍历
        public void postOrder(){
        
            //递归向左子树的遍历
            if (this.left !=null){
        
                this.left.postOrder();
            }
            //递归向左子树的遍历
            if (this.right !=null){
        
                this.right.postOrder();
            }
            System.out.println(this); //先输出父节点
        }
    
        /**
         * 前序遍历查找
         *
         * @param no 编号
         * @return 如果找到就返回Node，如果没有找到就返回null
         */
        public Node preOrderSearch(int no){
        
    
            System.out.println("遍历查找次数");
            //比较当前节点的no等于传入的no
            if (this.no == no){
        
                return this;
            }
            //1、判断当前节点是否为null，如果不为null，就前序递归遍历
            //2、如果左递归前序查找，找到节点，直接返回
            Node resNode = null;
            if ( this.left != null){
        
                resNode = this.left.preOrderSearch(no);
            }
            if (resNode != null){
          //说明左递归找打节点了
                return resNode;
            }
            //1、左递归前序查找，找到节点，则返回，否则继续判断
            //2、当前节点的右子节点是否为null，如果不为null，则继续向右递归前序查找
            if (this.right != null){
        
                resNode = this.right.preOrderSearch(no);
            }
            return resNode;
    
        }
    
        /**
         * 中缀顺序搜索
         *
         * @param no 编号
         * @return 如果找到就返回Node，如果没有找到就返回null
         */
        public Node infixOrderSearch(int no){
        
    
            //1、判断当前节点的左子节点是否为null，如果不为null，就递归中序查找
            Node resNode = null;
            if ( this.left != null){
        
                resNode = this.left.infixOrderSearch(no);
    
            }
            //2、如果左递归前序查找，找到节点，直接返回
            if (resNode != null){
          //说明左递归找打节点了
                return resNode;
            }
            System.out.println("遍历查找次数");
            //如果找到，则返回，如果没有找到，就和当前节点比较，如果是则返回当前节点
            if (this.no == no){
        
                return this;
            }
    
            //否则继续进行右递归的中序查找
            if (this.right != null){
        
                resNode = this.right.infixOrderSearch(no);
            }
            return resNode;
    
        }
        /**
         * 后序查找
         *
         * @param no 编号
         * @return 如果找到就返回Node，如果没有找到就返回null
         */
        public Node postOrderSearch(int no){
        
    
            //1、判断当前节点的左子节点是否为null，如果不为null，就递归后序遍历
            Node resNode = null;
            if ( this.left != null){
        
                resNode = this.left.postOrderSearch(no);
    
            }
            if (resNode != null){
          //说明左递归找打节点了
                return resNode;
            }
    
            //如果左子树没有找到，则向右子树进行后序遍历查找
            if (this.right != null){
        
                resNode = this.right.postOrderSearch(no);
            }
            if (resNode != null){
          //说明左递归找打节点了
                return resNode;
            }
            System.out.println("遍历查找次数");
            //如果左右子树都没有找到，就比较当前节点
            //比较当前节点的no等于传入的no
            if (this.no == no){
        
                return this;
            }
            //树中没有该节点就返回null
            return null;
    
        }
    
    
    }

##### 9.3.4 二叉树的删除节点 #####

**要求**

1、如果删除的节点是叶子节点，则直接删除该节点

2、如果删除的节点是非叶子节点，则删除该子树  
![在这里插入图片描述][f34a70b654704af39fc1e0ecfebc22c2.png]

**完成删除节点的操作**

**思路：**

首先处理：

考虑如果树本身是空树root，如果只有一个root节点，则等价于将二叉树置空

1、因为二叉树是单向的，所以我们是判断当前节点的子节点是否需要删除，而不能去判断当前这个节点是不是需要删除的节点。

2、如果当前节点的左子节点不为null，并且左子节点就是要删除的节点，就将当前节点的left置为null即：this.left=null;并且就返回（结束递归）

3、如果当前节点的右子节点不为null，并且右子节点就是要删除的节点，就将当前节点的right置为null即：this.right=null;并且就返回（结束递归）

4、如果第2、3步没有删除节点，那么需要向左子树进行递归删除

5、如果第4步也没有删除节点，则应当向右子树进行递归删除。

package com.ldm.tree;
    
    /**
     * @author 梁东明
     * 2022/8/31
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class BinaryTreeDemo {
        
        public static void main(String[] args) {
        
            //先需要创建一颗二叉树
            BinaryTree binaryTree = new BinaryTree();
            //创建需要的节点
            Node root = new Node(1, "小明");
            Node node2 = new Node(2, "李华");
            Node node3 = new Node(3, "张三");
            Node node4 = new Node(4, "李四");
            Node node5 = new Node(5, "王五");
            //手动创建二叉树，后续学习递归的方式创建二叉树
            root.setLeft(node2);
            root.setRight(node3);
            node3.setRight(node4);
            node3.setLeft(node5);
            binaryTree.setRoot(root);
      /*      //前序遍历
            System.out.println("前序遍历");
            binaryTree.preorder();
            //中序遍历
            System.out.println("中序遍历");
            binaryTree.infixOrder();
            //后序遍历
            System.out.println("后序遍历");
            binaryTree.postOrder();
    */
           /* //前序查找
            System.out.println("前序查找");
            Node resNode = binaryTree.preOrderSearch(5);
            if (resNode != null){
                System.out.println("找到了，信息为："+"  编号为："+resNode.getNo()+"\t姓名为："+resNode.getName());
            }else {
                System.out.println("没有找到节点为"+5+"的信息");
            }*/
           /* //中序查找
            System.out.println("中序查找");
            Node resNode = binaryTree.infixOrderSearch(5);
            if (resNode != null){
                System.out.println("找到了，信息为："+"  编号为："+resNode.getNo()+"\t姓名为："+resNode.getName());
            }else {
                System.out.println("没有找到节点为"+5+"的信息");
            }*/
           /* //后序查找
            System.out.println("后序查找");
            Node resNode = binaryTree.postOrderSearch(5);
            if (resNode != null){
                System.out.println("找到了，信息为："+"  编号为："+resNode.getNo()+"\t姓名为："+resNode.getName());
            }else {
                System.out.println("没有找到节点为"+5+"的信息");
            }*/
    
            //删除qian
            System.out.println("删除前,前序遍历");
            binaryTree.preorder();
            //删除后
            binaryTree.delete(5);
            System.out.println("删除后,前序遍历");
            binaryTree.preorder();
        }
    }
    
    //定义binaryTree 二叉树
    class BinaryTree{
        
        private Node root;  //定义根节点
    
        public void setRoot(Node root) {
        
            this.root = root;
        }
        //删除节点
        public void delete(int no){
        
            if (this.root != null){
        
                //需要判断该树是否只有根节点，是的话只需要删除根节点即可(将root置null）
                if (root.getNo() == no){
        
                    root = null;
                }else {
        
                    this.root.delete(no);
                }
            }else {
        
                System.out.println("空树，无法删除");
            }
        }
        //前序遍历
        public void preorder(){
        
            if (this.root != null){
        
                this.root.preOrder();
            }else {
        
                System.out.println("二叉树为null，无法遍历");
            }
        }
        //中序遍历
        public void infixOrder(){
        
            if (this.root != null){
        
                this.root.infixOrder();
            }else {
        
                System.out.println("二叉树为null，无法遍历");
            }
        }
        //后序遍历
        public void postOrder(){
        
            if (this.root != null){
        
                this.root.postOrder();
            }else {
        
                System.out.println("二叉树为null，无法遍历");
            }
        }
        //前序查找
        public Node preOrderSearch(int no){
        
            if (this.root != null){
        
                return root.preOrderSearch(no);
            }else {
        
               return null;
            }
        }
        //中序查找
        public Node infixOrderSearch(int no){
        
            if (this.root != null){
        
                return root.infixOrderSearch(no);
            }else {
        
                return null;
            }
        }
        //后序查找
        public Node postOrderSearch(int no){
        
            if (this.root != null){
        
                return root.postOrderSearch(no);
            }else {
        
                return null;
            }
        }
    
    }
    //先创建节点
    class Node{
        
        private int no;
        private String name;
        private Node left;  //默认为null
        private Node right;  //默认为null
    
    
        /**
         * 构造器
         * @param no   编号
         * @param name 名字
         */
        public Node(int no, String name) {
        
            this.no = no;
            this.name = name;
        }
    
        public int getNo() {
        
            return no;
        }
    
        public void setNo(int no) {
        
            this.no = no;
        }
    
        public String getName() {
        
            return name;
        }
    
        public void setName(String name) {
        
            this.name = name;
        }
    
        public Node getLeft() {
        
            return left;
        }
    
        public void setLeft(Node left) {
        
            this.left = left;
        }
    
        public Node getRight() {
        
            return right;
        }
    
        public void setRight(Node right) {
        
            this.right = right;
        }
    
        @Override
        public String toString() {
        
            return "Node{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
        //递归删除节点
        //1、如果删除的是叶子节点，则删除该节点
        //2、如果删除的是非叶子节点，则删除该子树
        public void delete(int no){
        
            if (this.left != null && this.left.no == no){
        
                //如果删除的节点就是该节点的左子节点，让他的左子节点置null
                this.left = null;
                return;
            }
            if (this.right != null && this.right.no == no){
        
                //如果删除的节点就是该节点的右子节点，让他的右子节点置null
                this.right = null;
                return;
            }
            //如果删除的节点不是当前节点，需要向当前节点的左子树进行递归遍历，找到它并删除删除
            if (this.left != null){
        
                this.left.delete(no);
            }
    
            //不要怀疑为什么是当前节点，因为刚开始递归的时候当前节点就是根节点
            //如果删除的节点不是当前节点并且不是其左子节树的节点，需要向其右子树进行递归遍历，找到它并删除删除
            if (this.right != null){
        
                this.right.delete(no);
            }
        }
    
        //前序遍历
        public void preOrder(){
        
            System.out.println(this); //先输出父节点
            //递归向左子树的遍历
            if (this.left !=null){
        
                this.left.preOrder();
            }
            //递归向左子树的遍历
            if (this.right !=null){
        
                this.right.preOrder();
            }
    
        }
        //中序遍历
        public void infixOrder(){
        
            //递归向左子树的遍历
            if (this.left !=null){
        
                this.left.infixOrder();
            }
            System.out.println(this); //先输出父节点
            //递归向左子树的遍历
            if (this.right !=null){
        
                this.right.infixOrder();
            }
        }
        //后序遍历
        public void postOrder(){
        
            //递归向左子树的遍历
            if (this.left !=null){
        
                this.left.postOrder();
            }
            //递归向左子树的遍历
            if (this.right !=null){
        
                this.right.postOrder();
            }
            System.out.println(this); //先输出父节点
        }
    
        /**
         * 前序遍历查找
         *
         * @param no 编号
         * @return 如果找到就返回Node，如果没有找到就返回null
         */
        public Node preOrderSearch(int no){
        
    
            System.out.println("遍历查找次数");
            //比较当前节点的no等于传入的no
            if (this.no == no){
        
                return this;
            }
            //1、判断当前节点是否为null，如果不为null，就前序递归遍历
            //2、如果左递归前序查找，找到节点，直接返回
            Node resNode = null;
            if ( this.left != null){
        
                resNode = this.left.preOrderSearch(no);
            }
            if (resNode != null){
          //说明左递归找打节点了
                return resNode;
            }
            //1、左递归前序查找，找到节点，则返回，否则继续判断
            //2、当前节点的右子节点是否为null，如果不为null，则继续向右递归前序查找
            if (this.right != null){
        
                resNode = this.right.preOrderSearch(no);
            }
            return resNode;
    
        }
    
        /**
         * 中缀顺序搜索
         *
         * @param no 编号
         * @return 如果找到就返回Node，如果没有找到就返回null
         */
        public Node infixOrderSearch(int no){
        
    
            //1、判断当前节点的左子节点是否为null，如果不为null，就递归中序查找
            Node resNode = null;
            if ( this.left != null){
        
                resNode = this.left.infixOrderSearch(no);
    
            }
            //2、如果左递归前序查找，找到节点，直接返回
            if (resNode != null){
          //说明左递归找打节点了
                return resNode;
            }
            System.out.println("遍历查找次数");
            //如果找到，则返回，如果没有找到，就和当前节点比较，如果是则返回当前节点
            if (this.no == no){
        
                return this;
            }
    
            //否则继续进行右递归的中序查找
            if (this.right != null){
        
                resNode = this.right.infixOrderSearch(no);
            }
            return resNode;
    
        }
        /**
         * 后序查找
         *
         * @param no 编号
         * @return 如果找到就返回Node，如果没有找到就返回null
         */
        public Node postOrderSearch(int no){
        
    
            //1、判断当前节点的左子节点是否为null，如果不为null，就递归后序遍历
            Node resNode = null;
            if ( this.left != null){
        
                resNode = this.left.postOrderSearch(no);
    
            }
            if (resNode != null){
          //说明左递归找打节点了
                return resNode;
            }
    
            //如果左子树没有找到，则向右子树进行后序遍历查找
            if (this.right != null){
        
                resNode = this.right.postOrderSearch(no);
            }
            if (resNode != null){
          //说明左递归找打节点了
                return resNode;
            }
            System.out.println("遍历查找次数");
            //如果左右子树都没有找到，就比较当前节点
            //比较当前节点的no等于传入的no
            if (this.no == no){
        
                return this;
            }
            //树中没有该节点就返回null
            return null;
    
        }
    
    
    }

#### 本次二叉树教程出自韩顺平的数据结构与算法 ####

[数据结构和算法教程][Link 1]，哔哩哔哩详细教程  
在 91-99p.

最后，认识一下，我是小白。努力成为一名合格的程序员。期待与你的下次相遇。

[img-jidZhDbY-1662035409016_C_Users_86139_AppData_Roaming_Typora_typora-user-images_image-20220831193440496.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/79c2efb7321942da9d5cd7f8bc3c9866.png
[img-fYH93ong-1662035409017_C_Users_86139_AppData_Roaming_Typora_typora-user-images_image-20220831194314378.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d46c384e24d04a51944255d0e563f8e1.png
[d6c6809e5ccf4150a9188ee355152d4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7ce4631a1238400290768162cbee0f5d.png
[fe4c06e43bb5471dab00857118f494ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8f5744daa3cc46fdb0f35bf5e82073a3.png
[f34a70b654704af39fc1e0ecfebc22c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/28a84936220041e88781103ceb776200.png
[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=71&spm_id_from=pageDriver&vd_source=027fde985896626031abccc06ce8b031