/**
 * 树节点
 */
public class Treenode {
    //节点权
    int data ;
    //左子节点
    Treenode leftNode;
    //右子节点
    Treenode rightNode;

    public Treenode(int data){
        this.data = data;
    }

    public void setLeftNode(Treenode leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(Treenode rightNode) {
        this.rightNode = rightNode;
    }


    /**
     * 前序遍历：先取父节点，再去左子节点，右子节点
     */
    public  void frontShow() {
        //输出根节点节点权
        System.out.print(this.data);
        //在取左子节点，先判断是否有左子节点
        if(this.leftNode!=null){
            this.leftNode.frontShow();
        }
        //再取右子节点
        if(this.rightNode!=null){
            this.rightNode.frontShow();
        }
    }
    /**
     * 中序遍历：先取左子节点，父节点，右子节点
     */
    public void midShow(){
        if(leftNode!=null){
            leftNode.midShow();
        }
        System.out.print(data);
        if(rightNode!=null){
            midShow();
        }
    }

    /**
     * 后序遍历：先取左子节点，右子节点，父节点
     */
    public void lastShow(){
        if(leftNode!=null){
            leftNode.lastShow();
        }
        if(rightNode!=null){
            rightNode.lastShow();
        }
        System.out.print(data);
    }

    /**
     * 二叉树查找
     */
    public Treenode binarySearch(int i){
        Treenode target = null;
        //先看当前节点权
        if(this.data == i){
            return this;
        }else{
            //在看左子节点
            if(leftNode!=null){
                target=leftNode.binarySearch(i);
            }
            //target不为空说明在左子节点找到了
            if(target!=null){
                return target;
            }
            if(rightNode!=null){
                target = rightNode.binarySearch(i);
            }
        }
        return target;
    }
    /**
     * 删除节点
     */
    public void delete(int i){
        //用于保存被删除节点的父节点,因为当找到要删除的节点时，不知道它的父节点是哪个，所以先保存下
        Treenode parent= this;
        //判断左子节点
        if(parent.leftNode.data==i){
            parent.leftNode=null;
            return;
        }
        //在判断右子节点
        if(parent.rightNode.data==i){
            parent.rightNode=null;
            return;
        }
        //如果第二层节点没找到，那么第二层节点就当做被删除节点的父节点继续执行
        //左子节点
        parent=leftNode;
        if(parent!=null){
            parent.delete(i);
        }
        //右子节点
        parent=rightNode;
        if(parent!=null){
            parent.delete(i);
        }
    }
}

/**
 * 二叉树
 */
public class Binarytree {
    //根节点
    Treenode rootNode;

    public void setRootNode(Treenode rootNode) {
        this.rootNode = rootNode;
    }

    public Treenode getRootNode() {
        return rootNode;
    }
    //前序遍历
    public void frontShow(){
        if(rootNode!=null){
            rootNode.frontShow();

        }
    }
    //中序遍历
    public void midShow(){
        if(rootNode!=null){
            rootNode.midShow();

        }
    }
    //后序遍历
    public void lashShow(){
        if(rootNode!=null){
            rootNode.lastShow();
        }
    }
    //二叉树查找（前序）
    public Treenode binarySearch(int i){
        return rootNode.binarySearch(i);
    }

    //删除节点
    public void delete(int data){
        if(rootNode!=null&&rootNode.data==data){
            rootNode=null;
        }else {
            rootNode.delete(data);
        }
    }
}