Lecture 25: Advanced Trees

CS61B

Traversals

有level order和 depth first traversal两大类，主要介绍三种depth first traversal: preorder, in order, post order.

注意一下，如何记忆这几种traversal,他们的命名中的in,pre,post指的是root被访问的顺序。比如pre,就是root最先被访问； In，就是root是in between被访问的，而post就是root最后被访问。

preorder

Root > Left > Right

Inorder

Left > Root > Right

Postorder

Left > Right > Root

Tricks and helpful resoucers:

TRICK for Preorder,Inorder,Postorder with Example (Imp)

Binary tree traversal: Preorder, Inorder, Postorder

这些traversal的应用：

Preorder Traversal 可以用来print directory listing:

Postorder traversal可以用来总计file sizes：

为了避免写Print，sumfilesizes这些具体的方法，我们可以采用visitor pattern来统一写tree traversal：

preorder traversal的runtime分析：

Every node visited exactly once. Constant work per visit.

Level Order Traversal

Level Order Traversal就是一层一层地Visit nodes on 0th level, then 1st level, then 2nd level, etc.

iterative deepening:

Level Order Traversal的time complexity:

Level Order Tree Traversal

Tree height和run time也没有直接关系，不要简单地相关联，而是要每种情况各自分析：

Range Finding

Geometric search: 比如我们想在tree里找到某个范围里的item:

实施起来很简单，traverse整个数，用一个hashset来装满足条件的item:

很intuitive地pruning来绕过那些根本不可能存在满足条件的分支：

Search的runtime：不知道为啥

Spatial Trees

如果我们想在平面上进行range finding, 我们需要另外一种tree:

Quadtree:

Study Guide:

Level C:

1.

LEVEL B:

参考：（可能height得定义不同，他们这里是1+ height(T.left) + height(T.right))
Diameter Of a Binary Tree

A LEVEL:

1.