/**
 * @author chenyi
 * @Description 二叉树遍历
 * @date 2022/2/17 15:30
 */
public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTreeDemo binaryTreeDemo = new BinaryTreeDemo();
        binaryTreeDemo.init();
        System.out.println("前序遍历");
        binaryTreeDemo.preOrder(binaryTreeDemo.root);
        System.out.println("中序遍历");
        binaryTreeDemo.infixOrder(binaryTreeDemo.root);
        System.out.println("后序遍历");
        binaryTreeDemo.postOrder(binaryTreeDemo.root);
        System.out.println("尝试中序线索化二叉树");
        binaryTreeDemo.threaded(binaryTreeDemo.root);
        System.out.println("线索化中序遍历");
        binaryTreeDemo.threadedList();

        /*System.out.println("测试删除");
        binaryTreeDemo.delNode(binaryTreeDemo.root, 4);
        binaryTreeDemo.infixOrder(binaryTreeDemo.root);*/

    }

    public void threadedList(){
        TreeNode node = root;
        while (node!=null){
            // 先找最左边的节点
            while (node.leftType!=1) {
                node = node.left;
            }
            System.out.println(node.val);
            while(node.rightType==1) {
                node = node.right;
                System.out.println(node.val);
            }
            node = node.right;
        }
    }

    public void threaded(TreeNode node){
        if(node==null){
            return;
        }
        // 线索左子树
        threaded(node.left);
        if(node.left==null) {
            node.leftType=1;
            node.left=node.parent;
        }
        if(node.parent!=null && node.parent.right==null) {
            node.parent.rightType=1;
            node.parent.right=node;
        }
        // 线索右子树
        threaded(node.right);
    }

    private void postOrder(TreeNode node) {
        if(node==null){
            return;
        }
        // 输出左边
        postOrder(node.left);
        // 输出右边
        postOrder(node.right);
        // 输出中间
        System.out.println(node.val);
    }

    private void preOrder(TreeNode node) {
        if(node==null){
            return;
        }
        // 输出中间
        System.out.println(node.val);
        // 输出左边
        preOrder(node.left);
        // 输出右边
        preOrder(node.right);
    }

    private void infixOrder(TreeNode node) {
        if(node==null){
            return;
        }
        // 输出左边
        infixOrder(node.left);
        // 输出中间
        System.out.println(node.val);
        // 输出右边
        infixOrder(node.right);
    }

    private boolean delNode(TreeNode node, int val){
        if(node==this.root){
            if(this.root.val==val) {
                this.root=null;
                return true;
            }
        }
        if(node.left!=null){
            if(node.left.val==val) {
                node.left = null;
                return true;
            }
            if(delNode(node.left, val)) {
                return true;
            }
        }

        if(node.right!=null){
            if(node.right.val==val) {
                node.right = null;
                return true;
            }
            if(delNode(node.right, val)) {
                return true;
            }
        }

        return false;
    }

    TreeNode root;

    public void init() {
        root = new TreeNode(4);
        // 添加第二层的左右节点
        TreeNode rootLeft = new TreeNode(2);
        TreeNode rootRight = new TreeNode(6);
        root.left = rootLeft;
        root.right = rootRight;
        // 添加第三层的左右节点
        TreeNode rootLeftLeft = new TreeNode(1);
        TreeNode rootLeftRight = new TreeNode(3);
        TreeNode rootRightLeft = new TreeNode(5);
        TreeNode rootRightRight = new TreeNode(7);
        rootLeft.left = rootLeftLeft;
        rootLeft.right = rootLeftRight;
        rootRight.left = rootRightLeft;
        rootRight.right = rootRightRight;

        rootLeft.parent=rootLeftLeft;
        rootLeftRight.parent=rootLeft;
        root.parent=rootLeftRight;
        rootRightLeft.parent=root;
        rootRight.parent=rootRightLeft;
        rootRightRight.parent=rootRight;
    }


    static final class TreeNode {
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        int leftType;
        int rightType;
        int val;

        public TreeNode(int val) {
            this.val = val;
        }

    }

}