【基础】9、二叉树（三）

2014-02-09 | 阅读：

二叉树删除

一、删除叶子节点

◼ 直接删除
node == node.parent.left
✓ node.parent.left = null

node == node.parent.right
✓ node.parent.right = null

node.parent == null
✓ root = null

二、删除度为1的节点

child 是 node.left 或者 child 是 node.right
用 child 替代 node 的位置

✓ 如果 node 是左子节点
➢ child.parent = node.parent
➢ node.parent.left = child

✓ 如果 node 是右子节点
➢ child.parent = node.parent
➢ node.parent.right = child

✓ 如果 node 是根节点
➢ root = child
➢ child.parent = null

三、删除度为2的节点

◼ 举例：先删除 5、再删除 4
◼ 先用前驱或者后继节点的值覆盖原节点的值
◼ 然后删除相应的前驱或者后继节点
◼ 如果一个节点的度为 2，那么
它的前驱、后继节点的度只可能是 1 和 0

四、代码实现

-(void)__removeNode:(LCBTNode*)node{
    if(!node) return;
    
    _size--;
    
    /**
     删除度为2的节点策略：
     对于二叉搜索树删除度为2的节点，应该找到其前驱或后继节点来顶替被删除的节点。
     因为前驱或后继节点在中序排序中是紧挨着被删除节点的，这样不会破坏二叉搜索树的性质
     */
    
    
    if ([node degree] == 2) {//度为2的节点
        //找到后继节点（因为度为2，后继节点一定存在）
        LCBTNode * s = [self __successor:node];
        
        //将当前要删除的节点内容替换为后继节点内容
        
        node->_element = s->_element;
        
        /**
         重要：度为2的节点的前驱节点和后继节点的度一定为1或者0，不可能为2；
         所以删除一个度为2的节点就转化为了删除一个度为1或者0的节点。
         */
        
        //删除当前节点转化为删除后继节点
        node = s;
    }
    
    
    LCBTNode* replaceNode = node->_left?node->_left:node->_right;
    
    if (replaceNode) {//replaceNode存在，node是度为1的节点
        
        replaceNode->_parent = node->_parent;
        
        if (!node->_parent) {//node是根节点
            _root = replaceNode;
        }else if(node == node->_parent->_left){
            node->_parent->_left = replaceNode;
        }else{
            node->_parent->_right = replaceNode;
        }
        
    }else{//replaceNode为空，node是度为0的节点（叶子节点）
        
        if (!node->_parent) {//node是根节点
            _root = nil;
        }else if(node == node->_parent->_left){
            node->_parent->_left = nil;
        }else{
            node->_parent->_right = nil;
        }
        
    }
}