二叉树

二叉树

二叉树简介

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分 。

二叉树定义

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉树特殊类型

1、满二叉树： 如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
2、完全二叉树： 深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

二叉树性质

性质1： 二叉树的第i层上至多有2^(i-1)（i≥1）个节点 。
性质2： 深度为h的二叉树中至多含有2^h-1个节点。
性质3： 若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有 n0=n2+1。
性质4： 具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。

java代码实现

// 二叉树
public class BinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");


        BinaryTree root = new BinaryTree(node1);
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        System.out.println("前序遍历结果为：");
        root.preOrder();
        System.out.println("中序遍历结果为：");
        root.infixOrder();
        System.out.println("后序遍历结果为：");
        root.postOrder();

        System.out.println("前序查找的结果为:");
        HeroNode preNode = root.preOrderSreach(5);
        if (preNode != null) {
            System.out.println("前序查找，查到的信息为：id=" + preNode.getId() + ",name=" + preNode.getName());
        } else {
            System.out.println("前序遍历没有查询到结果。");
        }

        System.out.println("中序查找的结果为:");
        HeroNode infixNode = root.infixOrderSreach(5);
        if (infixNode != null) {
            System.out.println("中序查找，查到的信息为：id=" + infixNode.getId() + ",name=" + infixNode.getName());
        } else {
            System.out.println("中序遍历没有查询到结果。");
        }

        System.out.println("后序查找的结果为:");
        HeroNode postNode = root.postOrderSreach(5);
        if (postNode != null) {
            System.out.println("后序查找，查到的信息为：id=" + postNode.getId() + ",name=" + postNode.getName());
        } else {
            System.out.println("后序遍历没有查询到结果。");
        }

        System.out.println("删除前的二叉树，前序遍历顺序：");
        root.preOrder();
        if (root.delNode(3)) {
            System.out.println("id=3删除成功");
        } else {
            System.out.println("删除失败");
        }

        System.out.println("删除后的二叉树，前序遍历顺序：");

        root.preOrder();


    }
}


//创建二叉树
class BinaryTree {
    private HeroNode root;  //二叉树的根节点

    public BinaryTree(HeroNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (root == null) {
            System.out.println("二叉树为空，前序遍历为空。");
        } else {
            root.preOrder();
        }
    }

    //中序遍历
    public void infixOrder() {
        if (root == null) {
            System.out.println("二叉树为空，中序遍历为空");
        } else {
            root.infixOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if (root == null) {
            System.out.println("二叉树为空，后序遍历为空");
        } else {
            root.postOrder();
        }
    }

    //前序遍历查找
    public HeroNode preOrderSreach(int no) {
        if (root != null) {
            return root.preOrderSreach(no);
        } else {
            return null;
        }
    }

    //中序遍历查找
    public HeroNode infixOrderSreach(int no) {
        if (root != null) {
            return root.infixOrderSreach(no);
        } else {
            return null;
        }
    }

    //后序遍历查找
    public HeroNode postOrderSreach(int no) {
        if (root != null) {
            return root.postOrderSreach(no);
        } else {
            return null;
        }
    }

    //删除结点
    //先判断当前的root是不是待删除结点 如果是就删除整颗二叉树，如果不是再调用结点的删除方法
    public Boolean delNode(int no) {
        if (root == null) {
            return false;
        } else {
            if (root.getId() == no) {
                root = null;
                return true;
            } else {
                return root.delNode(no);
            }
        }
    }

}


//创建节点的类
class HeroNode {
    private int id;
    private String name;
    private HeroNode left;  // 默认为空
    private HeroNode right;  // 默认为空

    public HeroNode(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 HeroNode getLeft() {
        return left;
    }

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

    public HeroNode getRight() {
        return right;
    }

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

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

    /**
     * 前序遍历思路
     * 1.输出当前节点
     * 2.判断段当前节点的左子节点是否为空，递归前序遍历
     * 3.判断当前节点的右子节点是否为空，递归前序遍历
     */
    public void preOrder() {
        System.out.println(this);

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

    /**
     * 中续遍历思路
     * 1.判断段当前节点的左子节点是否为空，递归中序遍历
     * 2.输出当前节点
     * 3.判断当前节点的右子节点是否为空，递归中续遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    /**
     * 后续遍历思路
     * 1.判断段当前节点的左子节点是否为空，递归后序遍历
     * 2.判断当前节点的右子节点是否为空，递归后续遍历
     * 3.输出当前节点
     */
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    /**
     * 前序遍历查找的思路
     * 1.判断当前节点是否为待查找节点，如果是直接返回，
     * 2.判断当前节点的左子节点是否为空，不为空则向左递归前序查找，找到则返回，找不到则返回null
     * 3.判断当前节点的右子节点是否为空，不为空则向右递归前序查找，找到则返回，找不到则返回null
     *
     * @param no 带查找的节点id
     * @return 返回该节点的信息
     */
    public HeroNode preOrderSreach(int no) {
//        System.out.println("前序遍历的次数~~~");

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

        HeroNode heroNode = null;
        //判断当前节点的左子节点是否为空，不为空则向左递归前序查找，找到则返回，找不到则返回null
        if (this.left != null) {
            heroNode = this.left.preOrderSreach(no);
        }
        if (heroNode != null) {
            return heroNode;
        }
        //判断当前节点的右子节点是否为空，不为空则向右递归前序查找，找到则返回，找不到则返回null
        if (this.right != null) {
            heroNode = this.right.preOrderSreach(no);
        }
        return heroNode;
    }


    /**
     * 中序遍历查找的思路
     * 1.判断当前节点的左子节点是否为空，不为空则向左递归中序查找，找到则返回，找不到则返回null，
     * 2.判断当前节点是否为待查找节点，如果是直接返回
     * 3.判断当前节点的右子节点是否为空，不为空则向右递归中序查找，找到则返回，找不到则返回null
     *
     * @param no 带查找的节点id
     * @return 返回该节点的信息
     */
    public HeroNode infixOrderSreach(int no) {
        HeroNode heroNode = null;
        //判断当前节点的左子节点是否为空，不为空则向左递归中序查找，找到则返回，找不到则返回null
        if (this.left != null) {
            heroNode = this.left.infixOrderSreach(no);
        }
        if (heroNode != null) {
            return heroNode;
        }
//        System.out.println("中序遍历的次数~~~");

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

        //判断当前节点的右子节点是否为空，不为空则向右递归中序查找，找到则返回，找不到则返回null
        if (this.right != null) {
            heroNode = this.right.infixOrderSreach(no);
        }
        return heroNode;
    }


    /**
     * 后序遍历查找的思路
     * 1.判断当前节点的左子节点是否为空，不为空则向左递归后序查找，找到则返回，找不到则返回null，
     * 2.判断当前节点的右子节点是否为空，不为空则向右递归后序查找，找到则返回，找不到则返回null
     * 3.判断当前节点是否为待查找节点，如果是直接返回
     *
     * @param no 带查找的节点id
     * @return 返回该节点的信息
     */
    public HeroNode postOrderSreach(int no) {
        HeroNode heroNode = null;
        //判断当前节点的左子节点是否为空，不为空则向左递归后序查找，找到则返回，找不到则返回null
        if (this.left != null) {
            heroNode = this.left.postOrderSreach(no);
        }
        if (heroNode != null) {
            return heroNode;
        }
        //判断当前节点的右子节点是否为空，不为空则向右递归后序查找，找到则返回，找不到则返回null
        if (this.right != null) {
            heroNode = this.right.postOrderSreach(no);
        }
        if (heroNode != null) {
            return heroNode;
        }
//        System.out.println("后序遍历的次数~~~~");

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

        return heroNode;
    }


    /**
     * 删除结点的思路
     * 1.因为二叉树是单向是的，所以删除的时候只能删除当前结点的下一个结点。
     * 2.如果当前的左子节点不为空，判断当前的左子结点是否为待删除结点，如果是领this.left=null,让后返回true。
     * 3.如果当前的右子节点不为空，判断当前的右子结点是否为待删除结点，如果是就领this.right=null，让后返回true。
     * 4.如果 2 ， 3 都没有找到待删除结点就向左递归，
     * 5.如果向左递归没有找到就向右递归
     *
     * @param no 待删除结点的id
     * @return 返回是否删除成功
     */
    public Boolean delNode(int no) {
        if (this.left != null && this.left.id == no) {
            this.left = null;
            return true;
        }
        if (this.right != null && this.right.id == no) {
            this.right = null;
            return true;
        }
        if (this.left != null) {
            if (this.left.delNode(no)) {
                return true;
            }
        }
        if (this.right != null) {
            if (this.right.delNode(no)) {
                return true;
            }
        }
        return false;
    }

}