树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
图示：
将数据结构存储在固定的数组中，虽然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。
由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为2。
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
1 class Node: 2 """树的节点类""" 3 def __init__(self, item): 4 self.elem = item 5 self.lchild = None 6 self.rchild = None 7 8 9 class Tree: 10 """二叉树""" 11 12 def __init__(self, root=None): 13 """初始化根节点""" 14 self.root = root 15 16 def add(self, elem): 17 """为树添加节点""" 18 node = Node(elem) 19 # 如果树是空的，则为根节点赋值 20 if self.root is None: 21 self.root = node 22 else: 23 queue = [] 24 queue.append(self.root) 25 # 对已有节点进行层次遍历 26 while queue: 27 # 弹出队列的第一个元素（先进先出） 28 cur_node = queue.pop(0) 29 if cur_node.lchild is None: 30 cur_node.lchild = node 31 return 32 elif cur_node.rchild is None: 33 cur_node.rchild = node 34 return 35 # 如果左右子树都不为空，加入队列继续判断 36 else: 37 queue.append(cur_node.lchild) 38 queue.append(cur_node.rchild)
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有节点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。
树的两种重要的遍历模式是深度优先遍历和广度优先遍历。深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
从树的root开始，从上到下、从左到右地遍历整个树的节点。
对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。
在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树。
在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树。
在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根节点。
1 class Node: 2 """树的节点类""" 3 def __init__(self, item): 4 self.elem = item 5 self.lchild = None 6 self.rchild = None 7 8 9 class Tree: 10 """二叉树""" 11 12 def __init__(self, root=None): 13 """初始化根节点""" 14 self.root = root 15 16 def add(self, elem): 17 """为树添加节点""" 18 node = Node(elem) 19 # 如果树是空的，则为根节点赋值 20 if self.root is None: 21 self.root = node 22 else: 23 queue = [] 24 queue.append(self.root) 25 # 对已有节点进行层次遍历 26 while queue: 27 # 弹出队列的第一个元素（先进先出） 28 cur_node = queue.pop(0) 29 if cur_node.lchild is None: 30 cur_node.lchild = node 31 return 32 elif cur_node.rchild is None: 33 cur_node.rchild = node 34 return 35 # 如果左右子树都不为空，加入队列继续判断 36 else: 37 queue.append(cur_node.lchild) 38 queue.append(cur_node.rchild) 39 40 def breadth_travel(self): 41 """广度遍历""" 42 if self.root is None: 43 return 44 queue = [self.root] 45 while queue: 46 cur_node = queue.pop(0) 47 print(cur_node.elem, end=" ") 48 if cur_node.lchild is not None: 49 queue.append(cur_node.lchild) 50 if cur_node.rchild is not None: 51 queue.append(cur_node.rchild) 52 53 def preorder(self, node): 54 """递归实现先序遍历""" 55 if node is None: 56 return 57 print(node.elem, end=" ") 58 self.preorder(node.lchild) 59 self.preorder(node.rchild) 60 61 def midorder(self, node): 62 """递归实现中序遍历""" 63 if node is None: 64 return 65 self.midorder(node.lchild) 66 print(node.elem, end=" ") 67 self.midorder(node.rchild) 68 69 def postorder(self, node): 70 """递归实现后序遍历""" 71 if node is None: 72 return 73 self.postorder(node.lchild) 74 self.postorder(node.rchild) 75 print(node.elem, end=" ") 76 77 78 if __name__ == "__main__": 79 tree = Tree() 80 tree.add(0) 81 tree.add(1) 82 tree.add(2) 83 tree.add(3) 84 tree.add(4) 85 tree.add(5) 86 tree.add(6) 87 tree.add(7) 88 tree.add(8) 89 tree.add(9) 90 print("广度遍历：", end="") 91 tree.breadth_travel() 92 print() 93 print("先序遍历：", end="") 94 tree.preorder(tree.root) 95 print() 96 print("中序遍历：", end="") 97 tree.midorder(tree.root) 98 print() 99 print("后序遍历：", end="") 100 tree.postorder(tree.root)
运行结果：
广度遍历：0 1 2 3 4 5 6 7 8 9 先序遍历：0 1 3 7 8 4 9 2 5 6 中序遍历：7 3 8 1 9 4 0 5 2 6 后序遍历：7 8 3 9 4 1 5 6 2 0
答：先序与中序，或中序与后续。
原文：https://www.cnblogs.com/juno3550/p/12687672.html