TeaPort

Zhejiang University Understanding of the Puzzle We simply regard the trees as the same as long as they have the same children for every node. Divide and Conquer The representation of a binary tree Build a Binary Tree Judge whether they are Isomers. Representing a Binary Tree Static Linked List: A Special Array. Structure of the Program 12345678BinTree Build();bool Judge();int main(){ Build tree1; Build tree2; Judge isomers; return 0;} Design the Functions 12345678#define ...

Zhejiang University DFS(Depth First Search) 1234567void DFS(Vertex V){ visited[V] = true; for(each adjacent vertex w){ if(!visited[w]) DFS(w); }} Complexity Adjacent List: O(N+E)O(N+E)O(N+E) Adjacent Matrix: O(N2)O(N^2)O(N2) BFS(Breadth First Search) 1234567891011void BFS(Vertex V){ visited[V] = true; Enqueue(V, Q); while(!IsEmpty(Q)){ V = Dequeue(Q); for(each adjacent vertex W of V) if(!visited[V]){ ...

Zhejiang University Graph It is used to represent a many-to-many relationship. It is so powerful because it includes both linear lists(one to one) and trees(one to many). Components Vertex(V): the set of all vertexes. Edge: the set of all sides. (v, w). Double directions. . From v to w (single direction). No multiple edges or multiple loops. A Quick Review: Definition of Abstract Data Type Name: Graph DataSet: G(V, E). V is Nonempty E is limited. Operation Set Graph Create() Graph Insert ...

Zhejiang University Set Operations There are some basic operations about sets. Eg: Union, Intersection, Set Difference… Union-Find Set Problem: There are n nodes. Some of them are connected. How do we know whether arbitrary 2 of them are connected? Answer: Make n sets to include n nodes. Then union those connected. Find whether 2 given nodes are in the same set. Creating Union-Find Set How to Store a Set? Tree. The root will be a set. Each node will be an element. Parental Representation: The ...

Zhejiang University Huffman Tree Question: How can we fit a 100 mark test into a 5 standards judging system? We need to carefully arrange our if clauses in accordance with the frequency of the actual result. (Decision Tree) Cost: ∑ratio×layers\sum\rm ratio\times layers∑ratio×layers Definition Weighed Path Length: A binary tree with n nodes with weight w. The distance between root and each leaf is l. Then the WPL for each leaf node will be WPL=∑i=1nwklkWPL = \sum_{i=1}^nw_kl_k WPL=i=1∑n​wk​lk​ ...

Zhejiang University Heap What is heap? When a computer is doing many things at the same time, different tasks will have different priorities. Thus we have a special data structure: Priority Queue. Creating a heap We need 2 functions: insert and delete Array difficult to delete a element linked list Ordered Array difficult to insert Ordered linked list Tree Tree Tree has some great characteristics in realizing heap. The insert process is related to the height of a tree while the delete proces ...

Zhejiang University Binary Search Tree (BST) Properties Left subTrees’s values are smaller than their roots Right subTrees’s values are larger than their roots Left and Right subTrees are all BSTs API Position Find(ElementType X, BinTree BST) Position FindMin(BinTree BST) Position FindMax(BinTree BST) BinTree Insert(ElementType X, BinTree BST) BinTree Delete(ElementType X, BinTree BST) Find Recursion Loop 123456789while(BST){ if(X > BST->Data) BST = BST->Right; els ...

Zhejiang University Binary Tree Properties Degree = 2. L and R are different. Layer i has a maximum number of nodes 2^(i-1) Degree = K, node sum = 2^(k-1) For any not-null binary tree, n0 = leaf, n2 = nodes which have 2 non-leaf nodes, then n0 = n2+1 Operation Set Boolean IsEmpty(BinTree BT) void Traversal(BinTree BT) PreOrderTraversal:rLR InOrderTraversal:LrR PostOrderTraversal:LRr LevelOrderTraversal:UD,LR BinTree CreatBinTree() Special Binary Tree Skewed Binary Tree Perfect Binary T ...

Zhejiang University Tree A Structure used for managing and organizing different levels of data. Properties A special node: Root® The rest nodes can be divided into m nonoverlapping subsets called SubTree. SubTrees do not overlap. Every Node has one parent except r. A tree with N nodes has N-1 sides. Terms Degree: The number of SubTrees for a Node. Degree of a Tree: The maximum Degree for all nodes of a tree. Leaf Parent Child Sibling Path and the Distance of Path: From Node n1 to Node nk, t ...

Zhejiang University Queue A restricted linear table. Queue and Round-robin Queue Properties AddQ DeleteQ FIFO Operation Set Queue CreateQueue(int Maxsize) int IsFull(Queue Q, int MaxSize) void AddQ(Queue Q, ElementType item) int IsEmpty(Queue Q) ElementType DeleteQ(Queue Q) indicators front(begins with -1) rear(begins with -1) Round-robin Queue A more efficient way to make use of space. Questions: How to tell whether a queue is full? Why is it difficult to tell whther it is full? Wha ...