二叉树查询，遍历代码实现

以你之姓@ 2024-04-19 15:54 59阅读 0赞

> # 二叉树的概念 #

*  1)如果该二叉树的**所有****叶****子节点都在最后一层**，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
 *  2)如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

> # **二叉树遍历** #

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

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

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

**小结**: 看输出父节点的顺序，就确定是前序，中序还是后序

**思路：**

**前序遍历**

//编写前序遍历的方法
        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);
        }

> # **二叉树查找思路分析** #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70][]

public HeroNode preOrderSearch(int no) {
            System.out.println("进入前序遍历");
            //比较当前结点是不是
            if(this.no == no) {
                return this;
            }
            //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
            //2.如果左递归前序查找，找到结点，则返回
            HeroNode resNode = null;
            if(this.left != null) {
                resNode = this.left.preOrderSearch(no);
            }
            if(resNode != null) {//说明我们左子树找到
                return resNode;
            }
            //1.左递归前序查找，找到结点，则返回，否继续判断，
            //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
            if(this.right != null) {
                resNode = this.right.preOrderSearch(no);
            }
            return resNode;
        }

> # ** 删除结点思路** #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 1][]

##    **思路** ##

*              1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点  是不是需要删除结点.
 *              2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
 *              3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
 *              4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
 *              5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.

public void delNode(int no) {
    
            //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
            if(this.left != null && this.left.no == no) {
                this.left = null;
                return;
            }
            //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
            if(this.right != null && this.right.no == no) {
                this.right = null;
                return;
            }
            //4.我们就需要向左子树进行递归删除
            if(this.left != null) {
                this.left.delNode(no);
            }
            //5.则应当向右子树进行递归删除
            if(this.right != null) {
                this.right.delNode(no);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d7c9e0ab71484c4bbb6d93e5bb89c57d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9b54f2b33520494c8259c109baf6b6a9.png