数据结构和算法学习之线索化二叉树

所谓线索化二叉树，就是让二叉树中的每一个节点的左右两侧均有所指，左侧指向前驱节点，右侧指向后继节点，让整个二叉树连起来。

package com.atguigu.threadedbinarytree;


public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试中序线索二叉树
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");

        //手动创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        //测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();

        //测试：以10号节点为例
//        HeroNode leftNode = node5.getLeft();
//        System.out.println("10号节点的前驱节点是" + leftNode);
//        HeroNode rightNode = node5.getRight();
//        System.out.println("10号节点的后继节点是" + rightNode);
        HeroNode right = node4.getRight();
        System.out.println("8号的后继节点为" + right);
        //使用线索化方式遍历线索化二叉树
        threadedBinaryTree.threadList();//8,3,10,1,14,6

    }
}

//定义一个ThreadedBinaryTree二叉树
//实现中序线索化
class ThreadedBinaryTree {
    private HeroNode root;


    //为了实现线索化，需要创建一个指向当前节点的前驱节点的指针
    //在递归线索化时，pre总保留当前节点的前一个节点
    private HeroNode pre = null;

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

    //遍历线索化二叉树
    public void threadList() {
        HeroNode node = root;
        while (node != null) {
            //循环找到leftType为1的节点，第一个就是8的节点
            while (node.getLeftType() == 0) {//node.getLeftType() == 0说明指向的是左子树
                node = node.getLeft();
            }
            System.out.println(node);//输出当前节点
            while (node.getRightType() == 1) {//说明当前节点有后继节点
                node = node.getRight();
                System.out.println(node);//输出下一个节点
            }
            //退出的时候的node指向的是右子树
            //换成node的下一个后继节点
            node = node.getRight();
        }
    }


    //重载一下
    public void threadedNodes() {
        this.threadedNodes(root);
    }

    //编写对二叉树进行中序线索化的方法

    
    public void threadedNodes(HeroNode node) {

        //传入节点为空，不能进行线索化
        if (node == null) {
            return;
        }

        //对左子树进行线索化
        threadedNodes(node.getLeft());
        //对当前节点进行线索化
        //(一)对前驱节点进行线索化
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针类型，指向前驱节点
            node.setLeftType(1);
        }
        //(二)对后继节点进行线索化
        if (pre != null && pre.getRight() == null) {
            //让前驱节点的右指针指向当前节点
            pre.setRight(node);
            //修改前驱节点的右指针类型
            pre.setRightType(1);
        }
        //!!!处理完每一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;
        //对右子树进行线索化
        threadedNodes(node.getRight());


    }

    //删除节点
    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
                return;
            }
            root.delNode(no);
        } else {
            System.out.println("空树，无法删除~");
        }


    }

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

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

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

    //前序遍历查找
    public HeroNode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            System.out.println("当前二叉树为空，未查找到");
            return null;
        }
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            System.out.println("当前二叉树为空，未查找到");
            return null;
        }
    }

    //后序遍历查找
    public HeroNode postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            System.out.println("当前二叉树为空，未查找到");
            return null;
        }
    }

}


class HeroNode {
    private int no;
    private String name;
    HeroNode left;//默认为null
    HeroNode right;//默认为null
    //说明:
    //1.如果leftType为0，说明指向左子树，如果leftType为1说明指向前驱节点
    //2.如果rightType为0，说明指向右子树，如果rightType为1，说明指向右子树
    private int leftType;
    private int rightType;

    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 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{" +
                "no=" + no +
                ", name='" + name + ''' +
                '}';
    }

    //递归删除节点
    //规定：
    //如果删除的节点是叶子节点，则删除该节点
    //如果删除的节点是非叶子节点，则删除该子树
    public void delNode(int no) {
        //由于当前二叉树是单向的，所以是判断当前节点的下一个节点是否是待删除节点，而不能判断该节点本身
        //1.判断左子节点是否满足
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;//删除之后就返回
        }
        //2.判断右子节点是否满足
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //3.当前节点的左右节点都不满足，则开始递归
        //3.1向左递归
        if (this.left != null) {
            this.left.delNode(no);
        }
        //3.2向右递归
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);//先输出父节点
        //递归向左子树进行遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右子树进行遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder() {
        //递归向左子树进行遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右子树进行遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //后续遍历
    public void postOrder() {
        //递归向左子树进行遍历
        if (this.left != null) {
            this.left.postOrder();
        }
        //递归向右子树进行遍历
        if (this.right != null) {
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);
    }

    //前序遍历查找

    
    public HeroNode preOrderSearch(int no) {
        System.out.println("进入前序遍历查找");
        //比较当前节点
        if (this.no == no) {
            return this;
        }
        //1.向左递归查找
        //2.如果找到则返回
        HeroNode tempNode = null;//用来存放是否查找到所需要的节点
        if (this.left != null) {
            tempNode = this.left.preOrderSearch(no);
        }
        if (tempNode != null) {//左侧递归找到了
            return tempNode;
        }
        //1.向右递归查找
        //2.如果找到则返回
        if (this.right != null) {
            tempNode = this.right.preOrderSearch(no);
        }
        return tempNode;//此时不管找到还是没找到，都返回tempNode
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {

        HeroNode tempNode = null;
        //1.向左递归查找
        //2.如果找到则返回
        if (this.left != null) {
            tempNode = this.left.infixOrderSearch(no);
        }
        if (tempNode != null) {//左侧找到
            return tempNode;
        }
        //判断当前节点是否满足
        System.out.println("进入中序遍历查找");
        if (this.no == no) {
            return this;
        }
        //1.向右递归查找
        //2.如果找到则返回
        if (this.right != null) {
            tempNode = this.right.infixOrderSearch(no);
        }
        return tempNode;

    }

    //后序遍历查找
    public HeroNode postOrderSearch(int no) {

        HeroNode tempNode = null;
        if (this.left != null) {
            tempNode = this.left.postOrderSearch(no);
        }
        if (tempNode != null) {//找到了
            return tempNode;
        }
        if (this.right != null) {
            tempNode = this.right.postOrderSearch(no);
        }
        if (tempNode != null) {
            return tempNode;
        }
        System.out.println("进入后序遍历查找");
        if (this.no == no) {
            return this;
        }
        return tempNode;
    }

}