Python数据结构二叉树之递归版二叉树遍历，查找

class Btnode:
    def __init__(self,data,lchild=None,rchild=None):
        self.data=data
        self.lchild=lchild
        self.rchild=rchild
   
class Bitree:
    
    def __init__(self,root=None):
        self.root=root
    
    #递归的思想生成二叉树
    @staticmethod
    def construct_tree(pre_order,in_order): #传递前序序列，与中序序列
        if len(pre_order)==0:
            return None
        root_data=pre_order[0]  
        i=in_order.index(root_data)
        lchild=Bitree.construct_tree(pre_order[1:i+1],in_order[0:i])
        rchild=Bitree.construct_tree(pre_order[1+i:],in_order[1+i:])
        
        return Btnode(root_data,lchild,rchild)
    #前序遍历
    @staticmethod
    def pre_order(root):
        if root is not None:
            print(root.data)                #根节点放在开头
            Bitree.pre_order(root.lchild)
            Bitree.pre_order(root.rchild)
            
    #中序遍历
    @staticmethod
    def in_order(root):
        if root is not None:
            Bitree.pre_order(root.rchild)
            print(root.data)                #根节点放在中间
            Bitree.pre_order(root.lchild)
    #调用统计方法
    def node_count(self):
        return self._node_count(self.root)
    #统计节点个数
    def _node_count(self,t):
        if t is None:
            return 0
        else:
            return 1 +self._node_count(t.lchild)+self._node_count(t.rchild)
    #调用查找节点方法
    def find_node(self,t,x):#在二叉树中查找x节点,如果找到就返回该节点，否则返回None 
        if self._find_node(t, x):
         return self._find_node(t, x)
        else:
            print(None)
        
    
     #查找节点方法    
    def _find_node(self,t,x):
        if t is not None:
            if t.data==x:
                return t.data
            elif self._find_node(t.rchild, x)==x:   #在右节点查找
                return self._find_node(t.rchild, x)
            elif self._find_node(t.lchild, x)==x:   #在左节点查找
                return self._find_node(t.lchild, x)
            
            

             
        
        
       

if __name__ == '__main__':
    pre_order='ABHFDECKG'
    in_order='HBDFAEKCG'
    my_tree=Bitree()
    my_tree.root=Bitree.construct_tree(pre_order,in_order)
    # my_tree.in_order(my_tree.root)
    my_tree.find_node(my_tree.root,'S')

本代码为上课过程中老师与作者自己写的代码