        二叉树是一种常用的树结构。

        对于树，我们称每一个节点的子节点个数为度；

        二叉树就是任意一个度小于等于2树，也就是说，二叉树中任意节点的子节点个数小于等于2；

二叉查找树是指按照一定规则次序排列的二叉树，这种二叉树左子树的任意节点的值小于当前节点，右子树的任意节点的值大于当前节点，二叉查找树中不能有重复数据。

这是我通过随意数据画出的二叉查找树，之后的操作都将用这组数据作为测试；
7,7,4,5,3,2,8,1,1,9,22；

如图可以观察出二叉查找树的特点：任意节点的子节点个数小于等于2 且左子树的任意节点的值小于当前节点，右子树的任意节点的值大于当前节点。

专有名词

以上是树的一些专有名词。

二叉树的数据节点结构

结构代码


class Node{
    class Node {
    private int val;//储存节点的数据
    private Node left;//储存该节点的左子节点
    private Node right;//储存该节点的右子节点
 
    public Node(int val) {
        this.val = val;
    }//赋值构造器
 
    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
 
    //以下是获取该节点信息的方法
    public int getVal() {
        return val;
    }
 
    public void setVal(int val) {
        this.val = val;
    }
 
    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;
    }
}

管理二叉树的类

为了方便对二叉树的操作，我定义一个用来管理二叉树的类 class ChargeTree


class ChargeTree {
    private Node root;//二叉树的根节点
 
    public ChargeTree() {
 
    }//因为创建时不需要给二叉树赋任何值所以用了各无参构造器
 
    //获取根节点的方法
    public Node getRoot() {
        return root;
    }
 
    public void setRoot(Node root) {
        this.root = root;
    }
}

之后的增，查，遍历等操作方法都写在这个类中。

二叉树的遍历

所有类型的二叉树通用的遍历方法；

前序遍历

遍历顺序：打印当前节点 --> 遍历左子树节点 --> 遍历右子树节点；

注意动词！

参照上图：

从根节点 7进入，7 作为当前节点先打印出来（打印当前节点）；

7 的左子树不为null，所以向 7 的左子树遍历；（遍历左子树节点）

4 作为当前节点打印出来；（打印当前节点）

4 的左子树不为null，所以向 4 的左子树遍历；（遍历左子树节点）

3 作为当前节点打印；（打印当前节点）

由此类推，直到打印完 1 ，发现没有左子树和右子树，开始返回到节点2 ；（递归的返回）

对于节点2来说，当前节点打印过了，左子树也遍历完了，该遍历右子树了；（遍历右子树节点）

但 2 的右子树为null，那就跳过这一步骤，再返回到 3 ；（递归的返回）

3 也是同样的情况，3 的右子树为null，继续返回到4；（递归的返回）

4 的右子树不为空，向 4 的右子树遍历；

遍历到 5 成为当前节点，打印出来；（打印当前节点）

5 的左子树和右子树都为null，只能返回到 4 ；（递归的返回）

4 的三步已经完成，返回到 7；（递归的返回）

7 的右子树不为空，继续遍历；（遍历右子树节点）

……

预测的打印顺序：7，4，3，2，1，5，8，22，9

代码实现：采用递归，子问题为打印当前节点，遍历左子树，再遍历右子树；


 //前序遍历  
 public void preOrder2(Node cur){
        if(this.root == null){
            System.out.println("树为空");
            return;
        }
        System.out.println(cur);
        if(cur.getLeft() != null){
            preOrder2(cur.getLeft());
        }
        if(cur.getRight() != null){
            preOrder2(cur.getRight());
        }
    }

测试代码


System.out.println("----------------前序遍历-------------------");
 
tree.preOrder2(tree.getRoot());

测试数据：7,7,4,5,3,2,8,1,1,9,22；

测试结果：

中序遍历

再二叉查找树中中序遍历是最常用的；因为二叉查找树有中序遍历出来的结果是按照由小到大的顺序排列好的；

遍历顺序：遍历左子树节点 --> 打印当前节点 --> 遍历右子树节点；

过程就不再讲解，和前序遍历一样。

测试数据：7,7,4,5,3,2,8,1,1,9,22；

预测打印出来的结果：1 2 3 4 5 7 8 9 22；

代码实现：同样是递归


    //中序遍历
    public void inOrder2(Node cur){
        if(this.root == null){
            System.out.println("树为空");
            return;
        }
        if(cur.getLeft() != null){
            inOrder2(cur.getLeft());
        }
        System.out.println(cur);
        if(cur.getRight() != null){
            inOrder2(cur.getRight());
        }
    }

测试代码：


        System.out.println("----------------中序遍历-------------------");
        tree.inOrder2(tree.getRoot());

测试结果：

后序遍历

遍历顺序：遍历左子树节点 --> 遍历右子树节点 --> 打印当前节点；

测试数据：7,7,4,5,3,2,8,1,1,9,22；

预期打印结果：1 2 3 5 4 9 22 8 7；

代码实现：递归思想


    //后序遍历
    public void postOrder2(Node cur){
        if(this.root == null){
            System.out.println("树为空");
            return;
        }
        if(cur.getLeft() != null){
            postOrder2(cur.getLeft());
        }
        if(cur.getRight() != null){
            postOrder2(cur.getRight());
        }
        System.out.println(cur);
    }

测试代码：


System.out.println("----------------后序遍历-------------------");
        tree.postOrder2(tree.getRoot());

测试结果：

层序遍历

层序遍历是按照一层一层，每层从左至右依次遍历的；

层序遍历利用了队列先进先出的特性；

最开始将根节点 7 存入队列，之后进入循环，每删除一个节点就记录它的两个子节点进入队尾；

直到队列为空时，二叉树所有元素遍历完成；

测试数据：7,7,4,5,3,2,8,1,1,9,22；

预测打印结果：7 4 8 3 5 22 2 9 1；

代码实现：


    //层序遍历
    public void floorOrder() {
        if (this.root == null) {
            System.out.println("树为空");
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node ret = queue.poll();
            System.out.println(ret);
            if (ret.getLeft() != null) {
                queue.offer(ret.getLeft());
            }
            if (ret.getRight() != null) {
                queue.offer(ret.getRight());
            }
        }
    }

测试代码：


        System.out.println("----------------层序遍历-------------------");
        tree.floorOrder();

测试结果：

计算二叉树中节点的总个数

方法一：遍历 + 计数

在类中定义一个整型表示计数；

将刚才的遍历方法中的打印语句替换成一个计数语句即可；


class ChargeTree{
    private int count;
 
        //方法一：中序遍历 + 计数
    public int size1B(Node cur){
        if(cur.getLeft() != null){
            inOrder2(cur.getLeft());
        }
        this.count++;
        if(cur.getRight() != null){
            inOrder2(cur.getRight());
        }
        return this.count;
    }
}

依旧是用原来的数据测试（7,7,4,5,3,2,8,1,1,9,22；）

就算去掉重复的一个 7 和一个 1也应该有9 个节点啊？

注意

问题1：这里的 count必须用static修饰，因为函数的实现过程用到了递归，递归每进行一次相当于实例化了一个对象然后使用里面的count字段；所以每次实例化count都会清0；

用 static 修饰的话，count就变成了类的属性，类的字段，每次使用count++的时候，count在类（模板）里面的值就会改变，实例化的时候也就不会清0；

修改过后


class ChargeTree{
    private static int count;
 
        //方法一：中序遍历 + 计数
    public int size1B(Node cur){
        if(cur.getLeft() != null){
            inOrder2(cur.getLeft());
        }
        this.count++;
        if(cur.getRight() != null){
            inOrder2(cur.getRight());
        }
        return this.count;
    }
}

再次测试

此时的结果好像是正常了……

问题2：如果我对该树进行了增加或删除的操作导致结点的数量改变；当我想要重新计算结点的总数时，count因为用static修饰了，所以保持着之前的值，count++就不是在0的基础上加了；计算出的结果肯定有问题；

尝试调用两次计数节点

果然出问题了

原因是：我们虽然不希望count在每次递归的时候重置，但每次计算二叉树总结点个数的时候又不得不重置。

解决方法：我们可以设置一个中间方法，用来将count重置，充值后再调用计算二叉树总结点数的方法。

最终结果


class ChargeTree{
    private static int count;
 
        //方法一：中序遍历 + 计数
    public int size1(Node cur){
        if(this.root == null){
            System.out.println("树为空");
            return 0;
        }
        this.count = 0;
        return size1B(cur);
    }  
    public int size1B(Node cur){
        if(cur.getLeft() != null){
            size1B(cur.getLeft());
        }
        this.count++;
        if(cur.getRight() != null){
            size1B(cur.getRight());
        }
        return this.count;
    }
}

方法二：递归子问题总节点个数 = 该节点的左子树节点个数 + 该节点的右子树节点个数 + 1（当前节点）

用这个方法更容易实现；

代码实现：


    public int size2(Node cur) {
        if (cur == null) {
            return 0;
        }
        //如果节点为null，返回0
        int count = size2(cur.getLeft()) + size2(cur.getRight()) + 1;
        return count;
    }

二叉树中叶子节点个数

根据上一个问题 “计算二叉树中节点的总个数” 可以总结出计数结点的规则。

基本方法：遍历 + 计数；
用 static 修饰类中记录节点数量的变量（count）；
用中间函数实现数为空的判断和 count 的重置。

叶子节点计数问题也是采用同样的方法，不一样的只是需要加一个判断是叶子结点的语句。

叶子结点的特点是左子树为空，右子树也为空；


    class Main{
    public static int count2;
    public int leavesNode(Node cur){
        if(this.root == null){
            System.out.println("树为空");
            return 0;
        }
        this.count2 = 0;
        return leavesNodeB(cur);
    }
    public int leavesNodeB(Node cur){
        if(cur.getLeft() != null){
            leavesNode(cur.getLeft());
        }
        if(cur.getLeft() == null && cur.getRight() == null){
            System.out.println(cur);
            this.count2++;
        }
        if(cur.getRight() != null){
            leavesNode(cur.getRight());
        }
        return this.count2;
    }
    }

获取第K层的节点个数

获取第 K 层节点个数并返回第 k 层节点数据


   
    //递归： 子问题 一层的节点个数 = 上一层所有的父节点的 左子节点个数 + 右子节点个数
    public int floorNodeCount(Node cur, int k) {
        if (cur == null) {
            return 0;
        }//当前节点为空，没有节点返回0
        if (k == 1) {
            System.out.println(cur);//打印第k层节点
            return 1;
        }//第k层的1个节点，返回1；
        return floorNodeCount(cur.getLeft(), k - 1) + floorNodeCount(cur.getRight(), k - 1);
 
    }

递归思想是下一层的节点数 = 该层所有父节点的左子树节点个数 + 右子树节点个数；

在编写递归函数的时候：

设想 floorNodeCount(Node cur, int k)函数的功能是求树的K层节点的个数；

这个问题拆解为求左子树的K层节点个数和右子树的K层节点个数；

直到当K == 1 时，当前所在层就是第k层。

实际运行更像是将每条路径一直走到第K层（当 k==1 时），如果存在节点返回1；如果不存在（cur == null）则返回0；（深度优先搜索）

换言之当k == 1时就已经将一条路径走到了第k层，所以当k == 1时可以打印出第k层节点数据；

二叉树的高度


    //二叉树的高度
 
    //递归：子问题  求左子树高度与右子树高度作比较 取较高者 +1（父节点）
    public int treeHigh(Node cur) {
        if (cur == null) {
            return 0;
        }
        return Math.max(treeHigh(cur.getLeft()), treeHigh(cur.getRight())) + 1;
        //取左子树和右子树较大高度 +1
    }

添加节点

一次添加一个节点

非递归实现：

根据二叉查找树的特性，添加节点会从根节点开始一次比较遍历：

如果当前节点的值大于要添加的值，那么向左子树遍历；

如果当前节点的值小于要添加的值，那么向右子树遍历；

如果当前节点的值等于要添加的值，那么不添加；

直到遍历到叶子节点，将要添加的数据赋给新的节点，并连接到叶子节点的后面；


    //排序二叉树（二叉查找树）的节点添加
    //非递归实现
    public void add(int val) {
        Node newNode = new Node(val);
        if (this.root == null) {
            this.root = new Node(val);
            return;
        }
        Node m = root;
        while (true) {
            if (val < m.getVal()) {
                if (m.getLeft() != null) {
                    m = m.getLeft();
                    continue;
                } else {
                    m.setLeft(newNode);//添加成功，退出循环
                    return;
                }
            } else if (val > m.getVal()) {
                if (m.getRight() != null) {
                    m = m.getRight();
                    continue;
                } else {
                    m.setRight(newNode);//添加成功，退出循环
                    return;
                }
            } else {
                System.out.println("元素 " + val + " 已存在");
                //元素已存在
                return;
            }
        }
    }

递归实现：

把握好递归条件，条件和非递归的一样，判断当前结点的数据与要添加的数据的大小关系；

完成深搜递归。


    public void add(Node cur, int val) {
        if(this.root == null){
            root = new Node(val);
            return;
        }
        if (cur.getVal() == val) {
            System.out.println("元素 " + val + "已存在");
            return;
        }
        //满足添加条件
        if (cur.getLeft() == null && val < cur.getVal()) {
            cur.setLeft(new Node(val));
            return;
        }
        if (cur.getRight() == null && val > cur.getVal()) {
            cur.setRight(new Node(val));
            return;
        }
        if (val < cur.getVal()) {
            add(cur.getLeft(), val);
        } else if (val > cur.getVal()) {
            add(cur.getRight(), val);
        }
    }

一次添加多个节点

规则都一样，不一样的只是利用了可变参数，相当于一个数组；


    public void addAll(int... val) {
        //利用可变参数；远离相当于创建了一个数组
        int k = 0;//记录第一个元素应添加下标
        //如果根节点的数据是新赋值的，则val中第一个数据赋给根节点（特判），其他数据正常赋值
        //如果不是新的，那么val中所有数据正常赋值
        if (this.root == null) {
            this.root = new Node(val[0]);
            k = 1;//再给子节点赋值的时候跳过第一个根据节点利用过的数据
        }
        for (int i = k; i < val.length; i++) {
            Node m = root;
            while (true) {
                if (val[i] < m.getVal()) {
                    if (m.getLeft() != null) {
                        m = m.getLeft();
                        continue;
                    } else {
                        m.setLeft(new Node(val[i]));
                        break;
                    }
                } else if (val[i] > m.getVal()) {
                    if (val[i] > m.getVal()) {
                        if (m.getRight() != null) {
                            m = m.getRight();
                            continue;
                        } else {
                            m.setRight(new Node(val[i]));
                            break;
                        }
                    }
                } else {
                    System.out.println("元素 " + val[i] + " 已存在");
                    break;
                }
            }
        }
    }

查找结点

非递归：

步骤和添加节点类似


    //1.非递归
    public Node query(int target) {
        if (this.root == null) {
            return null;
        }
        Node m = this.root;
        while (true) {
            if (target == m.getVal()) {
                return m;
            } else if (target < m.getVal()) {
                if (m.getLeft() != null) {
                    m = m.getLeft();
                    continue;
                } else {
                    return null;
                }
            } else {
                if (m.getRight() != null) {
                    m = m.getRight();
                    continue;
                } else {
                    return null;
                }
            }
        }
    }

递归：


    //2.递归 分为左右树递归查询
    public Node query(Node cur, int target) {
        if (cur == null) {
            return null;
        }
        if (cur.getVal() == target) {
            //如果当前节点是目标值
            return cur;
        }
        //在左子树中查找
        if (target < cur.getVal()) {
            Node ret = query(cur.getLeft(), target);
            if (ret != null) {
                //找到了  返回
                return ret;
            }
        }
        //在右子树中查找
        if (target > cur.getVal()) {
            Node ret = query(cur.getRight(), target);
            if (ret != null) {
                //找到了  返回
                return ret;
            }
        }
        //左右树中都没有找到
        return null;
    }

删除节点

删除节点分为以下几种情况：

要删除的节点不存在；
要删除的节点是叶子节点（没有左子树和右子树），这种可以直接删除；
要删除的节点左子树和右子树有一个为空，这种的需要跳过该节点，返回该节点不为空的一棵子树；
要删除的节点左子树和右子树都不为空，

这种的需要先将左子树继承到右子树中最小的节点上，然后直接跳过该节点，返回右子树（演示代码所采用的）；
或者将右子树继承到左子树最大的节点上，然后直接跳过该节点，返回左子树；

第4种情况，如果在这颗树中要删除的是4节点

先继承，后删除，结果为：

在这棵树中恰好4的右子树只有一个节点，那么他就作为右子树最小节点，连接4的左子树。

代码演示：


    //删除节点
 
    public Node remove(Node cur, int val){
        if(cur == null){
            return null;
        }
        if(cur.getVal() == val){
            //找到了要删除的节点
            if(cur.getLeft() == null && cur.getRight() == null){
                //叶子节点
                return null;
            }
            if(cur.getLeft() != null && cur.getRight() == null){
                //左子树不为空，右子树为空
                return cur.getLeft();
            }
            if(cur.getRight() != null && cur.getLeft() == null){
                //左子树为空，右子树不为空
                return cur.getRight();
            }
            if(cur.getLeft() != null && cur.getRight() != null){
                //左子树不为空，右子树不为空
                Node help = cur.getRight();
                //右孩子继承
                while(help.getLeft() != null){
                    help = help.getLeft();
                }//找到右子树中最小的（离cur的值最近的）节点
                help.setLeft(cur.getLeft());
                //将删除节点的左子树连接到help的左子树上
                //变成左子树为空，右子树不为空的情况
                return cur.getRight();
            }
        }//找到了要删除的节点
        if(cur.getVal() > val){
            cur.setLeft(remove(cur.getLeft(), val));
        }//遍历左子树查找
        if(cur.getVal() < val){
            cur.setRight(remove(cur.getRight(), val));
        }//遍历右子树查找
        return cur;
        //不需要删除则直接返回当前
    }

在编写递归函数的时候，函数的返回值类型是树节点Node，return可以表示结点的连接关系，return null就是上一个节点不连接任何东西了；return cur就是上一个节点连接到该节点；同理，return cur.getRight()和return cur.getLeft()就是上一个节点直接连接到当前节点的右子树或左子树。

这样就达到了删除的目的。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/275039?site