算法系列15天速成 第六天 五大经典查找【下】

//找到右子树中的最左节点
                    while (node.left != null)
                    {
                        //遍历它的左子树
                        node = node.left;
                    }

//交换左右孩子
                    node.left = bsTree.left;

//判断是真正的叶子节点还是空左孩子的父节点
                    if (node.right == null)
                    {
                        //删除掉右子树最左节点
                        DeleteBST(ref bsTree, node.data);

node.right = bsTree.right;
                    }
                    //重新赋值一下
                    bsTree = node;

}
            }

if (bsTree.data > key)
            {
                DeleteBST(ref bsTree.left, key);
            }
            else
            {
                DeleteBST(ref bsTree.right, key);
            }
        }
    }
}

运行结果：

值的注意的是：二叉排序树同样采用“空间换时间”的做法。

突然发现，二叉排序树的中序遍历同样可以排序数组，呵呵，不错！

PS:  插入操作：O(LogN)。
       删除操作：O(LogN)。
       查找操作：O(LogN）。

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!