Entry 1940

#!/usr/bin/env python
#coding=utf-8

#节点类
class Node():
    def __init__(self,value,father=0,lchild=0,rchild=0,visited=0):
        self.value = value
        self.father = father
        self.lchild = lchild
        self.rchild = rchild
        self.visited = visited
    def printValue(self):
        print self.value
    def isVisited(self):
        print self.visited

#二叉树先序遍历       
def LVisit(node):
    if node.lchild != 0:
        LVisit(node.lchild)
    node.printValue()
    if node.rchild != 0:
        LVisit(node.rchild)

#寻找同级节点
def FindSameLevelNode(node):
    #node.printValue()
    #先标记成已访问
    node.visited = 1
   
    #最简单的，先看看有没有同一父节点的兄弟
    if node.father != 0:
        print node.father.value
       
        #左边有没见过的兄弟吗？
        if node.father.lchild != 0 and node.father.lchild.value != node.value and node.father.lchild.visited != 1:
            print node.father.lchild.value
            return node.father.lchild
       
        #右边有没见过的兄弟吗？
        elif node.father.rchild != 0 and node.father.rchild.value != node.value and node.father.rchild.visited != 1:
            print node.father.rchild.value
            return node.father.rchild
       
        #没有兄弟就只能找叔叔了
        uperNode = node.father
       
        while True:
            #递归找哥们，拜叔为父
            anotherFather = FindSameLevelNode(uperNode)
           
            #左边有没见过的堂兄吗？
            if anotherFather.lchild != 0 and anotherFather.lchild.visited != 1:
                print anotherFather.lchild.value
                return anotherFather.lchild
           
            #右边有没见过的堂兄吗？
            elif anotherFather.rchild != 0 and anotherFather.rchild.visited != 1:
                print anotherFather.rchild.value
                return anotherFather.rchild
           
            #没有就找别的叔叔了
            else:
                uperNode = anotherFather
       
               

#主函数
def main():
    """
    树图
              1
             / \
            2   6
           / \   \
          3   5   7
         /       /
        4       8
    """
   
    #上面树图的实现
    n4 = Node(4)
    n3 = Node(3,lchild=n4)
    n4.father = n3
    n5 = Node(5)
    n2 = Node(2,lchild=n3,rchild=n5)
    n3.father = n2
    n5.father = n2
    n8 = Node(8)
    n7 = Node(7,lchild=n8)
    n8.father = n7
    n6 = Node(6,rchild=n7)
    n7.father = n6
    n1 = Node(1,lchild=n2,rchild=n6)
    n6.father = n1
    n2.father = n1
   
    #打印结果
    print "The same level node is Node %d." % FindSameLevelNode(n4).value
    print "And things ubove is the finding path."
   

if __name__ == '__main__':
    main()