树。树的种类：
树的顺序存储，将数据结构存储在固定的数组中，虽然在遍历上有一定的优势，但所占空间较大，非主流二叉树。通常以链式储存。
树的常见应用场景。
xml, html，解析器。路由协议就是使用了树的算法mysql数据库索引文件系统的目录结构很多经典的AI算法都是树搜索。树的实现。
class Node: def __init__(self,item): self.val = item self.left = None self.right = None class Tree: def __init__(self): self.root = None def add(self,item): node = Node(item) if not self.root: return queue = [self.root] while queue: cur_node = queue.pop(0) if not cur_node.left: cur_node.left = node return else: queue.append(cur_node.left) if not cur_node.right: cur_node.right = node return else: queue.append(cur_node.right) def bfs(self): if not self.root: return [] queue = [self.root] while queue: cur_node =queue.pop(0) print(cur_node.val) if cur_node.left: queue.append(cur_node.left) if cur_node.right: queue.append(cur_node.right) 前序(根左右)遍历。 #Method1 recursion def preorder(root): if not root: return [] return [root.val]+preorder(root.left)+preorder(root.right) #Method2 iteration def preorder(root): if not root: return [] stack,res = [root],[] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res 中序(左根右)遍历。 #Method1 recursion def inorder(root): if not root: return [] return inorder(root.left)+[root.val]+inorder(root.right) #Method2 iteration(medium) def inorder(root): if not root: return [] stack,res,node =[],[],root while stack or node: while node: stack.append(node) node = node.left node = stack.pop() res.append(node.val) node = node.right return res 后序(左右根)遍历。 #Method1 recursion def postorder(root): if not root: return [] return postorder(root.left)+postorder(root.right)+[root.val] #Method2 iteration(medium) def postorder(root): if not root: return [] stack,res,node =[],[],root while stack or node: while node: stack.append(node) node = node.left if node.left else node.right node = stack.pop() res.append(node.val) if stack and stack[-1].left == node: node = stack[-1].right else: node = None return res 两种排序（必须要知道中序）可以确定一棵树。遍历反推树较难。前序中序推后序，剑指OFFER07: def buildtree(preorder,inorder): if not preorder or not inorder: return None root = Node(preorder[0]) ind = inorder.index(preorder[0]) root.left = buildtree(preorder[1:ind+1],inorder[:ind]) root.right = buildtree(preorder[ind+1:],inorder[ind+1:]) return root