二叉树（前序，中序，后序遍历和查找，删除）详解

谁践踏了优雅 2023-07-09 02:23 54阅读 0赞

### 为什么需要树这种数据结构 ###

1.  数组存储方式的分析：
    
    > 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。  
    > 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低
2.  链式存储方式的分析
    
    > 优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。  
    > 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)
3.  树存储方式分析：
    
    > 能够提高数据存储，读取的效率，比如二叉排序树（Binary Sort Tree）, 即可以保证数据的检索速度，同时也可以保证数据的查找，修改，删除速度。

### 树示意图即常用术语 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]  
树的常用术语(结合示意图理解):

> 1.  节点
> 2.  根节点
> 3.  父节点
> 4.  子节点
> 5.  叶子节点 (没有子节点的节点)
> 6.  节点的权(节点值)
> 7.  路径(从root节点找到该节点的路线)
> 8.  层
> 9.  子树
> 10. 树的高度(最大层数)
> 11. 森林 :多颗子树构成森林

## 二叉树 ##

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

1.  树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
2.  二叉树的子节点分为左子节点和右子节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 1]
3.  如果该二叉树的所有叶子节点都在最后一层，并且节点总数=2^n-1，n为层数，则我们称为满二叉树
4.  如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

### 二叉树的遍历，查找，删除 ###

二叉树有前序遍历，中序遍历，后序遍历，  
前序遍历：**先输出父节点**，在遍历左子树和右子树  
中序遍历：先遍历左 子树，**在遍历父节点**，在遍历右子树

二叉树也有前序查找，中序查找，和后序查找方法

**代码示例**：  
要求如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 2]

看上图：  
遍历：

> 1.  使用前序，中序，后序遍历，请写出各自输出的顺序是什么?

查找：

> 请编写前序查找，中序查找和后序查找的方法。并分别使用三种查找方式，查找 heroNO = 5 的节点，

删除：

> 1.  如果删除的节点是叶子节点，则删除该节点
> 2.  如果删除的节点是非叶子节点，则删除该子树.
> 3.  测试，删除掉 5号叶子节点 和 3号子树.

代码实现如下：

节点类(代码有详细注释)：

public class HeroNode { 
        private int id;
        private String name;
        // 左子节点
        public HeroNode left;
        public HeroNode right;
    
        public HeroNode(int id, String name) { 
            this.id = id;
            this.name = name;
        }
    
        public int getId() { 
            return id;
        }
    
        public void setId(int id) { 
            this.id = id;
        }
    
        public String getName() { 
            return name;
        }
    
        public void setName(String name) { 
            this.name = name;
        }
    
        @Override
        public String toString() { 
            return "HeroNode{" +
                    "id=" + id +
                    ", 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 midOrder(){ 
            // 判断当前节点的左子节点是否为空，不为空则递归
            if (this.left != null) { 
                this.left.midOrder();
            }
            // 输出当前节点
            System.out.println(this);
            // 在判断当前节点的右子节点是否为空，不为空则递归
            if (this.right != null) { 
                this.right.midOrder();
            }
        }
    
        /** * 后序遍历 */
        public void postOrder() { 
            // 判断当前节点的左子节点不为空，则递归
            if (this.left != null) { 
                this.left.postOrder();
            }
            // 判断当前节点的右子节点不为空，则递归
            if (this.right != null) { 
                this.right.postOrder();
            }
            // 最后输出当前节点
            System.out.println(this);
        }
    
        /** * 前序查找 * @param heroNo * @return */
        public HeroNode preSearch(int heroNo) { 
            // 如果当前节点就是要找的节点，则直接返回
            if (this.getId() == heroNo) { 
                return this;
            }
    
            HeroNode res = null;
            // 如果当前节点的左子节点不为空，则递归查找
            if (this.left != null) { 
                res = this.left.preSearch(heroNo);
            }
            // 如果通过左子节点找到则直接返回
            if (res != null) { 
                return res;
            }
    
            // 如果当前节点的右子节点不为空，则递归查找
            if (this.right != null) { 
                res = this.right.preSearch(heroNo);
            }
            return res;
        }
    
        /** * 中序查找 * @param heroNo * @return */
        public HeroNode midSearch(int heroNo) { 
            // 如果当前节点的左子节点不为空，则递归查找
            HeroNode res = null;
            if (this.left != null) { 
                res = this.left.midSearch(heroNo);
            }
            // 如果通过左子节点递归已经找到了，则直接返回，不用继续找下去了
            if (res != null) { 
                return res;
            }
    
            // 如果当前节点就是要找的节点，则直接返回
            if (this.getId() == heroNo) { 
                return this;
            }
    
            // 如果当前节点的右子节点不为空，则递归查找
            if (this.right != null) { 
                res = this.right.midSearch(heroNo);
            }
            return res;
        }
    
        /** * 后序查找 * @param heroNo * @return */
        public HeroNode postSearch(int heroNo) { 
            HeroNode res = null;
            // 如果当前节点的左子节点不为空，则递归查找
            if (this.left != null) { 
                res = this.left.postSearch(heroNo);
            }
            // 如果通过左子节点递归查找已经找到，则直接返回，
            if (res != null) { 
                return res;
            }
    
            // 如果当前节点的右子节点不为空，则递归查找
            if (this.right != null) { 
                res = this.right.postSearch(heroNo);
            }
            // 如果通过右子节点递归找到，则直接返回
            if (res != null) { 
                return res;
            }
    
            // 如果当前节点就是要找的节点，则直接返回
            if (this.getId() == heroNo) { 
                return this;
            }
            return res;
        }
    
        /** * 删除节点 * 说明：删除二叉树节点，就是把要删除节点的父节点指向自己的引用置空 * @param heroNo */
        public void delHeroNode(int heroNo) { 
            // 因为二叉树是单向的，当前节点不能删除自己，只能删除其左子节点或右子节点
            // 如果当前节点的左子节点不为空，且其左子节点就是要删除的节点,则把其左子节点置空
            if (this.left != null && this.left.getId() == heroNo) { 
                this.left = null;
                return;
            }
    
            // 如果当前节点的右子节点不为空，且其左子节点就是要删除的节点，则把其右子节点置空
            if (this.right != null && this.right.getId() == heroNo) { 
                this.right = null;
                return;
            }
    
            // 如果其左子节点和右子节点都不是要删除的节点，则递归继续其子节点的查找删除
            if (this.left != null) { 
                this.left.delHeroNode(heroNo);
            }
            if (this.right != null) { 
                this.right.delHeroNode(heroNo);
            }
        }
    }

二叉树类：

public class BinaryTree { 
        private HeroNode root;
    
        public HeroNode getRoot() { 
            return root;
        }
    
        public void setRoot(HeroNode root) { 
            this.root = root;
        }
    
        /** * 前序遍历 */
        public void preOrder() { 
            if (root == null) { 
                System.out.println("该二叉树为空树");
                return;
            }
            this.root.preOrder();
        }
    
        /** * 后序遍历 */
        public void midOrder(){ 
            if (root == null) { 
                System.out.println("该二叉树为空树");
                return;
            }
            this.root.midOrder();
        }
    
        /** * 后序遍历 */
        public void postOrder(){ 
            if (root == null) { 
                System.out.println("该二叉树为空树");
                return;
            }
            this.root.postOrder();
        }
    
        /** * 前序查找 * @param heroNo * @return */
        public HeroNode preSearch(int heroNo){ 
            if (root == null ) { 
                return null;
            }
           return root.preSearch(heroNo);
        }
    
        /** * 中序查找 * @param heroNo * @return */
        public HeroNode midSearch(int heroNo){ 
            if (root == null) { 
                return null;
            }
            return root.midSearch(heroNo);
        }
    
        /** * 后序查找 * @param heroNo * @return */
        public HeroNode postSearch(int heroNo) { 
            if (root == null) { 
                return null;
            }
            return root.postSearch(heroNo);
        }
    
        /** * 删除节点 * @param heroNo */
        public void delNode(int heroNo) { 
            // 判断根节点是否是要删除的节点
            if (root == null) { 
                System.out.println("当前二叉树为空。");
                return;
            }
            if (root.getId() == heroNo) { 
                root =null;
                return;
            }
            root.delHeroNode(heroNo);
        }
    }

测试类：

public class MyTest { 
        public static void main(String[] args) { 
            HeroNode node1 = new HeroNode(1, "宋江");
            HeroNode node2 = new HeroNode(2, "吴用");
            HeroNode node3 = new HeroNode(3, "卢俊义");
            HeroNode node4 = new HeroNode(4, "林冲");
            HeroNode node5 = new HeroNode(5, "关胜");
    
            BinaryTree binaryTree = new BinaryTree();
            node1.left = node2;
            node3.left = node5;
            node3.right = node4;
            node1.right = node3;
            binaryTree.setRoot(node1);
    
            // 前序遍历，预期结果：1，2，3，5,4
            System.out.println("前序遍历：");
            binaryTree.preOrder();
    
            // 中序遍历,预期结果：2，1，5,3,4
            System.out.println("中序遍历：");
            binaryTree.midOrder();
    
            // 后序遍历，预计结果：2,5,4,3,1
            System.out.println("后序遍历：");
            binaryTree.postOrder();
    
            // 前序查找，
            System.out.println("-------查找测试--------------");
            System.out.println("前序查找:");
            HeroNode res1 = binaryTree.preSearch(5);
            System.out.println("查找到编号为5的英雄为：" + res1);
    
            System.out.println("中序查找：");
            HeroNode res2 = binaryTree.midSearch(5);
            System.out.println("查找到编号为5的英雄为：" + res2);
    
            System.out.println("后序查找：");
            HeroNode res3 = binaryTree.midSearch(5);
            System.out.println("查找到编号为5的英雄为：" + res3);
    
            System.out.println("-----删除节点测试------");
            System.out.println("删除五号节点后前序遍历预计结果：1,2,3,4");
            binaryTree.delNode(5);
            System.out.println("输出结果：");
            binaryTree.preOrder();
            System.out.println("删除3号节点后前序遍历预计结果：1， 2");
            binaryTree.delNode(3);
            System.out.println("输出结果：");
            binaryTree.preOrder();
        }
    }

运行结果：

前序遍历：
    HeroNode{ id=1, name='宋江'}
    HeroNode{ id=2, name='吴用'}
    HeroNode{ id=3, name='卢俊义'}
    HeroNode{ id=5, name='关胜'}
    HeroNode{ id=4, name='林冲'}
    中序遍历：
    HeroNode{ id=2, name='吴用'}
    HeroNode{ id=1, name='宋江'}
    HeroNode{ id=5, name='关胜'}
    HeroNode{ id=3, name='卢俊义'}
    HeroNode{ id=4, name='林冲'}
    后序遍历：
    HeroNode{ id=2, name='吴用'}
    HeroNode{ id=5, name='关胜'}
    HeroNode{ id=4, name='林冲'}
    HeroNode{ id=3, name='卢俊义'}
    HeroNode{ id=1, name='宋江'}
    -------查找测试--------------
    前序查找:
    查找到编号为5的英雄为：HeroNode{ id=5, name='关胜'}
    中序查找：
    查找到编号为5的英雄为：HeroNode{ id=5, name='关胜'}
    后序查找：
    查找到编号为5的英雄为：HeroNode{ id=5, name='关胜'}
    -----删除节点测试------
    删除五号节点后前序遍历预计结果：1,2,3,4
    输出结果：
    HeroNode{ id=1, name='宋江'}
    HeroNode{ id=2, name='吴用'}
    HeroNode{ id=3, name='卢俊义'}
    HeroNode{ id=4, name='林冲'}
    删除3号节点后前序遍历预计结果：1， 2
    输出结果：
    HeroNode{ id=1, name='宋江'}
    HeroNode{ id=2, name='吴用'}

运行结果和预期的完全一样，结果完全正确，以上示例就是二叉树的前序，中序，后序遍历和前序，中序，后序查找，还有二叉树的删除。

**注意**：  
以上代码不好理解的地方就是二叉树的**遍历，查找，删除的递归调用**，对照着图可以很好的理解二叉树的遍历，查找和删除递归的调用过程。不过想要很好的理解二叉树的递归调用过程一定要自己动手写一遍代码，必要时可以debug追下代码的调用过程加深理解

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200227152114655.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200227160352585.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200227172443720.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70