7.二叉树前驱节点、后继节点、删除节点

• 前序遍历+中序遍历，结果唯一

• 后序遍历+中序遍历，结果唯一

• 前序遍历+后序遍历，如果是一颗真二叉树，结果唯一。因为非真二叉树，只有一个子节点时，无法确定子节点是左节点还是右节点。

前驱节点：中序遍历时的前一个节点

• 如果是二叉搜索树，前驱节点就是左子树中的最大值。

• 通用：存在左节点，前驱节点就是左子树的最右的节点。(4,8,13)

• 通用：不存在左节点，前驱节点就是父节点链条上位于右节点上第一个位于右节点的父节点(5,9,11)

// 前驱节点
    func predecessor(note:Note){
        if(note.parent == nil && note.leftNote == nil && note.rightNote == nil){
            print("单个节点的树直接返回")
            return
        }
        // 如果有左节点，那么就是左节点最右的一个节点
        if var leftNote = note.leftNote {
            while(leftNote.rightNote != nil){
                leftNote = leftNote.rightNote!
            }
            print("前驱节点：\(leftNote.value)")
            return
        }
        // 如果没有左节点，那么就是父节点链条上第一个位于右节点的父节点
        // 父节点链条
        var temp = note
        while(temp.parent != nil){
            let parama = temp.parent!
            if let predecessor = parama.parent {
                if let predecessorRightValue = predecessor.rightNote?.value {
                    // 父节点位于右节点
                    if(predecessorRightValue == parama.value){
                        print("前驱节点：\(predecessor.value)")
                        return
                    }
                }
            }
            temp = parama
        }
        print("无前驱节点")
    }

后继节点（successor）：中序遍历时的后一个节点

• 如果right !=nil，successor = note.right.left.left.left...

• right != nil && parent != nil，那么就沿着节点的父节点链条，找到最后一个位于左节点的节点（7，6，3，11）

• 其他情况没有后继节点

删除节点

• 叶子节点，直接值为空

• 度为1的节点

  • 父节点指向子节点，子节点的父节点设置为祖父节点

  • root，root = child,child，parent = nil

• 度为2的节点

  • 删除根节点，找到前驱或者后继节点，用节点的值覆盖，把替换的节点删掉

  • 如果一个节点的度为2，那么它的前驱、后继节点的度要么为0，要么为1