教你如何使用Python实现二叉树结构及三种遍历

一：代码实现

class TreeNode:
   """节点类"""
   def __init__(self, mid, left=None, right=None):
       self.mid = mid
       self.left = left
       self.right = right

# 树类
class Tree:
   """树类"""
   def __init__(self, root=None):
       self.root = root

def add(self, item):
       # 将要添加的数据封装成一个node结点
       node = TreeNode(item)
       if not self.root:
           self.root = node
           return
       queue = [self.root]
       while queue:
           cur = queue.pop(0)
           if not cur.left:
               cur.left = node
               return
           else:
               queue.append(cur.left)

if not cur.right:
               cur.right = node
               return
           else:
               queue.append(cur.right)

tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)

二：遍历

在上述树类代码基础上加遍历函数，基于递归实现。

先序遍历：

先序遍历结果是：0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

# 先序遍历
   def preorder(self, root, result=[]):
       if not root:
           return
       result.append(root.mid)
       self.preorder(root.left, result)
       self.preorder(root.right, result)
       return result

print("先序遍历")
print(tree.preorder(tree.root))
"""
先序遍历
[0, 1, 3, 4, 2, 5, 6]
"""

中序遍历：

中序遍历结果是：3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

# 中序遍历
   def inorder(self, root, result=[]):
       if not root:
           return result
       self.inorder(root.left, result)
       result.append(root.mid)
       self.inorder(root.right, result)
       return result

print("中序遍历")
print(tree.inorder(tree.root))
"""
中序遍历
3, 1, 4, 0, 5, 2, 6]
"""

后续遍历

后序遍历结果是：3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

# 后序遍历
   def postorder(self, root, result=[]):
       if not root:
           return result
       self.postorder(root.left, result)
       self.postorder(root.right, result)
       result.append(root.mid)

return result

print("后序遍历")
print(tree.postorder(tree.root))
"""
后序遍历
[3, 4, 1, 5, 6, 2, 0]
"""

来源：https://blog.csdn.net/qq_39434183/article/details/117927680