（Swift 实现）二叉搜索树 —— 创建，最大，最小，查找，插入，删除，前驱，后继，中序遍历

概述了解了二叉堆之后，二叉搜索树就好说了，就是一个节点，左边的子节点是不可能比他大的，右边的子节点是一定大于它的，想了半天终于把创建给写好了。 创建 import UIKitvar str = "二叉搜索树"//这个就不跟前面的完全二叉树一样了，得自己建了类或者结构体了，我建了个类class erchaTreeNote { var data: Int var leftChil

了解了二叉堆之后，二叉搜索树就好说了，就是一个节点，左边的子节点是不可能比他大的，右边的子节点是一定大于它的，想了半天终于把创建给写好了。

创建

import UIKitvar str = "二叉搜索树"//这个就不跟前面的完全二叉树一样了，得自己建了类或者结构体了，我建了个类class erchaTreeNote {    var  data: Int    var leftChild: erchaTreeNote!    var rightChild: erchaTreeNote!    init(data:Int) {        self.data = data    }}var a = [12,321,432,213,423,4]func createTree() -> (erchaTreeNote) {    let root = erchaTreeNote(data:a[0]);    for x in a[1...a.count-1] {        let child = erchaTreeNote(data: x)        var temp = root        //循环的条件想了半天，想着如何能走下去，在纸上练了几遍，发现了规律，本来进来一个数如果它加进去了，它的左右子节点都是空的，再往下就不走了，但是这个是走不通的，再想他们有什么共性，我就想，既然把它按在了树上，那它再走一次，必然和上一次的路径是一样的，当我找到和它一模一样的时候，就是结束的时候，如果我找不到它，一直都不能结束。就按这个条件走就出来了。        while temp !== child {        //如果进来的数小于父节点            if child.data < temp.data {            //不为空，那我就把父节点左边子节点拿上，再重新来过                if temp.leftChild != nil                {                    temp = temp.leftChild                }             //当父节点左边是空的时候，那就直接填上                else                {                    temp.leftChild = child                         print("\(temp.data)左边的孩子")                    temp = child //优化语句                }            }else //进来的数大于父节点            {            //不为空，那我就把父节点右边子节点拿上，重新来过                if temp.rightChild != nil {                    temp = temp.rightChild                }            //当父节点的右边为空的时候，那就直接补上                 else                {                    temp.rightChild = child                    print("\(temp.data)右边的孩子")                    temp = child //优化语句                }               }        }        print(child.data)    }    return root}createTree()

最大值和最小值

//找到最大的，那就直接朝右走下去，最小则是朝左走下去func FindMax(_ shu:erchaTreeNote) -> (erchaTreeNote){    var temp = shu    //如果右边不为空，一直找下去    while temp.rightChild != nil {        temp = temp.rightChild    }    return temp}//最小func FindMin(_ shu:erchaTreeNote) -> (erchaTreeNote){    var temp = shu    //如果左边不为空，一直找下去    while  temp.leftChild != nil {        temp = temp.leftChild    }    return temp}

查找

//找到特定的那个数,这个我发现如果两个一样的数字，可能进入树的时间不一样，所以他们位置也就不一样，得把这棵树可能的条件都循环完毕才可以func Findfrom(_ shu:erchaTreeNote,_ mubiao:Int) -> ( Array<erchaTreeNote>){    var temp = shu    var arr = Array<erchaTreeNote>()    while true{        if temp.data < mubiao        {            if temp.rightChild != nil            {               print("拐进右边\(temp.rightChild.data)")               temp = temp.rightChild            }            else            {                print("没有啦")                break            }        }        else if temp.data > mubiao        {            if temp.leftChild != nil            {                print("拐进左边\(temp.leftChild.data)")                temp = temp.leftChild            }            else            {                print("没有啦")                break            }        }        else        {            print("找到啦它就是\(temp.data)")            //找到它的时候给它加载数组里，不确定还有没有一样的存在            arr.append(temp)            if (temp.rightChild != nil)            {                print("下面还有东西呢\(temp.rightChild.data)")                temp = temp.rightChild            }            else            {                break            }        }    }    return arr}

插入

//插入，其实就跟创建是一模一样，只不过多了一个数而已func insert(_ shu:erchaTreeNote,_ x :Int) -> (erchaTreeNote){    func digui (_ ee: erchaTreeNote)    {        if ee.data > x {            if ee.leftChild != nil            {                digui(ee.leftChild)            }            else            {                print("它的父节点是\(ee.data).他在左边")                ee.leftChild = erchaTreeNote(data: x)            }        }        else        {            if ee.rightChild != nil            {                digui(ee.rightChild)            }            else            {                print("它的父节点是\(ee.data).他在右边")                ee.rightChild = erchaTreeNote(data: x)            }        }    }    digui(shu)    return shu}

删除

删除好做，但是得找到那个能顶替它原来位置的节点，我这里只是打印出来，因为没有父节点，不好去找，所以就没做。。

//移除的逻辑也简单易懂，删除这个节点，如果有右节点，再去找右边最小的那个顶上，如果没有右节点，左节点顶上，要是都木有，那就删了func yichu(_ shu:erchaTreeNote,_ x:Int){    //先找到这个节点,因为里面可能有重复的情况发生，所以得删个几次，我们从最深的那个删起    let arr = Findfrom(shu,x)    arr.count    for i in 0..<arr.count    {        let temp = arr[arr.count - i - 1]        if temp.rightChild != nil        {            print("删了\(temp.data),与\(FindMin(temp.rightChild).data)发生调换")        }        else if temp.leftChild != nil        {            FindMax(temp.rightChild)            print("删了\(temp.data),与\(FindMax(temp.rightChild).data)发生调换")        }        else        {            print("删了\(temp.data),没有发生调换")        }    }}

前驱

//前驱，一个节点的前驱是指所有比它小的节点里面最大的那个；func Getpredecessor(_ shu:erchaTreeNote,_ x :Int) -> (erchaTreeNote){    let arr = Findfrom(shu,x)    for temp in arr    {        if temp.leftChild != nil        {            return FindMin(temp.leftChild)        }        else        {            return temp        }    }    print("\(x)并没有找到")    return erchaTreeNote(data: -1)}

后继

//后继，一个节点的后继是指所有比它大的节点里面最小的那个func GetSuccessor(_ shu:erchaTreeNote,x)    for temp in arr    {        if temp.rightChild != nil        {            return FindMax(temp.rightChild)        }        else        {            return temp        }    }    print("\(x)并没有找到")    return erchaTreeNote(data: -1)}

中序遍历

//遍历 Inorder Traversal 中序遍历，中序遍历就是先左后右，很直观的输出数字。func InorderTra(_ shu:erchaTreeNote){    var arr = Array<erchaTreeNote>()    func lunhui(_ shu:erchaTreeNote)    {        if shu.leftChild != nil        {            arr.append(shu)            lunhui(shu.leftChild)        }        else        {            print(shu.data)            let beis = arr.remove(at: arr.count-1)            print(beis.data)            if(beis.rightChild != nil) {                lunhui(beis.rightChild)            }        }    }    lunhui(shu)}

就酱，还是蛮有成就感的。要是不对，咱们一起讨论，当然里面的一些极端情况我没有做判断，只是想着熟悉下思路。

总结

以上是内存溢出为你收集整理的（Swift 实现）二叉搜索树 —— 创建，最大，最小，查找，插入，删除，前驱，后继，中序遍历全部内容，希望文章能够帮你解决（Swift 实现）二叉搜索树 —— 创建，最大，最小，查找，插入，删除，前驱，后继，中序遍历所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。