树（tree）是一种非线性的数据结构，是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合，它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合。

1.简介

树的结构十分直观，而树的很多概念定义都有一个相同的特点：递归，也就是说，一棵树要满足某种性质，往往要求每个节点都必须满足。
例如，在定义一棵二叉搜索树时，每个节点也都必须是一棵二叉搜索树。

2.创建二叉树

2.1.python模拟栈的实现

class Empty(Exception):passclass ParamsError(Exception):passclass Stack(object):"""模拟栈"""def __init__(self):self._data = []def __len__(self):return len(self._data)def is_empty(self):"""Return True if the stack is empty."""return len(self._data) == 0def pop(self):"""Remove and return the element from the top of the stack."""if self.is_empty():raise Empty('Stack is empty.')return self._data.pop()def push(self, e):"""Add an element e to the top of the stack."""self._data.append(e)def top(self):"""Return the element at the top of the stack."""if self.is_empty():raise Empty('Stack is empty.')return self._data[-1]

2.2.python模拟队列的实现

class Queue(object):"""模拟队列"""def __init__(self):self._data = []self._size = 0def __len__(self):return self._sizedef is_empty(self):return self._size == 0def first(self):if self.is_empty():raise Empty('Queue is empty.')return self._data[0]def dequeue(self):if self.is_empty():raise Empty('Queue is empty.')self._size -= 1return self._data.pop(0)def enqueue(self, e):self._data.append(e)self._size += 1

2.3.python模拟树的实现

class Node(object):"""节点"""def __init__(self, data=None, left=None, right=None):self.data = dataself.left = leftself.right = rightclass Tree(object):"""创建树"""default_chars = [chr(c) for c in range(65, 91)]def __init__(self, seq=None, depth=4, is_complete=True):"""初始化:param seq: 二叉树元素序列:param depth: 深度:param is_complete: 是否为完全二叉树"""seq = self.default_chars if seq is None else seqif len(seq) < depth and is_complete:raise ParamsError('seq is too small or depth is too large!')self.depth = depthself._root = Noneself.chars = seq[:pow(2, self.depth) - 1] if is_complete else seqdef create(self):"""执行创建"""# tree = self._recursive_create_node(self.chars)# 生成完全二叉树for (i, j) in enumerate(self.chars):node = Node(j)if i == 0:self._root = nodeelse:self._insert_node(node)return self._rootdef _recursive_create_node(self, seq):"""递归创建节点"""n = len(seq)if n == 0:return Nonei = n // 2return Node(seq[i], self._recursive_create_node(seq[:i]), self._recursive_create_node(seq[i + 1:]))def _insert_node(self, node):# 建立一个完全二叉树lst = []def _insert(tree_node, p, node):if tree_node.left is None:tree_node.left = nodelst.append(tree_node.left)returnelif tree_node.right is None:tree_node.right = nodelst.append(tree_node.right)returnelse:lst.append(tree_node.left)lst.append(tree_node.right)if p > (len(lst) - 2):returnelse:_insert(lst[p + 1], p + 1, node)lst.append(self._root)_insert(self._root, 0, node)

3.二叉树遍历

二叉树的遍历有：深度遍历和广度遍历，深度遍历分为：前序、中序以及后序三种遍历方法，广度遍历即层次遍历。

• 前序遍历（Preorder Traversal）：先访问根节点，然后访问左子树，最后访问右子树。（根 —> 左 —> 右）
• 中序遍历（Inorder Traversal）：先访问左子树，然后访问根节点，最后访问右子树。（左 —> 根 —> 右）
• 后序遍历（Postorder Traversal）：先访问左子树，然后访问右子树，最后访问根节点。（左 —> 右 —> 根）
• 广度遍历（Breadth traversal）：即层次遍历，每层从左到右遍历。

其中深度遍历可以利用 栈 的结构来实现，广度遍历可以利用 队列 的结构来实现。

3.1.前序遍历

• 栈实现：

import sysclass Tree(object):"""二叉树"""@staticmethoddef pre_traversal(tree):"""深度遍历 - 前序遍历: 栈实现 (根->左->右)"""if tree is None:returndata_list = []stack = Stack()stack.push(tree)  # 根入栈while not stack.is_empty():node = stack.pop()  # 出栈data_list.append(str(node.data))if node.right:stack.push(node.right)  # 右节点入栈if node.left:stack.push(node.left)sys.stdout.write('前序遍历: ' + '->'.join(data_list))

• 递归实现：

def pre_order(tree, lst=[]):"""前序遍历: 根->左->右"""if tree is None:return# print(tree.data, end='->')lst.append(tree.data)self.pre_order(tree.left, lst)self.pre_order(tree.right, lst)return lst

3.2.中序遍历

• 栈实现：

class Tree(object):"""二叉树"""@staticmethoddef in_traversal(tree):"""深度遍历 - 中序遍历: 栈实现 (左->根->右)"""if tree is None:returndata_list = []stack = Stack()node = treewhile node or not stack.is_empty():while node:  # 循环查找左节点stack.push(node)node = node.left# 循环结束，表示左节点为空node = stack.pop()  # 左节点，从下往上data_list.append(str(node.data))node = node.right  # 上一个左节点的右子节点sys.stdout.write('中序遍历: ' + '->'.join(data_list))

• 递归实现：

def mid_order(tree, lst=[]):"""中序遍历: 左->根->右"""if tree is None:returnself.mid_order(tree.left, lst)# print(tree.data, end='->')lst.append(tree.data)self.mid_order(tree.right, lst)return lst

3.3.后序遍历

• 栈实现：

class Tree(object):"""二叉树"""@staticmethoddef post_traversal(tree):"""深度遍历 - 后序遍历: 栈实现 (左->右->根)"""if tree is None:returndata_list = []stack1 = Stack()stack2 = Stack()node = treestack1.push(node)while not stack1.is_empty():  # stack1 存放遍历的逆序，正确顺序放入 stack2 中node = stack1.pop()if node.left:stack1.push(node.left)if node.right:stack1.push(node.right)stack2.push(node)while not stack2.is_empty():data_list.append(str(stack2.pop().data))sys.stdout.write('后序遍历: ' + '->'.join(data_list))

• 递归实现：

def post_order(tree, lst=[]):"""后序遍历: 左->右->根"""if tree is None:returnself.post_order(tree.left, lst)self.post_order(tree.right, lst)# print(tree.data, end='->')lst.append(tree.data)return lst

3.4.广度遍历

class Tree(object):"""二叉树"""@staticmethoddef level_traversal(tree):"""广度遍历: 层次遍历 - 队列实现"""if tree is None:returndata_list = []queue = Queue()node = treequeue.enqueue(node)while not queue.is_empty():node = queue.dequeue()  # 出队data_list.append(str(node.data))if node.left:queue.enqueue(node.left)  # 左节点入队if node.right:queue.enqueue(node.right)sys.stdout.write('广度遍历: ' + '->'.join(data_list))

3.5.测试

def code_test():"""测试"""# tree = Tree(depth=3)# tree = Tree(seq=[i for i in range(1, 10)], depth=3)tree = Tree(seq=[i for i in range(1, 10)], is_complete=False)btree = tree.create()# 深度遍历# 1-前序遍历print(pre_order(btree))  # [1, 2, 4, 8, 9, 5, 3, 6, 7]tree.pre_traversal(btree)  # 前序遍历: 1->2->4->8->9->5->3->6->7print('\n----------------------------------------')# 2-中序遍历print(mid_order(btree))  # [8, 4, 9, 2, 5, 1, 6, 3, 7]tree.in_traversal(btree)  # 中序遍历: 8->4->9->2->5->1->6->3->7print('\n----------------------------------------')# 3-后序遍历print(post_order(btree))  # [8, 9, 4, 5, 2, 6, 7, 3, 1]tree.post_traversal(btree)  # 后序遍历: 8->9->4->5->2->6->7->3->1print('\n----------------------------------------')# 广度遍历tree.level_traversal(btree)  # 广度遍历: 1->2->3->4->5->6->7->8->9print('\n----------------------------------------')if __name__ == '__main__':code_test()

---