前言
本文主要介绍树形结构——二叉树的相关操作，创建二叉树、遍历二叉树等等
一、创建二叉树
二叉树有两种表示形式，一种是以列表的形式存储，所有元素的下标从1开始依次向后排列，编号为i的元素的左孩子编号为2i，右孩子编号为2i+1。
二叉树的每个结点：
class TreeNode: def __init__(self,val): self.val=val (1) self.left=None (2) self.right=None (3)
（1）该结点的值
（2）该结点的左子树
（3）该结点的右子树
创建一个二叉树：
Input=[0] (1) tree=[] (2) Input=Input+input().split() for item in Input: t=TreeNode(item) tree.append(t) for i in range(1,len(tree)): if tree[i].val=='null': (3) continue if 2*i<len(Input) and tree[2*i].val!='null': (4) tree[i].left=tree[2*i] if 2*i+1<len(Input) and tree[2*i+1].val!='null': (5) tree[i].right=tree[2*i+1]
（1）存储输入的值
（2）存储结点
（3）若树结点为null，跳过
（4）找到该结点的左子树
（5）找到该节点的右子树
二、遍历二叉树
遍历二叉树有三种方法：先序遍历、中序遍历、后序遍历
先序遍历
def preorder(i): if tree[i].val=='null': return print(tree[i].val) preorder(2*i) preorder(2*i+1)
中序遍历
def inorder(i): if tree[i].val=='null': return inorder(2*i) print(tree[i].val) inorder(2*i+1)
后序遍历
1. def postorder(i): 2. if tree[i].val=='null': 3. return 4. postorder(2*i) 5. postorder(2*i+1) 6. print(tree[i].val)
三、问题引入
1. 已知一棵有n个元素的二叉树存储在一个列表中。输出先序遍历、中序遍历和后序遍历这颗二叉树的结果
（注：列表中每个元素的下标即为它在二叉树中的编号，下标从1开始。如果按编号顺序排列的元素之间有为空的位置，则用0代替，值为0的元素位置不算入总数n中）
输入格式：第一行输入二叉树中元素的个数n，第二行按二叉树中的编号顺序输入n+x个元素，x为0的个数；每个元素之间用空格隔开
输出格式：输出共三行；第一行输出先序遍历的结果，第二行输出中序遍历的结果，第三行输出后序遍历的结果，每行的各元素之间用空格隔开
样例输入：
6
2 9 3 1 0 7 8
样例输出：
2 9 1 3 7 8
1 9 2 7 3 8
1 9 7 8 3 2
程序设计
class TreeNode(): def __init__(self,val): self.val=val self.left=None self.right=None def preorder(i): if i>=len(tree): return if tree[i].val==0: return print(tree[i].val,end=' ') preorder(2*i) preorder(2*i+1) def inorder(i): if i>=len(tree): return if tree[i].val==0: return inorder(2*i) print(tree[i].val,end=' ') inorder(2*i+1) def postorder(i): if i>=len(tree): return if tree[i].val==0: return postorder(2*i) postorder(2*i+1) print(tree[i].val,end=' ') n=int(input()) lst=list(map(int,input().split(' '))) tree=[] tree.append(TreeNode(0)) for i in lst: t=TreeNode(i) tree.append(t) for i in range(1,len(tree)): if tree[i].val==0: continue if 2*i<=len(lst) and tree[2*i].val!=0: tree[i].left=tree[2*i] if 2*i+1<len(lst) and tree[2*i+1].val!=0: tree[i].right=tree[2*i+1] preorder(1) print() inorder(1) print() postorder(1)
程序分析
这是一个构建二叉树并进行前序、中序、后序遍历的程序。
主体部分：
首先输入节点个数n和按层序遍历的节点值列表lst，并创建一个空的节点列表tree作为树的基础。之后循环遍历lst，为每一个节点创建一个TreeNode对象，并将其添加到树的节点列表中。接着，再次循环遍历tree节点列表，为每个节点关联左右子节点。具体来说，检查2i和2i+1是否在节点列表范围内，以及它们的值是否不为0（因为我们使用0值表示空节点），如果是，则将它们赋值给当前节点的左右子节点。
之后是三个遍历函数preorder、inorder和postorder。这些函数参数是当前节点的索引，从1开始，因为根节点在节点列表中是第一个元素。如果索引超出了节点列表的范围或者当前节点的值为0，则直接返回。否则，按照前序、中序或后序遍历的顺序，分别先递归调用左子节点，然后递归调用右子节点，并打印出当前节点的值。
程序分析：
这个程序比较简单，主要考察二叉树的构建和遍历。在输入节点值时，需要按层序遍历的顺序输入，因为后面关联左右子节点时是按照2i和2i+1来实现的。在遍历过程中，需要特别注意空节点的处理，使用0值来表示空节点，遇到0值时直接返回即可。此外，需要注意节点索引从1开始。
总结
本文介绍了二叉树的创建方法以及三种遍历方法，先序遍历、中序遍历以及后序遍历
