python二叉树的一点实现

浏览数：20 / 时间：2015年06月08日

100

101

102

103

104

105

106

class 
TreeNode:
    parent,leftChild,rightChild,data=None,None,None,0
    def 
__init__(self,data):
        self.parent,self.leftChild,self.rightChild,self.data=None,None,None,data
class 
BinaryTree:
    root=None
    def 
__init__(self,data):
        self.root=TreeNode(data)
    def 
insertValue(self,beginNode,data):
        self.add(beginNode,TreeNode(data))
    def 
add(self,beginNode,inNode):
        if 
beginNode==None:
            raise 
NameError,"beginNode is None"
        else:
            if 
beginNode.data<inNode.data:
                if 
beginNode.rightChild==None:
                    inNode.parent=beginNode
                    beginNode.rightChild=inNode
                else:
                    self.add(beginNode.rightChild,inNode)
            else:
                if 
beginNode.leftChild==None:
                    inNode.parent=beginNode
                    beginNode.leftChild=inNode
                else:
                    self.add(beginNode.leftChild,inNode)
    def 
maxValue(self,beginNode):
        if 
beginNode.rightChild==None:
            return 
beginNode.data
        else:
            return 
self.maxValue(self,beginNode.rightChild)
    def 
maxDepth(self,beginNode):
        if 
beginNode==None:
            return 
0
        else:
            return 
max(self.maxDepth(beginNode.rightChild),self.maxDepth(beginNode.leftChild))+1
    def 
judgeDirction(self,beginNode,searchedNode):
        if 
searchedNode==beginNode:
            Direction="OnlySelf"
        elif 
searchedNode==beginNode.leftChild:
            Direction="Left"
        elif 
searchedNode==beginNode.rightChild:
            Direction="Right"
        else: Direction="Up"
        return 
Direction
    def 
nextNode(self,beginNode):
         
        returnNode,Direction=self.nextNodeByDirection(beginNode,"OnlySelf")
        if 
Direction=="AllOver":
            return 
None
        """
         else:
            returnNode,Direction=self.nextNodeByDirection(searchedNode,"Left")
        Direction=self.judgeDirction(beginNode,returnNode)
        """
        return 
returnNode
    def 
nextNodeByDirection(self,beginNode,searchedDirection="OnlySelf"):
        """
        beginNode：求beginNode的下一个节点
        searchedDirection:表示已经搜索过的方向：OnlySelf表示什么也没有搜索，Left,表示已经搜索了左孩子节点，Right表示已经
                          搜索右子树
        思路：
        1.如果什么都没有搜索，则返回左孩子，如果左孩子为空，进行步骤2
        2.搜索右孩子点，返回右孩子，如果右孩子为空，进入步骤3
        3.获取节点A的父节点parent,如果节点A是父节点parent的左孩子的话，设置已经搜索了"Left",设置parent节点为当前节点
        此时就可以进入步骤2，如果节点A是父节点parent的右孩子的话，设置已搜索方法为"Right",设置parent节点为当前节点，
        再进入节点3
         
        什么时候可以退出呢？当返回方向为"AllOver"且返回的节点为None时，就可以退出了
        """
        if 
searchedDirection=="OnlySelf":
            if  
not beginNode.leftChild:
                return 
self.nextNodeByDirection(beginNode,"Left")
            else:
                return 
beginNode.leftChild,searchedDirection
        elif 
searchedDirection=="Left":
            rightChildNode=beginNode.rightChild
            if 
not rightChildNode:
                return 
self.nextNodeByDirection(beginNode,"Right")
            else:
                return 
rightChildNode,searchedDirection
        else:
            parentNode=beginNode.parent
            if 
not parentNode:
                return 
None,searchedDirection
            else:
                if 
parentNode.leftChild==beginNode:
                    return 
self.nextNodeByDirection(parentNode,"Left")
                else:
                    return 
self.nextNodeByDirection(parentNode,"Right")
    def 
printTree(self,beginNode):
        searchNode=None
        print 
beginNode.data,
        searchNode=beginNode
        while 
True:
            searchNode=self.nextNode(searchNode)
            if 
not  searchNode:
                break
            print 
searchNode.data,
if 
__name__==‘__main__‘:
    ds=[5,6,4,10,8,7,2]
    BTree=BinaryTree(ds[0])
 
    for 
i in 
ds[1:]:
        BTree.insertValue(BTree.root,i)
    BTree.printTree(BTree.root)