树的介绍以及应用

树的介绍以及应用

目录

一、树的介绍

        1、数组存储方式的分析

        2、分析链式存储方式的

         3、树存储方式的分析

 二、树的常用术语

三、二叉树的概念

四、二叉树的遍历

        1、二叉树的应用

        2、代码实现：

五、顺序存储二叉树

        1、基本说明

        2、 顺序存储二叉树的特点:

        3、应用：

        4、代码实现：

六、线索化二叉树

        1、 基本介绍

        2、应用案例：

        3、 思路分析：

          4、代码实现：    

        5、测试结果

七、堆排序

        1、基本介绍

        2、应用案例

        3、思路分析

         4、代码实现

        5、测试

 八、霍夫曼树

        1、基本介绍

        2、应用案例

        3、思路分析

        4、代码实现

        5、测试结果 

九、二叉排序树

       1、基本介绍

       2、案例应用

       3、代码实现

       4、二叉排序树的删除

       5、思路分析

       6、代码实现

       7、测试结果

       8、删除存在的问题

       9、解决办法 

---

一、树的介绍         1、数组存储方式的分析

                优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。         缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

        2、分析链式存储方式的

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

                缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历) 

         3、树存储方式的分析

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

 二、树的常用术语

 

        节点

        根节点

        父节点

        子节点

        叶子节点 (没有子节点的节点)

        节点的权(节点值)

        路径(从root节点找到某个节点的路线)

        层

        子树

        树的高度(最大层数)

        森林 :多颗子树构成森林

三、二叉树的概念

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

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

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

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

四、二叉树的遍历

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

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

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

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

 中序遍历：2-->1-->3-->4

 前序遍历：1-->2-->3-->4

后序遍历：2-->4-->3-->1

        1、二叉树的应用

        使用代码实现对上图的遍历，查找，删除 *** 作：

        思路：

               1、创建HeroNode类，定义每个节点的属性

                2、对HeroNode类实现前序，中序，后序遍历。前序，中序，后序查找，删除 *** 作

                3、创建二叉树

                4、对二叉树类实现前序，中序，后序遍历。前序，中序，后序查找，删除 *** 作

        2、代码实现：

         1、创建HeroNode类

//创建英雄类
class Heronode {
    private int no;
    private String name;
    private Heronode leftNode; //指向左子节点
    private Heronode rightNode; //指向右子节点

    public Heronode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", 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 Heronode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Heronode leftNode) {
        this.leftNode = leftNode;
    }

    public Heronode getRightNode() {
        return rightNode;
    }

    public void setRightNode(Heronode rightNode) {
        this.rightNode = rightNode;
    }

    //前序遍历
    public void preOrder() {
        //输出当前节点
        System.out.println(this);
        if (this.leftNode != null) {
            this.leftNode.preOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.preOrder();
        }
    }

    //中序遍历
    public void midOrder() {
        if (this.leftNode != null) {
            this.leftNode.midOrder();
        }
        //输出当前节点
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.midOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        //出书当前节点
        System.out.println(this);
    }

    //前序查找
    public Heronode preSearch(int no) {
        Heronode res = null; //保存返回值
        if (this.no == no) {
            //对当前节点进行判断
            return this;
        }
        //在左子树查找
        if (this.leftNode != null) {
            res = this.leftNode.preSearch(no);
        }
        //对res进行判断，不为空说明找到了该节点
        if (res != null) {
            return res;
        }
        //在右子树查找
        if (this.rightNode != null) {
            res = this.rightNode.preSearch(no);
        }
        return res;
    }

    //中序查找
    public Heronode midSearch(int no) {
        Heronode res = null;
        if (this.leftNode != null) {
            res = this.leftNode.midSearch(no);
        }
        //判断res是否为空
        if (res != null) {
            return res;
        }
        if (this.no == no) {
            return this;
        }

        if (this.rightNode != null) {
            res = this.rightNode.midSearch(no);
        }

        return res;
    }

    //后序查找
    public Heronode postSearch(int no) {
        Heronode res = null;
        if (this.leftNode != null) {
            res = this.leftNode.postSearch(no);
        }
        if (res != null) {
            return res;
        }
        if (this.rightNode != null) {
            res = this.rightNode.postSearch(no);
        }
        if (this.no == no) {
            return this;
        }
        return res;
    }

    
    public void delNode(int no) {
        if (this.leftNode != null && this.leftNode.no == no) {
            this.leftNode = null;
        }
        if (this.rightNode != null && this.rightNode.no == no) {
            this.rightNode = null;
        }
        if (this.leftNode != null) {
            this.leftNode.delNode(no);
        }
        if (this.rightNode != null) {
            this.rightNode.delNode(no);
        }
    }
}

        2、创建二叉树

//创建二叉树
class BinaryTree {
    private Heronode root;

    //创建root节点
    public void setRoot(Heronode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            root.preOrder();
        } else {
            System.out.println("没有root节点");
        }
    }

    //中序遍历
    public void midOrder() {
        if (this.root != null) {
            root.midOrder();
        } else {
            System.out.println("没有root节点");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            root.postOrder();
        } else {
            System.out.println("没有root节点");
        }
    }

    //前序查找
    public Heronode preSearch(int no) {
        if (this.root != null) {
            return this.root.preSearch(no);
        }
        return null;
    }

    //中序查找
    public Heronode midSearch(int no) {
        if (this.root != null) {
            return this.root.midSearch(no);
        }
        return null;
    }

    //后序查找
    public Heronode postSearch(int no) {
        if (this.root != null) {
            return this.root.postSearch(no);
        }
        return null;
    }

    //删除
    public void delNode(int no) {
        if (this.root != null) {
            this.root.delNode(no);
        } else {
            System.out.println("根节点为空");
        }
    }
}

        3、测试

  public static void main(String[] args) {
        //测试
        BinaryTree binaryTree = new BinaryTree();

        //创建节点
        Heronode root = new Heronode(1, "宋江");
        Heronode node2 = new Heronode(2, "吴用");
        Heronode node3 = new Heronode(3, "卢俊义");
        Heronode node4 = new Heronode(4, "林冲");
        Heronode node5 = new Heronode(5, "关胜"); //新加一个关胜在卢俊义的左边

        //我们向手动创建二叉树。后面学递归创建
        root.setLeftNode(node2);
        root.setRightNode(node3);
        node3.setRightNode(node4);
        node3.setLeftNode(node5);
        //将根节点传到二叉树
        binaryTree.setRoot(root);

        System.out.println("前序遍历"); // 1 2 3 4      1 2 3 5 4
        binaryTree.preOrder();

        System.out.println("中序遍历");//2 1 3 4        2 1 5 3 4
        binaryTree.midOrder();

        System.out.println("后序遍历"); // 2 4 3 1      2 5 4 3 1
        binaryTree.postOrder();

        System.out.println("前序查找" + binaryTree.preSearch(5));
        System.out.println("中序查找" + binaryTree.midSearch(5));
        System.out.println("后序查找" + binaryTree.postSearch(5));

        binaryTree.delNode(3);
        System.out.println("查找3" + binaryTree.postSearch(3));
    }

    4、结果：

前序遍历
HeroNode{no=1, name='宋江'}
HeroNode{no=2, name='吴用'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=5, name='关胜'}
HeroNode{no=4, name='林冲'}
中序遍历
HeroNode{no=2, name='吴用'}
HeroNode{no=1, name='宋江'}
HeroNode{no=5, name='关胜'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=4, name='林冲'}
后序遍历
HeroNode{no=2, name='吴用'}
HeroNode{no=5, name='关胜'}
HeroNode{no=4, name='林冲'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=1, name='宋江'}
前序查找HeroNode{no=5, name='关胜'}
中序查找HeroNode{no=5, name='关胜'}
后序查找HeroNode{no=5, name='关胜'}
查找3null

---

五、顺序存储二叉树         1、基本说明

从数据存储来看，数组存储方式和树 的存储方式可以相互转换，即数组可 以转换成树，树也可以转换成数组

        2、 顺序存储二叉树的特点:

         第 i 个元素的左子节点的下标为  2 * i + 1

        第 i 个元素的右子节点的下标为  2 * i + 2

        第 i 个元素的父节点的下标为  (i-1) / 2

        i 是数组下标。

        3、应用：

        请用数组的形式保存一组数据，如：[1,2,3,4,5,6,7]。但是遍历仍可以用前序遍历。中序遍历。后序遍历

        4、代码实现：

//顺序存储二叉树
class ArrayTree {
    private int[] arr;
    private int i; //表示数组下标

    public ArrayTree(int[] arr) {
        this.arr = arr;
    }

    //前序遍历
    public void preOrder(int i) {
        if (arr.length == 0) {
            System.err.println("数组为空");
            return;
        }
        System.out.print(arr[i] + "t");
        //左子节点
        if ((i * 2 + 1) < arr.length) {
            preOrder(i * 2 + 1);
        }
        //右子节点
        if ((i * 2 + 2) < arr.length) {
            preOrder(i * 2 + 2);
        }
    }

    //中序遍历
    public void midOrder(int i) {
        if (arr.length == 0) {
            System.err.println("数组为空");
            return;
        }
        if ((i * 2 + 1) < arr.length) {
            midOrder(i * 2 + 1);
        }
        System.out.print(arr[i] + "t");
        if ((i * 2 + 2) < arr.length) {
            midOrder(i * 2 + 2);
        }
    }
    //后序遍历
    public void postOrder(int i) {
        if (arr.length == 0) {
            System.err.println("数组为空");
            return;
        }
        if ((i * 2 + 1) < arr.length) {
            midOrder(i * 2 + 1);
        }
        if ((i * 2 + 2) < arr.length) {
            midOrder(i * 2 + 2);
        }
        System.out.print(arr[i] + "t");
    }
}

        测试：

public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrayTree arrayTree = new ArrayTree(arr);
        //前序遍历
        arrayTree.preOrder(0); //1	2	4	5	3	6	7
        //中序遍历
        System.out.println();
        arrayTree.midOrder(0);//4	2	5	1	6	3	7
        //后序遍历
        System.out.println();
        arrayTree.postOrder(0);//4	2	5	6	3	7	1

    }

六、线索化二叉树         1、 基本介绍

1、n个结点的二叉链表中含有n+1  【公式 2n-(n-1)=n+1】 个空指针域。每个结点都有俩个指针域【左右指针域，左指针指向前驱结点，右指针指向后继结点】，利用二叉链表中的空指针域，指向该结点在某种遍历次序下的前驱和后继结点（这种附加的指针称为"线索"）

2、这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

3、一个结点的前一个结点，称为前驱结点

        一个结点的后一个结点，称为后继结点

 如上图所示：

        一共有6个结点，有 7个空指针域，中序遍历为：【8 3 10 1 14 6】

        那么对于中序遍历来说：8 是 3 的前驱结点，10 是 3 的后继节点 

        2、应用案例：

将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}

        3、 思路分析：

 说明:

当线索化二叉树后，Node节点的 属性 left 指针和 right指针 ，有如下情况:

left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.

right指向的是右子树，也可能是指向后继节点，比如 ① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点.

          4、代码实现：    

        线索化二叉树遍历，不能用以前的遍历方法，因为各个结点的指向发生了改变。

//创建二叉树
class BinaryTree {
    //根节点
    private Heronode root;
    //前驱节点
    private Heronode pre = null;

    //创建root节点
    public void setRoot(Heronode root) {
        this.root = root;
    }

    //中序线索化遍历
    public void showMidThreaded() {
        //从root节点开始遍历
        Heronode node = root;
        while (node != null) {
            //循环找到leftType == 1的 结点
            while (node.getLeftType() == 0) {
                node = node.getLeftNode();
            }
            System.out.println(node);
            while (node.getRightType() == 1) {
                node = node.getRightNode();
                System.out.println(node);
            }
            node = node.getRightNode();
        }
    }

    //中序线索化--node表示从哪个结点开始线索化
    public void threadedNode(Heronode node) {
        //如果当前节点是null，无法线索化
        if (node == null) {
            return;
        }

        //一、先线索化左子树
        threadedNode(node.getLeftNode());
        //二、线索化当前节点
        // 1、处理前驱节点
        if (node.getLeftNode() == null) {
            //当前节点的左指针指向前驱节点，并修改 leftType
            node.setLeftNode(pre);
            node.setLeftType(1);
        }
        //处理后继节点
        if (pre != null && pre.getRightNode() == null) {
            //让当前节点成为前驱结点的后继节点，并修改 rightType
            pre.setRightNode(node);
            pre.setRightType(1);
        }
        //!!每处理过一个节点后，就让当前节点是下一节点的前驱节点
        pre = node;
        //三、线索化右子树
        threadedNode(node.getRightNode());
    }


}

//创建英雄类
class Heronode {
    private int no;
    private String name;
    private Heronode leftNode; 
    private Heronode rightNode; 
    //指定规则，当 leftType = 0 时，指向左子树，leftType = 1时，指向前驱结点
    private int leftType;
    //指定规则，当 rightType = 0 时，指向右子树，rightType = 1时，指向后继结点
    private int rightType;



    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + ''' +
                '}';
    }

    //get，set方法
    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public Heronode(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 Heronode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Heronode leftNode) {
        this.leftNode = leftNode;
    }

    public Heronode getRightNode() {
        return rightNode;
    }

    public void setRightNode(Heronode rightNode) {
        this.rightNode = rightNode;
    }
}

        5、测试结果

七、堆排序         1、基本介绍

                (1)、堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

                (2)、堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右子结点的值，称为大顶堆, 注意 : 没有要求结点的左子结点的值和右子结点的值的大小关系。

                (3)、每个结点的值都小于或等于其左右子结点的值，称为小顶堆

                        每个结点的值都大于或等于其左右子结点的值，称为大顶堆

 大顶堆映射到数组中：

 大顶堆的特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]  // i 对应数组下标

 小顶堆特定：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]  // i 对应数组下标

一般升序采用大顶堆，降序采用小顶堆

        2、应用案例

        给定一个数组，使用堆排序进行排序 arr =  {4,6,8,5,9} 。

        3、思路分析

                (1)、将待排序序列构造成一个大顶堆 此时，整个序列的最大值就是堆顶的根节点。

                (2)、 将其与末尾元素进行交换，此时末尾就为最大值。 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

        第一步：构建大顶堆

         将给定的数组转换成二叉树，如图：

        

        构建大顶堆的原则：从最后一个非叶子结点开始【arr.length / 2 -1】，从左至右，自下到上。并且符合大顶堆的特定：所有结点都大于或等于左右子节点 

         1、所以我们从最后一个非叶子结点 6 开始，此时在5、6、9中，9 的值最大，就将 6 和 9 进行交换

         2、找到第二个非叶子结点 4，在4、8、9中，9的值最大，就将 9 和 4 进行交换

         3、此时，左子树中不满足大顶堆的特定，所以继续调整，在 4、5、6中，6最大，就将 4 和6 进行交换。交换完就构成了大顶堆。

         第二步：将根结点与末尾元素进行交换。此时末尾元素最大，根结点最小。继续调整二叉树的结构，使其满足大顶堆，继续将根结点与末尾元素交换....如此反复，得到一个有序的数组

        1、将 根结点 9 和 末尾元素 4进行交换

        2、继续调整二叉树，使其满足大顶堆的特定。 在 4、6、8 中，8 最大，将 8 和 4进行交换

 

         3、将根结点 8 和 末尾元素 5 进行交换

         4、继续调整，在4、5、6中，6最大，将 5 和6进行交换，

        5、最后将 6 与末尾元素 4 进行交换，得到最终一个有序的数组

         4、代码实现

    
    public static void adjustHeep(int[] arr, int i, int length) {
        int temp = arr[i];

        //判断左右子节点的关系
        for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
            if (j + 1 < length && arr[j] < arr[j + 1]) {
                //如果左子节点比右子节点小，就让j指向右子结点
                //比如：处理第一个非叶子节点6的下标为1，此时 i = 1 ，j = 3，j+1 = 4 。此时 j 对应的值为 5 ，j+1 对应的为 9
                //5 < 9 让 j 指向 j + 1，所以j = 4.
                j = j + 1;
            }
            //判断父节点 i 和 右子结点的大小关系
            //temp = 6 ，arr[j] = 9 , 6 < 9
            if (temp < arr[j]) {
                //如果父结点比右子节点小，就将父结点和右子节点交换
                //arr[i] = arr[j] = 9 , i = 4
                arr[i] = arr[j];
                i = j;
            } else {
                break;
            }
        }
        //此时的将父结点的值赋给与父结点交换的结点
        //此时 i = 4 ，arr[i] = 6
        arr[i] = temp;
    }


    
    public static void heepSort(int[] arr) {
        //从最后一个非叶子节点开始构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeep(arr, i, arr.length);
        }

        //进行排序
        for (int j = arr.length - 1; j > 0; j--) {
            //将首个元素与末尾元素进行交换
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;
            //交换完，继续调整，使其符合大顶堆
            adjustHeep(arr, 0, j);
        }
        System.out.println("排序完的数组：" + Arrays.toString(arr));
    }

 判断左右子结点大小时不要忘记：j + 1 < length 这个条件

        5、测试

 八、霍夫曼树         1、基本介绍

       (1)、 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 也叫霍夫曼树。

        (2)、赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

        (3)、路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1 

        (4)、结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积

        (5)、树的带权路径长度：为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。 WPL最小的就是赫夫曼树 

 第二个wpl最小，所以它是霍夫曼树

        2、应用案例

                将数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树.

        3、思路分析

                1、对数组进行排序，将每个元素都看做一个结点，每个结点都看做一颗二叉树。

                2、取出俩个权值最小的结点，创建一颗新的二叉树，新二叉树的根结点的权值为俩个结点的权值之和。

                3、再对根结点的权值以及数组中的元素进行排序。不断重复第二步，直到数组中所有数据都被处理为止

图解：

        1、对数组进行排序，排序后：[1,3,6,7,8,13,29]，取出俩个最小的结点 1和3，创建新的二叉树

        

     2、在进行排序，排序后：[4,6,7,8,13,29],取出俩个最小的结点 4和6，创建新的二叉树

         3、在进行排序，排序后：[7,8,10,13,29],取出俩个最小的结点 7和8，创建新的二叉树

         4、在进行排序，排序后：[10,13,15,29],取出俩个最小的结点 10和13，创建新的二叉树

         5、在进行排序，排序后[15,23,29],取出俩个最小的结点 15和23，创建新的二叉树

         6、在进行排序，排序后[29,38],最终二叉树为

 最终中序遍历为：29   67   7   15  8   38   1  4  3  10    6   23      13

        4、代码实现

//创建霍夫曼树
class HuffmanTree {
    //中序遍历
    public void midOrder(Node root) {
        if (root != null) {
            root.midOrder();
        } else {
            System.out.println("霍夫曼树为空！");
        }
    }

    //创建霍夫曼树
    public Node createHuffmanTree(int[] arr) {
        //创建集合保存结点
        List nodes = new ArrayList<>();
        //将数组中每个元素都创建为结点
        for (int i = 0; i < arr.length; i++) {
            nodes.add(new Node(arr[i]));
        }
        //处理集合中所有的结点
        while (nodes.size() > 1) {
            //进行排序
            Collections.sort(nodes);
            //1、取出俩个最小的结点
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //2、创建新的结点作为父节点,权值为前俩个结点之和
            Node parent = new Node(leftNode.value + rightNode.value);
            //3、将父结点与俩个结点相连接
            parent.left = leftNode;
            parent.right = rightNode;
            //4、删除处理过的结点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //5、将新结点加入集合
            nodes.add(parent);
        }
        //处理完，集合中剩下最后一个根结点
        return nodes.get(0);
    }
}


class Node implements Comparable {
    int value;//权值
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        //升序，反之降序
        return this.value - o.value;
    }

    //中序遍历
    public void midOrder() {

        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }
}

        5、测试结果 

九、二叉排序树         1、基本介绍

        二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

如果有相同的值，可以将该节点放在左子节点或右子节点 

 

         2、案例应用

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9，2)，创建出对应的二叉树为：

 

 中序遍历为：1  2  3  5  7 9 10  12 

         3、代码实现

//创建二叉排序树
class BST {
    private Node root;

    //中序遍历
    public void midOrder() {
        if (root != null) {
            root.midOrder();
        } else {
            System.out.println("没有根结点");
        }
    }

    //增加结点
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
}

//创建结点
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //中序遍历
    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    //增加结点的方法
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //如果node的value小于当前节点的value。就往左子树上增加
        if (node.value < this.value) {
            //如果当前结点的左子结点为空，直接增加到左子结点
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            //否则就是大于等于当前结点的value，就往右子树上增加
            //如果当前右子树为空，直接增加到右子树上
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

    }
}

 

        4、二叉排序树的删除

        二叉排序树的删除有三种情况：

                1、删除叶子结点 比如 2  5  9  12

                2、删除只有一个子树的结点   比如 1

                3、删除有俩个字树的情况  比如：7  3  10 

        5、思路分析

                删除叶子结点：

                        (1)、找到删除的结点 targetNode

                        (2)、找到targetNode的父节点 parent

                        (3)、并判断targetNode时parent结点的左子结点还是右子结点：

                                左子结点：this.left = null 

                                右子结点：this.right = null

                删除只有一个子树的结点：

                        (1)、找到删除的结点 targetNode

                        (2)、找到targetNode的父节点 parent

                        (3)、判断targetNode是左子结点还是右子结点，并且判断 targetNode是parent的右子结点还是左子结点。（一共有四种情况）

                    （4）、如果targetNode是左子结点有俩种情况：

                                （4.1）、targetNode是parent的左子结点

                                        parent.left = targetNode.left ;

                                （4.2）、targetNode 是parent的右子结点

                                        parent.right = targetNode.left;

                        （5）、如果targetNode是右子结点有俩种情况：

                                （5.1）、targetNode 是parent的左子结点

                                        parent.left = targetNode.right;

                                （5.2）、targetNode是parent的右子结点

                                        parent.right = targetNode.right ;

                删除有俩个子树的结点： 

                        (1)、找到删除的结点 targetNode

                        (2)、找到targetNode的父节点 parent

                        （3）、从targetNode的右子树找到最小的结点【也可以找左子树最大的】。用一个临时变量temp保存。

                        （4）、删除最小结点。

                        （5）、targetNode.value = temp

        5、代码实现

//创建二叉排序树
class BST {
    private Node root;

    //中序遍历
    public void midOrder() {
        if (root != null) {
            root.midOrder();
        } else {
            System.out.println("没有根结点");
        }
    }

    //增加结点
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    //获取删除结点信息
    public Node searchInfo(int value) {
        if (root != null) {
            return root.searchInfo(value);
        }
        return null;
    }

    //获取删除结点的父节点
    public Node searchParent(int value) {
        if (root != null) {
            return root.searchParent(value);
        }
        return null;
    }

    //获取以root为根节点的二叉树种最小结点，并删除
    public int getTreeMin(Node node) {
        Node target = node;
        //因为二叉排序树种，左子结点的值比父节点和右子结点小，所以要从左子树上找
        while (target.left != null) {
            target = target.left;
        }
        //删除结点
        delNode(target.value);
        return target.value;
    }

    //删除结点
    public void delNode(int value) {
        if (root == null) {
            return;
        }
        //找到删除的结点
        Node targetNode = searchInfo(value);
        if (targetNode == null) {
            //如果targetNode为空，说明没有找到。直接返回null
            return;
        } else {
            //找到了但是只有一个结点的时候，直接删除即可
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
        }
        //找到删除结点的父结点
        Node parent = searchParent(value);

        //第一种情况：删除的是叶子结点
        if (targetNode.left == null && targetNode.right == null) {//没有左右子节点
            //说明targetNode是parent的左子结点
            if (parent.left != null && parent.left.value == value) {
                parent.left = null;
            } else if (parent.right != null && parent.right.value == value) {
                parent.right = null;
            }
        }
        //第三种情况：删除有俩颗子树的结点
        else if (targetNode.left != null && targetNode.right != null) { //有左右子节点
            //从targetNode的右子树种找到最小值。
            int temp = getTreeMin(targetNode.right);
            targetNode.value = temp;
        } else {
            //第二种情况：删除有一颗子树的结点
            //如果targetNode是左子结点
            if (targetNode.left != null) {
                if (parent.left.value == value) {
                    //targetNode是parent的左子结点
                    parent.left = targetNode.left;
                } else {
                    //targetNode 是parent的右子结点
                    parent.right = targetNode.left;
                }
            } else {
                //targetNode是右子结点
                if (parent.left.value == value) {
                    //targetNode是parent的左子结点
                    parent.left = targetNode.right;
                } else {
                    //targetNode 是parent的右子结点
                    parent.right = targetNode.right;
                }
            }

        }

    }
}

//创建结点
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //中序遍历
    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    //增加结点的方法
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //如果node的value小于当前节点的value。就往左子树上增加
        if (node.value < this.value) {
            //如果当前结点的左子结点为空，直接增加到左子结点
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            //否则就是大于等于当前结点的value，就往右子树上增加
            //如果当前右子树为空，直接增加到右子树上
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

    }

    //找到删除结点的信息
    public Node searchInfo(int value) {
        if (value == this.value) {
            return this;
        } else if (this.value < value) {
            //如果当前结点value小于查找结点的value，就去右子树上找
            if (this.right != null) {
                return this.right.searchInfo(value);
            } else {
                return null;
            }
        } else {
            //当前结点value小于或等于查找结点的value，就去右子树上找
            if (this.left != null) {
                return this.left.searchInfo(value);
            } else {
                return null;
            }
        }
    }

    //查找删除结点的父节点
    public Node searchParent(int value) {
        //如果左子结点或者右子结点不为空，并且左子结点或者右子结点就是要删除的结点，那么当前结点就是要删除结点的父节点
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else if (this.value < value) { //如果当前结点的value小于查找结点的value，就去右子树上查找
            if (this.right != null) {
                return this.right.searchParent(value);
            } else {
                return null;
            }
        } else {
            //当前结点的value大于或等于查找结点的value，就去左子树上查找
            if (this.left != null) {
                return this.left.searchParent(value);
            } else {
                return null;
            }
        }
    }

}

        6、测试结果

         7、删除存在的问题

                虽然上面我们把删除做完了，但是还是存在一个问题。如果我们逐渐删除二叉排序树中的结点看看会是什么情况：

 这样逐渐删除是没有问题的，但是我把删除 3 结点 和删除 12 结点换一个位置，看看会出什么问题？

 当 12 和3 调换位置时出现空指针异常：这时因为当剩下这俩个结点时，删除的12是根结点，3是左子结点。所以parent.left 是 null 的

        8、解决办法 

                增加一个判断条件：当parent != null 的时候，继续执行下面的代码， ==null 的时候，将 根节点指向左子结点或者右子结点

 看看最后测试结果：这样就删除成功了