Python写数据结构:二叉树的创建和遍历

拼搏现实的明天。 2022-05-31 01:48 50阅读 0赞

#!/usr/bin/python3.5
    #_*_coding:utf-8_*_
    
    class Node:
        def __init__(self,value):
            self.data = value
            self.lchild = None
            self.rchild = None
    
    class Tree:
        def __init__(self):
            self.__root = None
            self.__i = 0 #用于方便创建树
    
        def __createTree(self,T,str):
            c = str[self.__i]
            self.__i += 1
            if c == '#':
                T = None
            else:
                T = Node(c)
                T.lchild = self.__createTree(T.lchild,str)
                T.rchild = self.__createTree(T.rchild,str)
            return T
    
        def createTree(self,str):
            root = None
            self.__i = 0
            self.__root = self.__createTree(root,str)
            return self.__root
    
        def clearTree(self,T):
            if T == None:
                return
            temp = T
            self.clearTree(T.lchild)
            self.clearTree(T.rchild)
            del temp
            return None
    
        def treeEmpty(self):
            return self.__root == None
    
        def treeDepth(self,T):
            if T == None:
                return 0
            left = self.treeDepth(T.lchild)
            right = self.treeDepth(T.rchild)
            return left + 1 if left >= right else right + 1
    
        def getRoot(self):
            if self.treeEmpty():
                print('树空')
                return
            else:
                print(self.__root.data)
                return self.__root.data
    
        def postOrderTraverse(self,T = None):
            if T == None:
                print('#')
                return
            self.postOrderTraverse(T.lchild)
            self.postOrderTraverse(T.rchild)
            print(T.data)
    
        def inOrderTraverse(self,T):
            if T == None:
                print('#')
                return
            self.inOrderTraverse(T.lchild)
            print(T.data)
            self.inOrderTraverse(T.rchild)
    
        def preOrderTraverse(self,T):
            if T == None:
                print('#')
                return
            print(T.data)
            self.preOrderTraverse(T.lchild)
            self.preOrderTraverse(T.rchild)
    
    if __name__ == '__main__':
        tree = Tree()
        root = tree.createTree('AB#D##C##')