python实现树（三种遍历算法）

树(Tree)

树是一种分层数据的抽象模型,以分层结构表示数据之间的关系。树结构包含以下几个概念:

• 节点 - 树中的每个元素都叫做节点
• 根节点 - 树的顶部节点
• 父节点 - 一个节点包含的子树的顶部节点
• 子节点 - 一个节点所包含的树中的节点
• 叶节点 - 没有子节点的节点
• 子树 - 由节点和它的后代构成的树
• 节点的度 - 节点包含的子树数量
• 树的度 - 树内节点的最大度数
• 高度 - 根节点到该节点的最长简单路径边的条数

三种遍历算法

• 前序遍历 - 访问顺序为根节点、左子树、右子树
• 中序遍历 - 访问顺序为左子树、根节点、右子树
• 后序遍历 - 访问顺序为左子树、右子树、根节点

Python 实现

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def preorder(root):
    if not root:
        return
    
    print(root.data)
    preorder(root.left)
    preorder(root.right)
    
def inorder(root):
    if not root:
        return
    
    inorder(root.left)
    print(root.data)
    inorder(root.right)

def postorder(root):
    if not root:
        return
    
    postorder(root.left)
    postorder(root.right)
    print(root.data)
    
root = TreeNode('D')
root.left = TreeNode('B')
root.right = TreeNode('E')
root.left.left = TreeNode('A')
root.left.right = TreeNode('C') 

preorder(root)
inorder(root) 
postorder(root)