【数据结构与算法】9.1、二叉树 遍历查找 删除

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

     1).数组存储方式的分析

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

       缺点：如果要检索具体某个值，或者插入值会整体移动，效率低。

      2).链式存储方式的分析

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

       缺点：在进行检索时，效率任然较低，比如检索(需要从头开始检索)。

      3).树存储方式的分析

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

2、树的基本知识

   

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

3.二叉树的概念

1. 树有很多种，每个节点最多只能由两个子节点的一种形式称为二叉树。
2. 二叉树的子节点分为左节点和右节点
3. 
4. 如果该二叉树的所有叶子节点都在最后一层，并且节点总数=2^N-1 N为层数，则我们称为满二叉树。
5. 
6. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
7. 

4.二叉树的遍历

• 使用前序。中序和后序对下面的二叉树进行遍历
• 前序遍历：先输出父节点，在遍历左子树和右子树
• 中序遍历：先遍历左子树，在输出父节点，在遍历右子树
• 后续遍历：先遍历左子树，在遍历右子树，在输出父节点。
• 总结:看输出父节点的顺序，就确定是前序 中序 后序。

5、代码实现

package com.hblg.tree;

/**
 * @author i
 * @create 2019/10/12 17:33
 * @Description 二叉树
 *   二叉树
 *   前序遍历
 *         父-》左-》右
 *   中序遍历
 *         左-》父-》右
 *   后续遍历
 *         左-》右-》父
 */
public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        StudentNode root = new StudentNode(1,"宋江");
        StudentNode node2 = new StudentNode(2,"吴用");
        StudentNode node3 = new StudentNode(3,"罗俊毅");
        StudentNode node4 = new StudentNode(4,"林冲");
        StudentNode node5 = new StudentNode(5,"张飞");

        binaryTree.setRootNode(root);//设置根节点
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
//        //前序遍历 父左右
//        System.out.println("前序遍历:"); // 1.2.3.4
//        binaryTree.preOrder();
//
//        //中序遍历 左 父 右   2134
//        System.out.println("中序遍历");
//        binaryTree.midOrder();
//
//        //后序遍历 左 右 父  2431
//        System.out.println("后序遍历");
//        binaryTree.postOrder();
        //删除节点
//        binaryTree.delStudentNode(5);
//        binaryTree.preOrder();//前序遍历  1 2
        binaryTree.delStudentNode(5);
        binaryTree.postOrder();//后序遍历
    }

}

/***
 * 二叉树
 */
class BinaryTree{

    private StudentNode rootNode;//根节点

    public StudentNode getRootNode() {
        return rootNode;
    }

    public void setRootNode(StudentNode rootNode) {
        this.rootNode = rootNode;
    }

    //前序遍历 父左右
    public void preOrder(){
        if (this.rootNode != null){
            this.rootNode.preOrder();
        }else {
            System.out.println("二叉树不存在~");
        }
    }
    //中序遍历 左父右
    public void midOrder(){
        if(this.rootNode != null){
            this.rootNode.midOrder();
        }else {
            System.out.println("二叉树不存在~");
        }
    }
    //后序遍历 左右父
    public void postOrder(){
        if (this.rootNode != null){
            this.rootNode.postOrder();
        }else {
            System.out.println("二叉树不存在~");
        }
    }

    //前序查找
    public StudentNode preOrderSearch(int no){
        if (this.rootNode != null){
            return rootNode.preOrderSearch(no);
        }else {
            return null;
        }
    }

    //中序遍历 左父右
    public StudentNode midOrderSearch(int no){
        if(this.rootNode != null){
            return rootNode.midOrderSearch(no);
        }else {
            return null;
        }
    }

    //后序遍历 左右 父
    public StudentNode postOrderSearch(int no){
        if (this.rootNode != null){
            return rootNode.postOrderSearch(no);
        }else {
            return null;
        }
    }

    //删除节点
    public void delStudentNode(int no){
        if (this.rootNode != null){
            if (this.rootNode.getId() == no){
                this.rootNode  = null;//删除就是根节点
            }else {
                this.rootNode.delStudentNode(no);//删除子节点 递归查找删除
            }
        }else {
            System.out.println("没有找到!");
        }
    }

}

/***
 * 节点类
 */
class StudentNode{

    private Integer id;
    private String name;
    private StudentNode left;//左节点
    private StudentNode right;//右节点

    public StudentNode(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public StudentNode getLeft() {
        return left;
    }

    public void setLeft(StudentNode left) {
        this.left = left;
    }

    public StudentNode getRight() {
        return right;
    }

    public void setRight(StudentNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "StudentNode{" +
                "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);
    }


    /***
     * 使用前序 中序 后序的方式来查询指定的节点
     * 前序查找思路
     *  1.先判断当前节点的no是否等于要查找的
     *  2.如果是相等，则返回当前节点
     *  3.如果不等，则判断当前节点的左子节点是否为空，如果不为空，则递归前序查找
     *  4.如果左递归前序查找，找到节点，则返回 否则继续判断，
     *  当前的节点的右子节点是否为空，如果不空，则继续向右递归前序查找
     *
     */
    public StudentNode preOrderSearch(int no){
        //1、先判断当前节点no是否是要查找的
        if(this.getId() == no){
            return this;
        }
        StudentNode currentNode = null;
        //2、如果不等，则判断当前节点的左子节点是否为空
        if(this.left!=null){
            currentNode = this.left.preOrderSearch(no);//递归前序查找
        }
        //说明左子树找到
        if (currentNode != null){
            return currentNode;
        }
        //3.判断右子节点是否相等
        if (this.right != null){
            currentNode = this.right.preOrderSearch(no);//递归前序查找
        }
        return currentNode;
    }


    /***
     * 中序遍历
     *   1.判断当前节点的左子节点是否为空，如果不为空，则递归中序查找
     *   2.如果找到，则返回，如果没有找到，就和当前节点做比较，如果是返回当前节点，否则继续进行向右递归中序查找
     *   3.如果右递归中序查找，找到就返回 否则返回null
     * @param no
     * @return
     */
    public StudentNode midOrderSearch(int no){
        StudentNode currentNode = null;
        //1.判断当前节点的左子节点是否为空，如果不为空 则递归中序查找
        if (this.left != null){
            currentNode = this.left.midOrderSearch(no);
        }
        //2.找到直接返回
        if (currentNode != null){
            return currentNode;
        }
        //3.如果找到 直接返回
        if (this.getId() == no){
            return this;
        }
        //4.否则进行向右递归查找
        if (this.right != null){
            currentNode = this.right.midOrderSearch(no);
        }
        return currentNode;
    }


    /***
     *  后序遍历
     *  1.判断当前节点的左子节点是否为空，如果不为空，则递归后查找
     *  2.如果找到，就返回 如果没有找到，就判断当前节点的右子节点是否为空，如果不为空 则右递归进行后续查找，如果找到，就返回
     *  3.就和当前节点进行，比如，如果是则返回，否则返回null.
     * @param no
     * @return
     */
    public StudentNode postOrderSearch(int no){
        StudentNode currentNode = null;
        if (this.left != null){//左子树查找
            currentNode = this.left.postOrderSearch(no);
        }
        if (currentNode != null){//找到 直接返回
            return currentNode;
        }
        if (this.right != null){//右子树查找
            currentNode = this.right.postOrderSearch(no);
        }
        if (currentNode != null){//找到 直接返回
            return currentNode;
        }

        if (this.getId() == no){
            return  this;
        }
        return currentNode;
    }

    /***
     * 递归删除节点
     * 1.如果删除的节点是叶子节点，则删除该节点
     * 2.如果删除的节点是非叶子节点，则删除该子树
     *
     * 思路:1.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否需要删除节点，而不能去判断当前这个节点是不是需要删除的节点
     *  2.如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将this.left = null;并且就返回(结束递归删除)
     *  3.如果当前节点的右子节点不为空，并且右子节点就是要删除的节点 就将this.right = null;并且就返回(结束递归删除)
     *  4.如果第2步和第三部没有删除节点，那么我们就需要向左子节点树进行递归删除
     *  5.如果第4步也没有删除节点，则应当向右子树进行递归删除。
     *  @param no
     */
    public void delStudentNode(int no){
        //2.如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将this.left = null
        if (this.left != null && this.left.getId()== no){
            this.left = null;
            return;
        }
        //3.如果当前节点的右子节点不为空，并且右子节点就是要删除节点，就将this.right = null
        if (this.right != null && this.right.getId() == no){
            this.right = null;
            return;
        }
        //4.递归左子树
        if (this.left != null){
            this.left.delStudentNode(no);
        }

        //5.递归右子树
        if (this.right != null){
            this.right.delStudentNode(no);
        }

    }

}