树的存储和遍历——python实现前，中，后序遍历

# 该方式表明只有存在左子树才可能有右子树，而右子树不会单独存在
class TreeNode:  # 定义孩子节点
    def __init__(self, val):
        # 存储某个节点在表头数组的下标
        self.child = val
        # 指向该头节点的下一个孩子
        self.next = None


class HeadNode:  # 定义表头结点
    def __init__(self, val):
        # 数据域：相当于该节点代表的值
        self.data = val
        # 指针域指向该节点第一个孩子节点
        self.firstchild = None  # 将其指向TreeNode


# 先初始化多个表头结点，0也代表了初始化每个节点的data为0
headNode = [HeadNode(0) for i in range(100)]


def add(a, b):  # 我们使b作为a的孩子节点，所以要先创建b
    tree_node = TreeNode(b)  # 该孩子节点的child编号为b
    if headNode[a].firstchild != None:  # 表示a节点存在左孩子节点
        headNode[a].firstchild.next = tree_node
    else:
        headNode[a].firstchild = tree_node  # 否则将b节点置为右孩子节点


# 后序遍历
def dfs(x):
    x = int(x)
    temp_treeNode = headNode[x].firstchild  # 临时节点，指向以n为根的子树的左子树
    if temp_treeNode != None:  # 说明存在左子树
        dfs(temp_treeNode.child)
        temp_treeNode = temp_treeNode.next  # 再去看右子树
        if temp_treeNode != None:  # 说明有右子树
            dfs(temp_treeNode.child)
        print(headNode[x].data, end=' ')#(根)
    else:
        print(headNode[x].data, end=' ')

# 前序遍历
# def dfs(x):
#     x = int(x)
#     temp_treeNode = headNode[x].firstchild  # 临时节点，指向以n为根的子树的左子树
#     print(headNode[x].data, end=' ')
#     if temp_treeNode != None:  # 说明存在左子树
#         dfs(temp_treeNode.child)
#         temp_treeNode = temp_treeNode.next  # 再去看右子树
#         if temp_treeNode != None:  # 说明有右子树
#             dfs(temp_treeNode.child)

# 中序遍历
# def dfs(x):
#     temp_treeNode = headNode[x].firstchild  # 临时节点，指向x为根的节点的左子树
#     if temp_treeNode != None:  # 存在左子树时
#         dfs(temp_treeNode.child)  # 参数为左子树节点编号
#         print(headNode[x].data, end=' ')  # (根)
#         temp_treeNode = temp_treeNode.next
#         if temp_treeNode != None:  # 存在右子树时
#             dfs(temp_treeNode.child)
#     else:
#         print(headNode[x].data, end=' ')


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    data = sys.stdin.readline().split()
    for i in range(n):
        headNode[i + 1].data = data[i]  # 重新给每个节点的data赋值
    for i in range(n - 1):
        a, b = map(int, sys.stdin.readline().split())
        add(a, b)  # 将a,b节点连接
    root = int(sys.stdin.readline())
    dfs(root)