题目:给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的
下一个节点?树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。在图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= dataself.right = rightself.left = leftself.parent = parentdef inOrder1(BinaryTreeNode):if BinaryTreeNode ==None:returnstack=[]p = BinaryTreeNodewhile p!=None or stack:while p!=None:stack.append(p)p = p.leftif stack:s = stack.pop()print(s.data, end=' ')p = s.rightprint()def GetNext(BinaryTreeNode):if BinaryTreeNode == None:returncur = BinaryTreeNodeif BinaryTreeNode.right:cur = BinaryTreeNode.rightwhile cur.left:cur = cur.leftreturn curelif cur ==cur.parent.left:return BinaryTreeNode.parentelse:while cur.parent.parent and cur.parent == cur.parent.parent.right:cur =cur.parentif not cur.parent.parent:returnreturn 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 = rootn2.parent = rootn3.parent = n1n4.parent = n1n5.parent = n2n6.parent = n2n9.parent = n4n10.parent = n4inOrder1(root)x = GetNext(n6)print(x)