Преемник узла в бинарном дереве поиска - Swift

Question

Попытка найти преемника для узла в двоичном дереве на дереве

имеет следующих преемников: для 8 -> 10,10 -> 12 и 14 -> 20

Однако для 10 я возвращаю ноль (и, действительно, для 14 я возвращаю ноль).

Мой алгоритм:

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

inorderSearch:

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))

С помощьюпоследние три строки возвращают 10, ноль и ноль соответственно.Что не так?

Answer 1

Вы можете сделать это так:

Сначала объявите класс Node следующим образом:

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)

Answer 2

Проблема связана с вашей функцией поиска.Подумайте о том, что происходит, если он не находит фактическое число в самой левой ветви (дочерний узел (узлы) левого узла левого узла и т. Д. Корневого узла).Возможным исправлением будет проверка на 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
        }
    }
}

Этот код предполагает, что у вас нетлюбое предчувствие, что это за график.В противном случае вы также можете проверить, больше или меньше искомое число по сравнению со значением текущего узла, и выполнить поиск в левой или правой части соответственно.