数据结构与算法-二叉排序树创建、查找、删除(Swift实现)

￡神魔★判官ぃ 2022-03-28 05:30 187阅读 0赞

### 概要 ###

*   *   *  基本概念
         *  二叉排序树查找
         *  二叉排序树插入
         *  二叉排序树创建
         *  二叉排序树删除
         *   *  删除叶子结点或仅有左右子树之一的结点
             *  删除左右子树都有的结点
         *  总结

### 基本概念 ###

> 二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
> 
> >  *  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
> >  *  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
> >  *  它的左、右子树也分别为二叉排序树。

### 二叉排序树查找 ###

*  Swift代码实现

//二叉树结点
    class BinaryTreeNode {
        var data: Int                   //结点存储数据
        var leftChild: BinaryTreeNode?  //左孩子指针
        var rightChild: BinaryTreeNode? //右孩子指针
        
        //初始化方法
        init(data: Int) {
            self.data = data
        }
    }
    
    //二叉排序树查找结果
    class SearchResult {
        //存储查找的结点，如果查找成功就是当前查找成功的结点
        var searchNode: BinaryTreeNode?
        
        //存储当前查找结点的直接父母结点
        var parentNode: BinaryTreeNode?
        
        //查找成功为true,查找失败为false
        var isFound: Bool = false
    }
    
    /**
     * 二叉排序树查找
     * @param currentRoot 当前二叉排序树的根结点或子树的根结点
     * @param parentNote  currentRoot的父母结点，如果currentRoot是整个二叉排序树的根结点，则该参数为nil
     * @param key         查找的关键字
     *
     * @return            返回查找的结果对象 
     */
     fileprivate func searchBST(currentRoot: BinaryTreeNode?,
                                   parentNode: BinaryTreeNode?,
                                   key: Int) -> SearchResult {
            let searchResult = SearchResult()
            
            //查找失败，返回该结点的父母结点（便于插入）
            if currentRoot == nil {
                searchResult.parentNode = parentNode
                searchResult.isFound = false
                return searchResult
            }
            
            //查找成功，返回查找成功的结点，将isFound设置为true
            if key == currentRoot!.data {
                searchResult.searchNode = currentRoot
                searchResult.parentNode = parentNode
                searchResult.isFound = true
                return searchResult
            }
            
            if key < currentRoot!.data { //在左子树继续查找
                return searchBST(currentRoot:currentRoot?.leftChild, parentNode: currentRoot, key: key)
            } else { //在右子树继续查找
                return searchBST(currentRoot:currentRoot?.rightChild, parentNode: currentRoot, key: key)
            }
     }

*  图示查找过程  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70][]

### 二叉排序树插入 ###

*  Swift代码实现

/**
     * 二叉排序树插入
     * @param parentNote 待插入结点的父母结点
     * @param key        待插入的数据
     */
    fileprivate func insertBST(parentNode: BinaryTreeNode?, key: Int) {
            //创建结点
            let node = BinaryTreeNode(data: key)
            
            //如果parentNote为nil,说明当前二叉排序树为空树
            guard parentNode != nil else {
                rootNode = node //待插入结点更新为整个二叉排序树的根结点
                return
            }
            
            if key < parentNode!.data { //插入为左孩子
                parentNode?.leftChild = node
            } else { //插入为右孩子
                parentNode?.rightChild = node
            }
    }

*  图示插入过程  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 1][]

### 二叉排序树创建 ###

*  Swift代码实现  
    ***二叉排序树的创建就是不断查找和插入的过程。***

/**
     * 根据提供的集合创建二叉排序树
     */
    fileprivate func createBST() {
            for key in items {
                //查找key
                let searchResult = searchBST(currentRoot: rootNode, parentNode: nil, key: key)
                
                //如果查找失败，则插入到二叉排序树上
                if !searchResult.isFound {
                    insertBST(parentNode: searchResult.parentNode, key: key)
                }
            }
    }

### 二叉排序树删除 ###

#### 删除叶子结点或仅有左右子树之一的结点 ####

*  Swfit代码实现

/**
     * 待删除的结点是叶子结点或者只有一个孩子
     * @param searchResult 待删除结点搜索结果
     * @param subNote      待删除结点孩子
     */
    fileprivate func deleteNodeWithZeroOrOneChild(searchResult: SearchResult, subNode: BinaryTreeNode?) {
            //将待删除结点的左右孩子指针置空
            searchResult.searchNode?.leftChild = nil
            searchResult.searchNode?.rightChild = nil
            
            guard let parentNode = searchResult.parentNode else { //如果待删除结点为整个二叉排序树的根结点
                rootNode = subNode //更新根结点
                return
            }
            
            if searchResult.searchNode!.data < parentNode.data { //待删除结点的孩子成为待删除结点父母结点的左孩子
                parentNode.leftChild = subNode
            } else { //待删除结点的孩子成为待删除结点父母结点的右孩子
                parentNode.rightChild = subNode
            }
    }

*  图示删除过程

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 3][]

#### 删除左右子树都有的结点 ####

*  Swift代码实现

/**
     * 待删除的结点有左右子树
     *
     * 这边以待删除结点右子树最左边的结点(最小)覆盖、删除为例。然取左子树最右边的结点亦可！！！
     */
    fileprivate func deleteNodeWithTwoChild(searchResult: SearchResult) {
            //初始化游标结果对象，用于存储右子树最小结点（最左边）
            let cursorResult = SearchResult()
            cursorResult.parentNode = searchResult.searchNode
            cursorResult.searchNode = searchResult.searchNode?.rightChild
            cursorResult.isFound = false
            
            //寻找待删除结点右子树最左边的结点
            while cursorResult.searchNode?.leftChild != nil {
                cursorResult.parentNode = cursorResult.searchNode
                cursorResult.searchNode = cursorResult.searchNode?.leftChild
            }
            
            //将右子树最左边的结点赋值给待删除结点
            searchResult.searchNode!.data = cursorResult.searchNode!.data
            
            //删除右子树最左边的结点
            deleteBST(searchResult: cursorResult)
    }

*  图示删除过程

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 5][]

### 总结 ###

*  二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。
 *  而对于二叉排序树的查找，走的就是从根结点到要查找结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过数的深度。
 *  也就是说，二叉排序树的查找性能取决于二叉排序树的形状。因插入和删除亦依赖于查找，故而，如何构建一棵平衡的二叉排序树（深度与完全二叉树相同，即深度最小）显得尤为重要。
 *  本篇博客只对二叉排序树的核心代码进行了介绍，完整实例请移步[github][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70]: /images/20220328/81f9db0134964fa5a7acaef9e1d3b890.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 1]: /images/20220328/cd157ab8c2df469f8b56f4589d32e1aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 2]: /images/20220328/bb1f422977834abe99d0bc66ca9bfcfb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 3]: /images/20220328/7296260abb68475cb3336d5ff0fc8675.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 4]: /images/20220328/896e872cd21742e5bc9c91cafe3cb24a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 5]: /images/20220328/aa1d770cd7564f4b92e18aaf0fec6d84.png
[github]: https://github.com/shengguoqiang/DQSSourceCode.git