二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。这里有两个关键词：访问和次序。访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等。它算作是一个抽象操作。
二叉树的遍历次序不同于线性结构，最多也就是从头到尾、循环和双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。
二叉树的遍历方式，主要分为三种：
1. 中序遍历
2. 后序遍历
3. 前序遍历
中序遍历： 先中序访问左子树，然后访问根，最后中序访问右子树。总的来说是左—根—右
1. 先处理左子树，然后处理当前节点，再处理右子树；
2. 对于一颗二叉查找树，所有的信息都是有序排列的，中序遍历可以是信息有序输出，且运行时间为 O（n）；
3. 递归实现中序遍历。
def inorder(self, node):
if node is None:
return []
result = [node.item]
left_item = self.inorder(node.left)
right_item = self.inorder(node.right)
return left_item + result + right_item
后序遍历： 先后序访问左子树，然后后序访问右子树，最后访问根。总的来说是左—右—根
1. 先处理左右子树，然后再处理当前节点，运行时间为 O（n）
2. 递归实现后序遍历
def postorder(self, node):
if node is None:
return []
result = [node.item]
left_item = self.postorder(node.left)
right_item = self.postorder(node.right)
return left_item + right_item + result
前序遍历： 先访问根节点，再先序遍历左子树，然后再先序遍历右子树。总的来说是根—左—右
1. 先处理当前节点，再处理左右子树；
2. 递归实现先序遍历。
def preorder(self, node):
if node is None:
return []
result = [node.item]
left_item = self.preorder(node.left)
right_item = self.preorder(node.right)
return result + left_item + right_item
字典树
字典树，又称单词查找树，Trie 树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
字典树的主要性质：
1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3. 每个节点的所有子节点包含的字符都不相同。
class TrieNode:
def __init__(self):
self.nodes = dict() #构建字典
self.is_leaf = False
def insert(self, word: str): #插入一个字到字典树中
curr = self
for char in word:
if char not in curr.nodes:
curr.nodes[char] = TrieNode()
curr = curr.nodes[char]
curr.is_leaf = True
def insert_many(self, words: [str]): #插入一列表的字到字典树中
for word in words:
self.insert(word)
def search(self, word: str): #在字典树里面查询一个字
curr = self
for char in word:
if char not in curr.nodes:
return False
curr = curr.nodes[char]
return curr.is_leaf
字典树的应用： 用在统计和排序大量字符串，如自动机。字典树能做前缀搜索，在正则匹配，数据压缩，构建索引都可能用到。
堆
堆 (heap) 是一种经过排序的完全二叉树，其中任一非叶子节点的值均不大于（或不小于）其左孩子和右孩子节点的值。堆，又被称为优先队列(priority queue)。尽管名为优先队列，但堆并不是队列。
* 最大堆 根结点的键值是所有堆结点键值中最大者。
* 最小堆 根结点的键值是所有堆结点键值中最小者
