• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

基本概念

二叉排序树(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)
        }
 }

  • 图示查找过程

二叉排序树插入

  • 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
        }
}

  • 图示插入过程

二叉排序树创建

  • 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
        }
}
    
  • 图示删除过程

删除左右子树都有的结点

  • 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)
}
    
  • 图示删除过程

总结

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

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
女神画廊App (Swift1.2)发布时间:2022-07-13
下一篇:
Swift网络封装库Moya中文手册之Targets发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap