二叉树 | 程序员小舟

type

status

date

slug

summary

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

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

链式存储方式的分析优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

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

。

2、树示意图

树的常用术语(结合示意图理解):

节点

根节点

父节点

子节点

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

节点的权(节点值)

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

子树

树的高度(最大层数)

森林 :多颗子树构成森林

3、二叉树的概念

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

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

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

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。使用前序，中序和后序对下面的二叉树进行遍历.

4、二叉树遍历的说明

前序遍历: 先输出父节点，再遍历左子树和右子树中序遍历: 先遍历左子树，再输出父节点，再遍历右子树后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点小结: 看输出父节点的顺序，就确定是前序，中序还是后序

4.1、前序遍历


  public void preOrder(){
        System.out.println(this);

        //向左子树递归
        if (this.left!=null){
            this.left.preOrder();
        }

        //向左子树递归
        if (this.right!=null){
            this.right.preOrder();
        }
    }

4.2、中序遍历


 public void midOrder(){
        if (this.left!=null){
            this.left.midOrder();
        }

        System.out.println(this);

        if (this.right!=null){
            this.right.midOrder();
        }
    }

4.3、后序遍历


 public void postOrder(){
        if (this.left!=null){
            this.left.postOrder();
        }

        if (this.right!=null){
            this.right.postOrder();
        }

        System.out.println(this);

    }

5、二叉树-查找指定节点

要求请编写前序查找，中序查找和后序查找的方法。并分别使用三种查找方式，查找 heroNO = 5 的节点并分析各种查找方式，分别比较了多少次

5.1、前序查找


 /**
     * 前序查找（id）
     */
    public Hero preOrderSearch(int id){
        System.out.println("前序查找~~~");
        if (this.id==id){
            return this;
        }

        //向左子节点遍历
        Hero result=null;
        if (this.left!=null){
            Hero hero = this.left.preOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    return hero;
                }
            }

        }

        //向右子节点遍历
        if (this.right!=null){
            Hero hero = this.right.preOrderSearch(id);
            if (hero!=null){
            if (hero.id==id){
                result=hero;
            }
            }
        }
        return result;
    }

5.2、中序查找


  /**
     * 中序查找（id）
     */
    public Hero midOrderSearch(int id){
        //向左子节点遍历
        Hero result=null;
        if (this.left!=null){
            Hero hero = this.left.midOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    return hero;
                }
            }

        }

        System.out.println("中序查找~~~");
        if (this.id==id){
            return this;
        }

        //向右子节点遍历
        if (this.right!=null){
            Hero hero = this.right.midOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    result=hero;
                }
            }
        }
        return result;
    }

5.3、后序查找


  /**
     * 后序查找（id）
     */
    public Hero postOrderSearch(int id){
        //向左子节点遍历
        Hero result=null;
        if (this.left!=null){
            Hero hero = this.left.postOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    return hero;
                }
            }

        }


        //向右子节点遍历
        if (this.right!=null){
            Hero hero = this.right.postOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    result=hero;
                }
            }
        }


        if (this.id==id){
            return this;
        }

        System.out.println("后序查找~~~");

        return result;
    }

6、二叉树-删除节点

要求：

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

6.1、删除节点思路分析


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


 public void deleteNo(int id){
        if (this.left!=null&&this.left.id==id){
            this.left=null;
        }

        if (this.right!=null&&this.right.id==id){
            this.right=null;
        }

        if (this.left!=null){
            this.left.deleteNo(id);
        }

        if (this.right!=null){
            this.right.deleteNo(id);
        }


    }

7、代码实现


package com.qf;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        Hero hero1=new Hero(1,"宋江");
        Hero hero2=new Hero(2,"吴用");
        Hero hero3=new Hero(3,"卢俊义");
        Hero hero4=new Hero(4,"林冲");
        Hero hero5=new Hero(5,"豹子头");
        Hero hero6=new Hero(6,"武松");
        hero1.setLeft(hero2);
        hero2.setRight(hero5);
        hero1.setRight(hero3);
        hero3.setRight(hero4);
        hero3.setLeft(hero6);
        BinaryTree binaryTree=new BinaryTree();
        binaryTree.setRoot(hero1);
        binaryTree.delete(6);
        binaryTree.postOrder();
      /*  Hero hero = binaryTree.postOrderSearch(4);
        if (hero==null){
            System.out.println("未找到该英雄");
        }else{
            System.out.println("找到了该英雄");
            System.out.println(hero);
        }*/
    }
}
class BinaryTree{
    private Hero root;

    public Hero getRoot() {
        return root;
    }

    public void setRoot(Hero root) {
        this.root = root;
    }

    public void preOrder(){
        if (this.root!=null){
            root.preOrder();
        }else {
            System.out.println("树为空");
        }
    }

    public void midOrder(){
        if (this.root!=null){
            root.midOrder();
        }else {
            System.out.println("树为空");
        }
    }

    public void postOrder(){
        if (this.root!=null){
            root.postOrder();
        }else {
            System.out.println("树为空");
        }
    }

    public Hero preOrderSearch(int id){
        if (this.root!=null){
            Hero hero = root.preOrderSearch(id);
            return hero;
        }else {
            return null;
        }
    }

    public Hero midOrderSearch(int id){
        if (this.root!=null){
            Hero hero = root.midOrderSearch(id);
            return hero;
        }else {
            return null;
        }
    }

    public Hero postOrderSearch(int id){
        if (this.root!=null){
            Hero hero = root.postOrderSearch(id);
            return hero;
        }else {
            return null;
        }
    }

    public void delete(int id){
        if (root!=null){
            if (root.getId()==id){
                root=null;
            }else{
                root.deleteNo(id);
            }
        }else{
            System.out.println("空树无法删除~");
        }
    }

}

class Hero{
    private int id;
    private String name;
    private Hero left;
    private Hero right;

    public Hero(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;
    }

    public Hero getLeft() {
        return left;
    }

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

    public Hero getRight() {
        return right;
    }

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

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

    }

    /**
     * 前序查找（id）
     */
    public Hero preOrderSearch(int id){
        System.out.println("前序查找~~~");
        if (this.id==id){
            return this;
        }

        //向左子节点遍历
        Hero result=null;
        if (this.left!=null){
            Hero hero = this.left.preOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    return hero;
                }
            }

        }

        //向右子节点遍历
        if (this.right!=null){
            Hero hero = this.right.preOrderSearch(id);
            if (hero!=null){
            if (hero.id==id){
                result=hero;
            }
            }
        }
        return result;
    }


    /**
     * 中序查找（id）
     */
    public Hero midOrderSearch(int id){
        //向左子节点遍历
        Hero result=null;
        if (this.left!=null){
            Hero hero = this.left.midOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    return hero;
                }
            }

        }

        System.out.println("中序查找~~~");
        if (this.id==id){
            return this;
        }

        //向右子节点遍历
        if (this.right!=null){
            Hero hero = this.right.midOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    result=hero;
                }
            }
        }
        return result;
    }

    /**
     * 后序查找（id）
     */
    public Hero postOrderSearch(int id){
        //向左子节点遍历
        Hero result=null;
        if (this.left!=null){
            Hero hero = this.left.postOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    return hero;
                }
            }

        }


        //向右子节点遍历
        if (this.right!=null){
            Hero hero = this.right.postOrderSearch(id);
            if (hero!=null){
                if (hero.id==id){
                    result=hero;
                }
            }
        }


        if (this.id==id){
            return this;
        }

        System.out.println("后序查找~~~");

        return result;
    }

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

        if (this.right!=null&&this.right.id==id){
            this.right=null;
        }

        if (this.left!=null){
            this.left.deleteNo(id);
        }

        if (this.right!=null){
            this.right.deleteNo(id);
        }


    }
}