数据结构和算法：二叉树

二叉树

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

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。

特殊类型

满二叉树：二叉树内只有度为2和0的节点，且度为0的节点在同一层，即除了树的最后一层的节点没有子节点，其他节点都有2个子节点，则这个二叉树就是满二叉树。满二叉树的节点数量为2^k-1(k为树的深度)。

完全二叉树：完全二叉树的节点顺序是由上到下，由左到右的。即叶子节点所在的层级差别不能大于1，且右节点不为空时，左节点也不能为空。满二叉树一定就是完全二叉树，但完全二叉树不一定是满二叉树。

代码实例

使用二叉树来存储水浒英雄好汉，模拟水浒英雄排名。

首先需要先创建二叉树里的节点，用于存储水浒英雄的编号、名字和节点的左、右子节点。

//水浒英雄节点
class HeroNode{
    private int id;
    private String name;
    private HeroNode left;//节点的左子节点
    private HeroNode right;//节点的右子节点

    //3种遍历树的方法，在《数据结构与算法：树》的一章有过讲解
    //前序遍历（中-左-右）
    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);
    }

    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 + '\'' +
                '}';
    }

}

有了节点，接下来就需要创建二叉树类了，而二叉树的起点是根节点，我们需要靠根节点才可以实现增删改查的操作，所以二叉树最重要的属性就是根节点。

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

    //实例化根节点，即实例化二叉树
    public void setRoot(HeroNode 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 class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();

        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node1 = new HeroNode(2, "卢俊义");
        HeroNode node2 = new HeroNode(3, "吴用");
        HeroNode node3 = new HeroNode(4, "公孙胜");
        HeroNode node4 = new HeroNode(5, "关胜");

        //为各个节点设置关系
        root.setLeft(node1);
        root.setRight(node2);
        node2.setLeft(node4);
        node2.setRight(node3);
        //实例化二叉树根节点
        binaryTree.setRoot(root);

        //使用3种遍历方式遍历二叉树
        System.out.println("前序遍历：");
        binaryTree.preOrder();
        System.out.println("中序遍历：");
        binaryTree.midOrder();
        System.out.println("后序遍历：");
        binaryTree.postOrder();
    }
}

如果我们要根据id查找单个水浒英雄信息时，只需将遍历方法修改一下即可，下面以前序遍历查找为例：

//前序遍历查找(修改节点方法只需添加个修改参数，并把返回代码改成修改代码)
public HeroNode preOrderSearch(int id){
    //如果当前节点就是查找的节点时，返回该节点(中)
    if (id == this.getId()){
        return this;
    }
    HeroNode result = null;
    //往左子节点递归遍历查找
    if (this.left != null){
        result = this.left.preOrderSearch(id);
    }
    //如果result不为空则表明已经查找到该节点，直接返回result
    if (result != null){
        return result;
    }
    //往右子节点递归遍历查找
    if (this.right != null){
        result = this.right.preOrderSearch(id);
    }
    return result;
}

顺序存储二叉树

二叉树的存储方式有俩种，一种是链式存储(上面代码所演示的)，另一种是顺序存储。顺序存储指的是用数组来存储二叉树，即根据层级，从第一层到最后一层由左到右的顺序存储在数组中。

顺序存储二叉树的节点总数量：数组的长度

下标为n的节点的左节点下标：n*2+1

下标为n的节点的右节点下标：n*2+2

下标为n的节点的父节点下标：(n-1)/2

注意：顺序存储方式只能存储完全二叉树，如果要存储非完全二叉树，需将它转换成完全二叉树，即补值为0的节点，直到该二叉树变成完全二叉树

代码实例

//顺序存储二叉树
class ArrayBinaryTree{
    //顺序存储的数组
    private int[] array;

    public ArrayBinaryTree(int[] array) {
        this.array = array;
    }

    public void preOrder(){
        preOrder(0);
    }

    public void midOrder(){
        midOrder(0);
    }

    public void postOrder(){
        postOrder(0);
    }

    //前序遍历
    public void preOrder(int index){
        if (array == null || array.length == 0){
            System.out.println("二叉树数组为空，无法遍历");
            return;
        }
        //输出该节点(中)
        System.out.println(array[index]);
        //往左递归遍历(左)
        if (index*2+1 < array.length){//判断左节是否为空
            preOrder(index*2+1);
        }
        //往右递归遍历(右)
        if (index*2+2 < array.length){//判断右节点是否为空
            preOrder(index*2+2);
        }
    }

    //中序遍历
    public void midOrder(int index){
        if (array == null || array.length == 0){
            System.out.println("二叉树数组为空，无法遍历");
            return;
        }
        if (index*2+1 < array.length){
            midOrder(index*2+1);
        }
        System.out.println(array[index]);
        if (index*2+2 < array.length){
            midOrder(index*2+2);
        }
    }

    //后序遍历
    public void postOrder(int index){
        if (array == null || array.length == 0){
            System.out.println("二叉树数组为空，无法遍历");
            return;
        }
        if (index*2+1 < array.length){
            postOrder(index*2+1);
        }
        if (index*2+2 < array.length){
            postOrder(index*2+2);
        }
        System.out.println(array[index]);
    }
}

线索化二叉树

在上图的二叉树遍历中，当我们遍历到叶子节点时，需要一层一层的返回到下一个输出的节点，效率并不高，那我们能不能直接让叶子节点指向在对应遍历方法中它的下一个节点呢？这时我们就需要线索化二叉树了。

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

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

代码实例

//中序线索化二叉树
class ThreadedBinaryTree{
    private HeroNode2 root;
    //在中序线索化时，保存前一个节点，默认为空
    private HeroNode2 pre;

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

    public void threadedNodes(){
        threadedNodes(root);
    }

    //中序线索化二叉树
    public void threadedNodes(HeroNode2 node){
        //如果传入的参数节点为空，即已经超出二叉树范围，则直接返回
        if (node == null){
            return;
        }

        /**
         * 按照中序遍历(左中右)的顺序，依次为各个节点线索化
         */
        //先向节点的左节点递归，依次线索化左节点
        threadedNodes(node.getLeft());

        //为节点线索化
        /*
        如果该节点的左节点为空，则将该节点的左节点设置为中序线索化的前一个节点pre,
        并将该节点的左节点类型leftType设置为前驱节点1
        注意: 在第一次线索化时，左节点会设置为空，但因为是中序线索化，所以不影响
         */
        if (node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        /*
        如果前一个节点pre的右节点为空，则将中序线索化的前一个节点pre的右节点设置为当前节点，
        并将pre节点的右节点类型设为后继节点1
        逻辑：pre只有当它的右节点为空时才会进入线索化，而这时递归已经返回到中序遍历时pre节点的
        下一个遍历节点node，所以node就是在中序线索化中pre的下一个节点，即后继节点
         */
        if (pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //线索化后要将当前节点设置会上一个节点
        pre = node;

        //再向节点的右节点递归，依次线索化右节点
        threadedNodes(node.getRight());
    }

    //遍历中序线索化二叉树(即输出中序遍历的结果)
    public void threadedList(){
        HeroNode2 node = root;

        //当node为空时，即中序线索化二叉树已经遍历完成
        while (node != null){
            //如果左节点的类型是子树0的话，则继续往节点的左节点走
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            //当退出循环时，即node没有左子节点了，则输出node节点
            System.out.println(node);

            //如果右节点的类型是后继节点1时，则直接跳到后继节点并输出
            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            //当退出循环时，即node还有右子节点，则继续往节点的右子节点走
            node = node.getRight();
        }
    }
}

//线索化二叉树节点
/**
 * 因为二叉树线索化后，
 * 左节点的指向有两种情况：指向左子树或指向前驱节点；右节点的指向也有两种情况：指向右子树或指向后继节点；
 * 所以要分别为左、右节点创建一个属性，该属性可以说明左、右节点的指向情况。
 */
class HeroNode2{
    private int id;
    private String name;
    private HeroNode2 left;
    private HeroNode2 right;
    //左指向的类型，当为0时，指向的是左子树，当为1时，指向的是前驱节点
    private int leftType;
    //右指向的类型，当为0时，指向的是右子树，当为1时，指向的是后继节点
    private int rightType;

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

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

    public HeroNode2 getRight() {
        return right;
    }

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

    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;
    }

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