二叉树按层遍历-插入-删除

三个问题

1. 二叉树按层遍历
2. 给定指定n个节点，二叉树有多少种组合
3. 二叉树插入删除，保持顺序

思路

1. 通过队列保存缓存结果，从root节点开始，然后进队出队，输出结果同时左节点进队右节点进队，直到队列为空。

public void printByLayer() {
        Queue<TreeStruct> queue = new LinkedList<>();
        queue.offer(this);
        TreeStruct temp;
        while (queue.size() > 0) {
            temp = queue.poll();
            assert temp != null;
            System.out.println(temp.value);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

2. 对于第二个问题，已看到就会想到n！。但是二叉树不是完全二叉树。
   卡特兰数
   f(0)=1;f(1) = 1;
   n个数字，1个在根节点其他可能情况。0个在左，n-1个在右；1个在左，n-2个在右；2个在左，n-3个在右。。。
   f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-2)f(1) + f(n-1)f(0)
   Cn = (2n)!/((n+1)!*n!)

3. 插入node，大于等于在右叶子，小于根节点在左叶子。删除节点，1.左右节点空，直接删除；2.左节点空，右节点不为空，找到右节点中最小的替换到删除节点位置；3.左节点不为空，右节点为空，找到左节点中最大的替换到删除节点位置；4.左右节点都不为空，同3一样

Code

public class TreeStruct {

    public TreeStruct() {
    }

    public TreeStruct(Integer value) {
        this.value = value;
    }

    private Integer value;
    private TreeStruct left;
    private TreeStruct right;

    /**
     * 按层输出
     */
    public void printByLayer() {
        Queue<TreeStruct> queue = new LinkedList<>();
        queue.offer(this);
        TreeStruct temp;
        while (queue.size() > 0) {
            temp = queue.poll();
            assert temp != null;
            System.out.println(temp.value);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

    public void printByLayer(Consumer<Integer> consumer) {
        Queue<TreeStruct> queue = new LinkedList<>();
        queue.offer(this);
        TreeStruct temp;
        while (queue.size() > 0) {
            temp = queue.poll();
            assert temp != null;
            consumer.accept(temp.value);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

    /**
     * 遍历
     */
    public void travel() {
        travelRecursion(this);
    }
    /**
     * 前序遍历
     */
    private void travelRecursion(TreeStruct node) {
        if (node != null) {
            System.out.println(node.value);
            travelRecursion(node.getLeft());
            travelRecursion(node.getRight());
        }
    }

    /**
     * 查找
     */
    public TreeStruct find(Integer value) {
        TreeStruct node = this;
        while (node != null) {
            if (node.getValue() > value) {
                node = node.getLeft();
            } else if (node.getValue() < value) {
                node = node.getRight();
            } else {
                return node;
            }
        }
        return null;
    }

    /**
     * 插入node，大于等于在右叶子，小于根节点在左叶子
     */
    public void insertNode(Integer value) {
        TreeStruct node = this;
        while (node != null) {
            if (node.getValue() == null) {
                node.setValue(value);
                break;
            }
            if (node.getValue() < value) {
                if (node.getRight() == null) {
                    node.setRight(new TreeStruct(value));
                    node = null;
                } else {
                    node = node.getRight();
                }
            } else {
                if (node.getLeft() == null) {
                    node.setLeft(new TreeStruct(value));
                    node = null;
                } else {
                    node = node.getLeft();
                }
            }
        }
    }

    /**
     * 删除1个节点，不删除重复数据
     */
    public void deleteNode(Integer value) {
        TreeStruct pre = null;
        TreeStruct node = this;
        while (node != null) {
            if (node.getValue() > value) {
                pre = node;
                node = node.getLeft();
            } else if(node.getValue() < value) {
                pre = node;
                node = node.getRight();
            } else {
                if (node.getLeft() == null) {
                    if (node.getRight() == null) {
                        if (pre == null) {
                            this.value = null;
                        } else {
                            if (pre.getLeft() == node) {
                                pre.setLeft(null);
                            } else if (pre.getRight() == node){
                                pre.setRight(null);
                            }
                        }
                    } else {
                        // left == null && right != null
                        // find right minimum element
                        TreeStruct tempPre = null;
                        TreeStruct temp = node.getRight();
                        while (temp.getLeft() != null) {
                            tempPre = temp;
                            temp = temp.getLeft();
                        }
                        // remove temp
                        if (tempPre != null) {
                            tempPre.setLeft(null);
                        } else {
                            node.setRight(null);
                        }
                        // move temp to node
                        temp.setLeft(node.getLeft());
                        temp.setRight(node.getRight());
                        if (pre != null) {
                            if (pre.getLeft() == node) {
                                pre.setLeft(temp);
                            } else if (pre.getRight() == node) {
                                pre.setRight(temp);
                            }
                        }
                    }
                } else {
                    // left != null && right == null || left != null && right != null
                    // find left maximum element
                    TreeStruct tempPre = null;
                    TreeStruct temp = node.getLeft();
                    while (temp.getRight() != null) {
                        tempPre = temp;
                        temp = temp.getRight();
                    }
                    // remove temp
                    if (tempPre != null) {
                        tempPre.setRight(null);
                    } else {
                        node.setLeft(null);
                    }
                    // move temp to node
                    temp.setLeft(node.getLeft());
                    temp.setRight(node.getRight());
                    if (pre != null) {
                        if (pre.getLeft() == node) {
                            pre.setLeft(temp);
                        } else if (pre.getRight() == node) {
                            pre.setRight(temp);
                        }
                    } else {
                        this.value = temp.getValue();
                    }
                }
                break;
            }
        }
    }

    /**
     * 数高
     */
    public Integer height() {
        return height(this);
    }

    private Integer height(TreeStruct treeStruct) {
        if (treeStruct == null) {
            return 0;
        } else {
            Integer leftHeight = height(treeStruct.getLeft());
            Integer rightHeight = height(treeStruct.getRight());
            return leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
        }
    }
}