4树 二叉树 二叉搜索树 堆

#python
class TreeNode: 
def __init__(self, val): 
self.val = val 
self.left, self.right = None, None
public class TreeNode {
	public int val;
	public TreeNode left, right;
	public TreeNode(int val) {
		this.val = val;
		this.left = null;
		this.right = null; } }

示例代码
前序 中序 后序

示例代码
def preorder(self, root): 
	if root: 
	self.traverse_path.append(root.val) 
	self.preorder(root.left) 
	self.preorder(root.right)
def inorder(self, root):
	if root: 
	self.inorder(root.left) 
	self.traverse_path.append(root.val) 
	self.inorder(root.right)
def postorder(self, root):
	if root: 
	self.postorder(root.left) 
	self.postorder(root.right) 
	self.traverse_path.append(root.val)
二叉搜索树
  1. 左子树上所有结点的值均小于它的根结点的值;
  2. 右子树上所有结点的值均大于它的根结点的值;
  3. 以此类推:左、右子树也分别为二叉查找树。 (这就是 重复性!)
    中序遍历:升序排列
    4树 二叉树 二叉搜索树 堆
堆 heap 优先队列 priority_queue

可以迅速找到一堆数中的最大或者最小值的数据结构
根节点最大的堆叫做大顶堆,根节点最小的堆叫做小顶堆
插入
删除
查找

二叉堆的性质

通过完全二叉树来实现
二叉堆(大顶)性质:
是一棵完全树
树中任意节点的值总>=其子节点的值

细节:
二叉堆一般是通过数组来实现
假设第一个元素在数组中的索引是0,左孩子是2i+1,右孩子是2i+2,父节点是i-1/2
插入:插入到尾部,依次向上调整 logn
删除堆顶:堆尾替换到顶部,以词向下调整整个堆的结构

#DFS
visited = set() # 和树中的DFS最大区别
def dfs(node, visited):
	if node in visited: # terminator
	# already visited 
	return 
	visited.add(node) 
# process current node here. 
...
	for next_node in node.children(): 
		if not next_node in visited: 
			dfs(next_node, visited)
#BFS
def BFS(graph, start, end):
	queue = [] 
	queue.append([start]) 
	visited = set() # 和树中的BFS的最大区别
	while queue: 
		node = queue.pop() 
	visited.add(node)
	process(node) 
	nodes = generate_related_nodes(node) 
	queue.push(nodes)
上一篇:DFS 和 BFS


下一篇:2021-03-09单词搜索