Python实现二叉树的建立与遍历

1. 创建（二叉）树节点类

   class Node:
       def __init__(self,data,l=None,r=None):
           self.val = data
           self.left = l
           self.right = r

2. 创建（二叉）树

   class Tree:
       def __init__(self):
           self.root = None
       def add_node(self,item):
           node = Node(item)#实例化节点
           if self.root is None:
               self.root = node
               return
           queue = [self.root]#队列存放的是待操作节点一个个Node object
           while queue:
               cur_node = queue.pop(0)#取出队头作为当前操作节点
               if cur_node.left is None:
                   cur_node.left = node
                   return
               else:
                   queue.append(cur_node.left)
               if cur_node.right is None:
                   cur_node.right = node
                   return
               else:
                   queue.append(cur_node.right)
       #def 遍历函数...(如下)

3. （二叉）树的遍历

   (1). 广度遍历（Breadth traversal）即层次遍历（Sequence traversal）

       def Breadth_travel(self):
           if self.root == None:
               return
           queue =[self.root]
           while queue:
               cur_node = queue.pop(0)
               print(cur_node.val,end=' ')
               if cur_node.left:
                   queue.append(cur_node.left)
               if cur_node.right:
                   queue.append(cur_node.right)

   (2). 深度遍历（Depth traversal）

   • 先序遍历(preorder traversal)

         def preorder(self,node):
             if node is None:
                 return
             print(node.val,end=' ')
             self.preorder(node.left)
             self.preorder(node.right)

   • 中序遍历(inorder traversal)

         def inorder(self,node):
             if node is None:
                 return
             self.inorder(node.left)
             print(node.val,end=' ')
             self.inorder(node.right)

   • 后序遍历(postorder traserval)

         def postorder(self,node):
             if node is None:
                 return
             self.inorder(node.left)
             self.inorder(node.right)
             print(node.val,end=' ')

4. 应用实例：[判断对称二叉树]

   说明：给定一个二叉树，检查他是否是镜像对称的。

   example：

   源代码：(将下列源码加入到Tree类)

   def isSymmetric(self, node) -> bool:
       if node is None:
           return True
       def dfs(left,right):
           if left ==None and right ==None:#判空操作
               return 1
           if not (left and right):#如两边有一个为空（第一个if已经判断了同时为空）
               return 0
           if left.val!=right.val:#两边不为空，则判断两边的值
               return 0
           return dfs(left.left,right.right) and dfs(left.right,right.left)
           # 用递归函数，比较左节点，右节点
       return dfs(self.root.left,self.root.right)

主程序：

if __name__ == '__main__':
    tree = Tree()
    data = [1, 2, 2, 3, 4, 4, 3]
    for i in data:
        tree.add_node(i)
    #tree.preorder(tree.root)
    #tree.inorder(tree.root)
    #tree.postorder(tree.root)
    tree.Breadth_travel()
    print()
    print(tree.isSymmetric(tree.root))