import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class BinaryTreeNode<T extends Comparable<T>> implements Comparable<T> {
    public T data;
    public BinaryTreeNode<T> parent;
    public BinaryTreeNode<T> childL;
    public BinaryTreeNode<T> childR;

    public BinaryTreeNode() {
        this(null);
    }

    public BinaryTreeNode(T data) {
        this(data, null);
    }

    public BinaryTreeNode(T data, BinaryTreeNode<T> parent) {
        this(data, parent, null, null);
    }

    public BinaryTreeNode(T data, BinaryTreeNode<T> parent, BinaryTreeNode<T> childL, BinaryTreeNode<T> childR) {
        super();
        this.data = data;
        this.parent = parent;
        this.childL = childL;
        this.childR = childR;
    }

    @Override
    public int compareTo(T e) {
        if (data == e) {
            return 0;
        }
        if (data == null) {
            return -1;
        }
        if (e == null) {
            return 1;
        }
        return data.compareTo(e);
    }

    @Override
    public String toString() {
        return String.valueOf(data);
    }

    //获得当前树的跟节点
    public final BinaryTreeNode<T> getRoot() {
        if (parent == null) {
            return this;
        }
        BinaryTreeNode<T> root = parent;
        while (root.parent != null) {
            root = root.parent;
        }
        return root;
    }

    public final BinaryTreeNode<T> find(T target) {
        int i;
        BinaryTreeNode<T> node = this;
        while (true) {
            i = node.compareTo(target);
            if (i > 0) {
                if (node.childL != null) {
                    node = node.childL;
                } else {
                    return null;
                }
            } else if (i < 0) {
                if (node.childR != null) {
                    node = node.childR;
                } else {
                    return null;
                }
            } else {
                return node;
            }
        }
    }

    public final void add(T element) {
        if (element == null) {
            return;
        }
        if (this.data == null) {
            this.data = element;
            return;
        }
        int i;
        BinaryTreeNode<T> node = this;
        while (true) {
            i = node.compareTo(element);
            if (i > 0) {
                if (node.childL != null) {
                    node = node.childL;
                } else {
                    node.childL = new BinaryTreeNode<>(element, node);
                }
            } else if (i < 0) {
                if (node.childR != null) {
                    node = node.childR;
                } else {
                    node.childR = new BinaryTreeNode<>(element, node);
                }
            } else {
                return;
            }
        }
    }

    //删除当前节点
    public final void del() {
        BinaryTreeNode<T> replace;
        //如果具有左节点则取左边最大值进行替换
        if ((replace = this.childL) != null) {
            while (replace.childR != null) {
                replace = replace.childR;//循环找到左侧最大元素
            }
            //替补节点是删除节点的左节点
            if (this.childL == replace) {
                this.childL = replace.childL;
            } else {
                replace.parent.childR = replace.childL;
            }
            //移交替补可能存在的子节点
            if (replace.childL != null) {
                replace.childL.parent = replace.parent;
            }
        } else if ((replace = this.childR) != null) {
            //如果具有右节点则取右边最小值进行替换
            while (replace.childL != null) {
                replace = replace.childL;//循环找到右侧最大元素
            }
            if (this.childR == replace) {
                this.childR = replace.childR;
            } else {
                replace.parent.childL = replace.childR;
            }
            if (replace.childR != null) {
                replace.childR.parent = replace.parent;
            }
        }
        //为空表示删除的是叶节点
        if (replace == null) {
            this.data = null;
            if (this.parent != null) {
                if (this.parent.childL == this) {
                    this.parent.childL = null;
                } else {
                    this.parent.childR = null;
                }
                this.parent = null;
            }
        } else {
            this.data = replace.data;
            replace.parent = null;
        }
    }

    /**
     * 中序遍历
     */
    public void midOrderTraverse(BinaryTreeNode<T> root) {
        if (root == null || root.data == null) {
            return;
        }
        //LDR
        midOrderTraverse(root.childL);
        System.out.print(root.data);
        System.out.print(',');
        System.out.print(' ');
        midOrderTraverse(root.childR);
    }

    //非递归的中序遍历求和
    public int inTraverseSum(BinaryTreeNode<T> root) {
        Stack<BinaryTreeNode> st = new Stack<>();
        BinaryTreeNode<T> p = root;
        int count = 0;
        while (p != null || !st.empty()) {
            while (p != null) {
                st.push(p);
                count++;
                p = p.childL;
            }
            if (!st.empty()) {
                p = st.peek();
                st.pop();
                p = p.childR;
            }
        }
        return count;
    }

    public void MorrisIn(BinaryTreeNode<T> head) {
        if (head == null) return;
        BinaryTreeNode<T> cur = head;
        BinaryTreeNode<T> mostRight;
        while (cur != null) {
            mostRight = cur.childL;
            //【1、2、】判断Cur的左孩子是否为空
            if (cur.childL != null) {
                //不断向右寻找Cur左子树最右的节点【mostRight右节点不为空 或者 不为当前cur节点，则非最右】
                while (mostRight.childR != null && mostRight.childR != cur) {
                    mostRight = mostRight.childR;
                }
                // { 隐含意思：为空表示第一次来到该节点位置，为cur表示第二次来到该节点位置 }
                //【2、(1)、】若最右节点为空
                if (mostRight.childR == null) {
                    //{ 第一次来到该节点， 将该节右指针设为cur，表示该节点下一步将移动到cur }
                    mostRight.childR = cur;
                    cur = cur.childL;
                    continue;
                } else {
                    //【2、(2)、】若最右节点为当前节点cur
                    /** { 第二次来到该节点， 将该节点右指针设为原来的null，
                     前一步其实已经将当前cur指针指向了该节点的右节点了，
                     即当前的cur已经是当前mostright的下一步节点了} */
                    mostRight.childR = null;
                }
            } else {//当前cur没有左孩子的时候
            }
            //【---【中序遍历】： 当前指针cur要准备往右孩子走了，马上打印】
            System.out.print(cur.data);
            //【1、】Cur的左孩子为空 或者【 2、(2)、】mostright的右孩子为Cur，即第二次访问到该节点的时候
            cur = cur.childR;
        }
    }

    public static void main(String[] args) {
        BinaryTreeNode<Integer> tree = new BinaryTreeNode<>();
        int[] arr = new int[16];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(99);
            tree.add(arr[i]);
        }
        System.out.print("插入数据：");
        System.out.println(Arrays.toString(arr));
        System.out.print("数据排序：");
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.print("二叉树序：[");
        tree.midOrderTraverse(tree);
        System.out.println();
        System.out.println(tree.inTraverseSum(tree));
        System.out.println("----");
        tree.MorrisIn(tree);
        BinaryTreeNode<Integer> del;
        for (int i = 0; i < arr.length; i++) {
            System.out.print("删除数字");
            System.out.println(arr[i]);
            del = tree.find(arr[i]);
            if (del != null) {
                del.del();
            }
            tree.midOrderTraverse(tree);
            System.out.println();
            tree.add(arr[i]);
        }
        System.out.println("逐个删除：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print("删除数字");
            System.out.println(arr[i]);
            del = tree.find(arr[i]);
            if (del != null) {
                del.del();
            }
            tree.midOrderTraverse(tree);
            System.out.println();
        }
    }
}