学步园

Problem 4.5: Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

To address this problem, the most important thing is making the cases clear. The three cases we should consider about are:
1) The given node has right child.
2) The given node has no right child. 
    a. The given node is the left child of its parent.
    b. The given node is the right child of its parent.

The implementation is given below:

from queue import *
class btree_node:
    def __init__(self, value = None, parent = None):
        self.value = value
        self.parent = parent
        self.left = None
        self.right = None
def find_next_node(node):
    if node == None:
        return None
    # If the given node has right child
    if node.right != None:
        # Find the next node in right branch
        next = node.right
        while next.left != None:
            next = next.left
        return next
    # If the given node has no right child
    # and it is left child of its parent
    elif node == node.parent.left:
        return node.parent
    # If the given node has no right child
    # and it is right child of its parent
    elif node == node.parent.right:
        # The given node is the greatest in the sub-tree,
        # whose root is the given node's parent.
        # The sub-tree above is left sub-tree of a node,
        # and the node is next node of given node
        next = node.parent
        while next != None:
            if (next.parent == None) or (next == next.parent.left):
                break
            else:
                next = next.parent
        if next == None:
            return None
        else:
            return next.parent
# Test case
if __name__ == "__main__":
    # Construct the binary search tree
    array = [btree_node(i) for i in range(0, 15)]
    root = construct_min_btree(array, 0, 14)
    # Print the binary tree in level-order
    q = queue()
    q.enqueue(root)
    current_level = 0
    num_in_current_level = 2**current_level
    while not q.is_empty():
        n = q.dequeue()
        print n.value,
        if n.left != None:
            q.enqueue(n.left)
        if n.right != None:
            q.enqueue(n.right)
        num_in_current_level -= 1
        # End of a level
        if num_in_current_level == 0:
            current_level += 1
            num_in_current_level = 2**current_level
            print "\n"
    # Test the implementation
    print find_next_node(array[0]).value
# Utility function to construct binary search tree
def construct_min_btree(array, start, end):
    if start > end:
        return None
    mid = (start + end)/2
    array[mid].left = construct_min_btree(array, start, mid - 1)
    array[mid].right = construct_min_btree(array, mid + 1, end)
    if array[mid].left != None:
        array[mid].left.parent = array[mid]
    if array[mid].right != None:
        array[mid].right.parent = array[mid]
    return array[mid]