代码之家 › 专栏 › 技术社区 › stevenpcurtis

二叉搜索树中节点的后继者-Swift

nodes binary-search-tree algorithm swift

stevenpcurtis · 技术社区 · 8 年前

在二叉树中求节点的后继者s.t.树

具有以下继承者:对于8->10,10->12和14->20

我的算法是:

func inorderSucc(_ node: Node? = nil) -> Node? {
    if (node == nil) {
        return nil
    } else {
        if let rhn = node?.right {
            return leftMostChild(rhn)
        } else {
            var q = node
            var x = node?.parent
            while (x != nil && x!.left != q) {
                q = x
                x = x?.parent
            }
            return x
        }
    }
}

func leftMostChild(_ n: Node) -> Node? {
    var node = n
    while (node.left != nil) {
        node = node.left!
    }
    return node
}

class Node : CustomStringConvertible, Hashable{
    var hashValue : Int { return data}
    static func == (lhs: Node, rhs: Node) -> Bool {
        return lhs.data == rhs.data
    }

    var data : Int
    var left : Node?
    var right : Node?
    var parent : Node? = nil
    var description: String {
        return String(data) + (left?.description ?? "") + (right?.description ?? "")
    }

    init(_ data: Int) {
        self.data = data
    }

    func insert(_ data: Int) {
        if (data < self.data){
            if let lhs = left {
                lhs.insert(data)
            }
            else {
                let lhNode = Node(data)
                lhNode.parent = self
                left = lhNode
            }
        }
        else {
            if let rhs = right {
                rhs.insert(data)
            }
            else {
                let rhNode = Node(data)
                rhNode.parent = self
                right = rhNode
            }
        }
    }
}

顺序搜索是:

func inorderSearch (_ node: Node, _ data: Int) -> Node? {
    if (node.data == data) {return node}
    else {
        if let lft = node.left {
            return inorderSearch(lft, data)
        }

        if let rht = node.right {
            return inorderSearch(rht, data)
        }

    }

    return nil
}

我插入节点如下:

let gfg = Node(20)
gfg.insert(8)
gfg.insert(4)
gfg.insert(12)
gfg.insert(10)
gfg.insert(14)
gfg.insert(22)
print (gfg)
inorderSucc(inorderSearch(gfg, 8))
inorderSucc(inorderSearch(gfg, 10))
inorderSucc(inorderSearch(gfg, 14))

2 回复 | 直到 8 年前

JBL 8 年前

这个问题源于你的搜索功能。想想如果在最左边的分支(左节点的左节点的子节点等)上找不到实际的数目会发生什么。。。根节点的)。一个可能的修正是检查 nil

func inorderSearch (_ node: Node, _ data: Int) -> Node? {
    if (node.data == data) {return node}
    else {
        if let lft = node.left, let found = inorderSearch(lft, data) {
            return found
        } else if let rht = node.right, let found = inorderSearch(rht, data) {
            return found
        } else {
            return nil
        }
    }
}

tBug 7 年前

你可以这样做:

class Node {
    let value: Int
    var leftChield: Node?
    var rightChield: Node?

    init(value: Int, leftChield: Node?, rightChield: Node?) {
        self.value = value
        self.leftChield = leftChield
        self.rightChield = rightChield
    }    
}

然后创建所有分支:

    //Left Branch
    let tenNode = Node(value: 10, leftChield: nil, rightChield: nil)
    let fourteenNode = Node(value: 14, leftChield: nil, rightChield: nil)
    let twelveNode = Node(value: 12, leftChield: tenNode, rightChield: fourteenNode)
    let foureNode = Node(value: 4, leftChield: nil, rightChield: nil)
    let eithNode = Node(value: 8, leftChield: foureNode, rightChield: twelveNode)

    //Right Branch
    let twentytwoNode = Node(value: 22, leftChield: nil, rightChield: nil)

    // Root Node
    let rootTwentyNode = Node(value: 20, leftChield: eithNode, rightChield: twentytwoNode)

        func binarySearch(node: Node?, searchValue: Int) -> Bool {

            if node == nil {
                return false
            }

            if node?.value == searchValue {
                return true
            } else if searchValue < node!.value {
                return binarySearch(node: node?.leftChield, searchValue: searchValue)
            } else {
                return binarySearch(node: node?.rightChield, searchValue: searchValue)
            }
        }

最后,像这样调用函数,并使用所需的值添加rootNode。

binarySearch(node: rootNode, searchValue: 50)