1.树和二叉树

二叉树的分类:满二叉树,完全二叉树

二叉树物理存储结构:链式存储结构,数组(按照广度优先层序遍历进行存储),已知父节点,左孩子节点2*parent+1,右孩子节点2*parent+2

二叉树的应用:二叉查找树,二叉排序树

2.二叉树的遍历

2.0 基本定义

深度优先:前序遍历,中序遍历,后序遍历

广度优先:层序遍历

2.1创建二叉树

class TreeNode:def __init__(self, data):self.data = dataself.left = Noneself.right = Nonedef create_binary_tree(input_list=[]):"""构建二叉树:param input_list: 输入数列"""if input_list is None or len(input_list) == 0:return Nonedata = input_list.pop(0)if data is None:return Nonenode = TreeNode(data)node.left = create_binary_tree(input_list)node.right = create_binary_tree(input_list)return node

2.2先序遍历

1.递归

def pre_order_traversal(node):"""前序遍历:param node: 二叉树节点"""if node is None:returnprint(node.data)pre_order_traversal(node.left)pre_order_traversal(node.right)return node

2.栈

def pre_order_traversal_with_stack(root):if not root:return []stack, res = [], []while root or stack:while root:res.append(root.data)stack.append(root)root = root.leftroot = stack.pop()root = root.rightreturn res

letcode先序遍历栈

2.3中序遍历

1.递归

def post_order_traversal(node):"""后序遍历:param node: 二叉树节点"""if node is None:returnpost_order_traversal(node.left)post_order_traversal(node.right)print(node.data)return node

2.栈

def in_order_traversal_with_stack(root):if not root:return []stack, res = [], []while root or stack:while root:# 左节点stack.append(root)root = root.left# 没有左节点root = stack.pop()res.append(root.data)root = root.rightreturn res

letcode中序遍历栈

2.4后续遍历

1.递归

def post_order_traversal(node):"""后序遍历:param node: 二叉树节点"""if node is None:returnpost_order_traversal(node.left)post_order_traversal(node.right)print(node.data)return node

2.栈

def post_order_traversal_with_stack(root):if not root:return []stack, res = [], []prev = Nonewhile root or stack:while root:stack.append(root)root = root.leftroot = stack.pop()if not root.right or root.right == prev:# 情况1:右节点不存在存在,# 情况2:右节点存在且等于prevres.append(root.data)prev = rootroot = Noneelse:# 右节点存在,且不等于prevstack.append(root)root = root.rightreturn res

letcode后续遍历栈

if __name__ == '__main__':my_input_list = [3, 9, None, None, 4, 5, None, None, 7, None, None]root1 = create_binary_tree(my_input_list)print("前序遍历：")# print("result", [3, 9, 4, 5, 7])print("current", pre_order_traversal_with_stack(root1))# print("中序遍历：")# print("result", [9, 7, 5, 4, 3])print("current", in_order_traversal_with_stack(root1))# print("后序遍历：")# print("result", [9, 5, 7, 4, 3])print("current", post_order_traversal_with_stack(root1))

2.5补充

已知一颗二叉树,如果先序遍历的节点顺序是:ADCEFGHB,中序遍历是:CDFEGHAB,则后续遍历序列的结果为 CFHGEDBA

参考

3.二叉堆

3.1基本定义

二叉堆本质上是一种完全二叉树,它分为两种类型:最大堆和最小堆

二叉堆的存储方式:顺序存储在数组中,已知父节点其左节点为2×parent+1,右节点2×parent+2。

3.2二叉堆的自我调整

插入节点

def up_adjust(array=[]):"""二叉堆的尾节点上浮操作:求出最小的元素:param array: 原数组"""child_index = len(array) - 1parent_index = (child_index - 1) // 2# temp保存插入的叶子节点值，用于最后的赋值temp = array[child_index]while child_index > 0 and temp < array[parent_index]:# 无需真正交换，单向赋值即可array[child_index] = array[parent_index]child_index = parent_indexparent_index = (parent_index - 1) // 2array[child_index] = temp

删除节点

def down_adjust(parent_index, length, array=[]):"""二叉堆的节点下沉操作:param parent_index: 待下沉的节点下标:param length: 堆的长度范围:param array: 原数组"""# temp保存父节点值，用于最后的赋值temp = array[parent_index]child_index = 2 * parent_index + 1while child_index < length:# 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子if child_index + 1 < length and array[child_index + 1] < array[child_index]:child_index += 1# 如果父节点小于任何一个孩子的值，直接跳出if temp <= array[child_index]:break# 无需真正交换，单向赋值即可array[parent_index] = array[child_index]parent_index = child_indexchild_index = 2 * child_index + 1array[parent_index] = temp# 前提:基于最小堆
my_array = list([1, 3, 2, 6, 5, 7, 8, 9, 10, 0])
up_adjust(my_array)
print(my_array)

构建二叉堆

def build_heap(array=[]):"""二叉堆的构建操作:param array: 原数组"""# 从最后一个非叶子节点开始，依次下沉调整for i in range((len(array) - 2) // 2, -1, -1):down_adjust(i, len(array), array)my_array = list([7, 1, 3, 10, 5, 2, 8, 9, 6])
build_heap(my_array)
print(my_array)

​