二叉树

森林、二叉树转换

1.树转换为二叉树

由于二叉树是有序的，所以为了避免混淆，对于无序的树，我们默认每个节点的孩子是从左到右是按顺序排列的。所以转换步骤是：
①加线，将所有的兄弟连成一条线
②去线，只保留树中每个节点与第一个孩子的线
③选择，以树的节点为轴心，选择角度，时他们在节点的右边

2.森林转换为二叉树

森林转换为树，需要先将森林中的每一颗树转换为二叉树。
然后从第二课树开始，依次把后一颗树的根节点作为前一棵树的二叉树的右孩子节点，用线连起来。

3.二叉树转换为树

二叉树转换为树，就是树转换为二叉树的逆过程
1、将所有节点左孩子的右节点全部与该节点连接
2、删除所有子节点与右孩子节点的连线

整理：就是所有孩子的右孩子，全部用父节点连接

4.二叉树转换为森林

①先把每个结点与右孩子结点的连线删除，得到分离的二叉树；
②把分离后的每棵二叉树转换为树；
③整理第②步得到的树，使之规范，这样得到森林。

二叉排序树的删除

思路：先找到需要删除的节点，然后删除该节点，重新建立删除节点附近的节点的关系。用删除节点左子树的最大值或者右子树的最小值取代删除节点的值。
代码：

//查找需要的节点：
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null)
        return null;
    TreeNode parent = null;
    TreeNode curr = root;
    while (curr!=null&&curr.val!=key){
        parent = curr;
        if (curr.val>key){
            curr = curr.left;
        }else {
            curr = curr.right;
        }
    }
    //如果parent为null，那么就是要删除根节点
    if (parent == null){
        return deleteTargetNode(curr);
    }
    if (parent.left == curr) {
        parent.left = deleteTargetNode(curr);
    } else {
        parent.right = deleteTargetNode(curr);
    }
    return root;
}

//删除节点代码：
public TreeNode deleteTargetNode(TreeNode target) {
    if (target == null)
        return null;
    if (target.left == null)
        return target.right;
    if (target.right == null)
        return target.left;
    //用一个指针保存需要删除节点的父节点
    //重新构建删除节点附近的关系,用删除节点的左子树的最大值取代
    TreeNode parent = target;
    //获得删除节点左子树的根节点
    TreeNode curr = target.left;
    while (curr.right!=null){
        //找到左子树的最大值和它的父节点
        parent = curr;
        curr = curr.right;
    }
    curr.right = target.right;
    if (target.left!=curr){
        //因为curr是最大值，所以它一定没有右子树，它的左子树的父节点由curr变成之前保存的parent
        //最大值的父节点的右子树指向最大值的左子树
        parent.right = curr.left;
        //最大值的左子树指向删除节点的左子树
        curr.left = target.left;
    }
    return curr;
}

数据结构导读目录