[数据结构与算法]面试题8:二叉树的下一个节点

题目:给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的
下一个节点?树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。在图2.8中的二叉树的中序遍历序列是{d, b,h,e,i,a, f,c, g}。我们将以这棵树为例来分析如何找出二叉树的下一个节点。

如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最
左子节点。也就是说，从右子节点出发一直沿着指向左子节点的指针，我
们就能找到它的下一个节点。 例如，图28中节点b的下一个节点是小.节
点a的下一个节点是f。
接着我们分析一个节点没有右子树的情形。如果节点是它父节点的左
子节点，那么它的下一个节点就是它的父节点。例如，图2.8中节点d的下
一个节点是b,节点f的下一个节点是C。
如果一个节点既没有右子树，并且它还是它父节点的右子节点，
那么
这种情形就比较复杂。我们可以沿着指向父节点的指针-直向上遍历，直
到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这
个节点的父节点就是我们要找的下一个节点。
为了找到图2.8中节点i的下一个节点，我们沿着指向父节点的指针向
上遍历，先到达节点e。由于节点e是它父节点b的右节点，我们继续向上
遍历到达节点b。节点b是它父节点a的左子节点，因此节点b的父节点a
就是节点i的下一个节点。
找出节点g的下一个节点的步骤类似。我们先沿着指向父节点的指针
到达节点C。由于节点c是它父节点a的右子节点，我们继续向上遍历到
达节点a。由于节点a是树的根节点，它没有父节点，因此节点g没有下
一个节点。

# 面试题8 二叉树的下一个节点
'''
此题的方法就是画图分析，三种情况：
    1.如果一个结点有右子树，则下一个节点就是它右子树的最左节点
    2.如果一个结点无右子树：
        a.当该节点是父节点的左子节点，则下一个节点就是父节点
        b.当该节点是父节点的右子节点，则需要向上遍历，至少找个一个是它父节点的左子节点的节点。
'''
class BinaryTreeNode():
    def __init__(self,data,right=None,left=None,parent=None):
        self.data= data
        self.right = right
        self.left = left
        self.parent = parent

def inOrder1(BinaryTreeNode):
    if BinaryTreeNode ==None:
        return
    stack=[]
    p = BinaryTreeNode
    while p!=None or stack:
        while p!=None:
            stack.append(p)
            p = p.left
        if stack:
            s = stack.pop()
            print(s.data, end=' ')
            p = s.right
    print()
        
def GetNext(BinaryTreeNode):
    if BinaryTreeNode == None:
        return
    cur = BinaryTreeNode
    if BinaryTreeNode.right:
        cur = BinaryTreeNode.right
        while cur.left:
            cur = cur.left
        return cur
    elif cur ==cur.parent.left:
        return BinaryTreeNode.parent
    else:
        while cur.parent.parent and cur.parent == cur.parent.parent.right:
            cur =cur.parent
        if not cur.parent.parent:
            return
        return cur.parent.parent
if __name__ == '__main__':
    n10 = BinaryTreeNode('i')
    n9 = BinaryTreeNode('h')
    n6 = BinaryTreeNode('g')
    n5 = BinaryTreeNode('f')
    n4 = BinaryTreeNode('e', left=n9, right=n10)
    n3 = BinaryTreeNode('d')
    n2 = BinaryTreeNode('c', left=n5, right=n6)
    n1 = BinaryTreeNode('b', left=n3, right=n4)
    root = BinaryTreeNode('a', left=n1, right=n2)
    n1.parent = root
    n2.parent = root
    n3.parent = n1
    n4.parent = n1
    n5.parent = n2
    n6.parent = n2
    n9.parent = n4
    n10.parent = n4
    inOrder1(root)
    x = GetNext(n6)
    print(x)