其他课程面向对象程序设计lecture

1、CS 1031Tree Traversal Techniques; Heaps Tree Traversal ConceptTree Traversal Techniques: Preorder, Inorder, PostorderFull Trees Almost Complete TreesHeapsCS 1032Binary-Tree Related DefinitionsThe children of any node in a binary tree are ordered into a left child and a right childA node can have a l

2、eft anda right child, a left childonly, a right child only,or no childrenThe tree made up of a leftchild (of a node x) and all itsdescendents is called the left subtree of xRight subtrees are defined similarly10131198465712CS 1033A Binary-tree Node Classclass TreeNode public: typedef int datatype; T

3、reeNode(datatype x=0, TreeNode *left=NULL, TreeNode *right=NULL)data=x; this-left=left; this-right=right; ;datatype getData( ) return data; TreeNode *getLeft( )return left;TreeNode *getRight( )return right;void setData(datatype x) data=x;void setLeft(TreeNode *ptr) left=ptr;void setRight(TreeNode *p

4、tr) right=ptr; private:datatype data; / different data type for other appsTreeNode *left; / the pointer to left childTreeNode *right; / the pointer to right child;CS 1034Binary Tree Classclass Tree public: typedef int datatype; Tree(TreeNode *rootPtr=NULL)this-rootPtr=rootPtr; TreeNode *search(datat

5、ype x); bool insert(datatype x); TreeNode * remove(datatype x); TreeNode *getRoot()return rootPtr; Tree *getLeftSubtree(); Tree *getRightSubtree(); bool isEmpty()return rootPtr = NULL; private: TreeNode *rootPtr; CS 1035Binary Tree TraversalTraversal is the process of visiting every node onceVisitin

6、g a node entails doing some processing at that node, but when describing a traversal strategy, we need not concern ourselves with what that processing isCS 1036Binary Tree Traversal TechniquesThree recursive techniques for binary tree traversalIn each technique, the left subtree is traversed recursi

7、vely, the right subtree is traversed recursively, and the root is visitedWhat distinguishes the techniques from one another is the order of those 3 tasksCS 1037Preoder, Inorder, PostorderIn Preorder, the rootis visited before (pre)the subtrees traversalsIn Inorder, the root isvisited in-between left

8、 and right subtree traversalIn Preorder, the rootis visited after (pre)the subtrees traversalsPreorder Traversal:Visit the rootTraverse left subtreeTraverse right subtreeInorder Traversal:Traverse left subtreeVisit the rootTraverse right subtreePostorder Traversal:Traverse left subtreeTraverse right

9、 subtreeVisit the rootCS 1038Illustrations for TraversalsAssume: visiting a node is printing its labelPreorder: 1 3 5 4 6 7 8 9 10 11 12Inorder:4 5 6 3 1 8 7 9 11 10 12Postorder:4 6 5 3 8 11 12 10 9 7 113119846571210CS 1039Illustrations for Traversals (Contd.)Assume: visiting a node is printing its

10、dataPreorder: 15 8 2 6 3 711 10 12 14 20 27 22 30Inorder: 2 3 6 7 8 10 1112 14 15 20 22 27 30Postorder: 3 7 6 2 10 1412 11 8 22 30 27 20 1561582371110141220272230CS 10310Code for the Traversal TechniquesThe code for visitis up to you to provide, dependingon the applicationA typical examplefor visit(

11、) is toprint out the data part of its inputnodevoid inOrder(Tree *tree) if (tree-isEmpty( ) return; inOrder(tree-getLeftSubtree( ); visit(tree-getRoot( ); inOrder(tree-getRightSubtree( );void preOrder(Tree *tree) if (tree-isEmpty( ) return; visit(tree-getRoot( ); preOrder(tree-getLeftSubtree(); preO

12、rder(tree-getRightSubtree();void postOrder(Tree *tree) if (tree-isEmpty( ) return; postOrder(tree-getLeftSubtree( ); postOrder(tree-getRightSubtree( ); visit(tree-getRoot( );CS 10311Application of Traversal Sorting a BSTObserve the output of the inorder traversal of the BST example two slides earlie

13、rIt is sortedThis is no coincidenceAs a general rule, if you output the keys (data) of the nodes of a BST using inorder traversal, the data comes out sorted in increasing orderCS 10312Other Kinds of Binary Trees(Full Binary Trees)Full Binary Tree: A full binary tree is a binary tree where all the le

14、aves are on the same level and every non-leaf has two childrenThe first four full binary trees are:CS 10313Examples of Non-Full Binary TreesThese trees are NOT full binary trees: (do you know why?)CS 10314Canonical Labeling ofFull Binary TreesLabel the nodes from 1 to n from the top to the bottom, l

15、eft to right11231234567123456789101112131415Relationships between labelsof children and parent:2i2i+1iCS 10315Other Kinds of Binary Trees(Almost Complete Binary trees)Almost Complete Binary Tree: An almost complete binary tree of n nodes, for any arbitrary nonnegative integer n, is the binary tree m

16、ade up of the first n nodes of a canonically labeled full binary112123456712123456123412345CS 10316Depth/Height of Full Trees and Almost Complete TreesThe height (or depth ) h of such trees is O(log n)Proof: In the case of full trees, The number of nodes n is: n=1+2+22+23+2h=2h+1-1Therefore, 2h+1 =

17、n+1, and thus, h=log(n+1)-1Hence, h=O(log n)For almost complete trees, the proof is left as an exercise.CS 10317Canonical Labeling ofAlmost Complete Binary TreesSame labeling inherited from full binary treesSame relationship holding between the labels of children and parents:Relationships between la

18、belsof children and parent:2i2i+1iCS 10318Array Representation of Full Trees and Almost Complete TreesA canonically label-able tree, like full binary trees and almost complete binary trees, can be represented by an array A of the same length as the number of nodes Ak is identified with node of label

19、 kThat is, Ak holds the data of node kAdvantage: no need to store left and right pointers in the nodes save memoryDirect access to nodes: to get to node k, access AkCS 10319Illustration of Array RepresentationNotice: Left child of A5 (of data 11) is A2*5=A10 (of data 18), and its right child is A2*5

20、+1=A11 (of data 12). Parent of A4 is A4/2=A2, and parent of A5=A5/2=A2615821118122027133015820211302713610121234567891011CS 10320Adjustment of IndexesNotice that in the previous slides, the node labels start from 1, and so would the corresponding arraysBut in C/C+, array indices start from 0The best

21、 way to handle the mismatch is to adjust the canonical labeling of full and almost complete trees.Start the node labeling from 0 (rather than 1).The children of node k are now nodes (2k+1) and (2k+2), and the parent of node k is (k-1)/2, integer division.CS 10321Application of Almost Complete Binary

22、 Trees: HeapsA heap (or min-heap to be precise) is an almost complete binary tree whereEvery node holds a data value (or key)The key of every node is the keys of the childrenNote:A max-heap has the same definition except that the Key of every node is = the keys of the childrenCS 10322Example of a Mi

23、n-heap16581511181220273330CS 10323Operations on HeapsDelete the minimum value and return it. This operation is called deleteMin. Insert a new data valueApplications of Heaps: A heap implements a priority queue, which is a queue that orders entities not a on e first-serve basis, but on a priority bas

24、is: the item of highest priority is at the head, and the item of the lowest priority is at the tail Another application: sorting, which will be seen laterCS 10324DeleteMin in Min-heapsThe minimum value in a min-heap is at the root!To delete the min, you cant just remove the data value of the root, b

25、ecause every node must hold a keyInstead, take the last node from the heap, move its key to the root, and delete that last nodeBut now, the tree is no longer a heap (still almost complete, but the root key value may no longer be the keys of its children CS 10325Illustration of First Stage of deletem

26、in16581511181220273330168151118122027333016815111812202733301681511181220273330CS 10326Restore HeapTo bring the structure back to its “heapness”, we restore the heapSwap the new root key with the smaller child.Now the potential bug is at the one level down. If it is not already the keys of its child

27、ren, swap it with its smaller childKeep repeating the last step until the “bug” key es its children, or the it es a leafCS 10327Illustration of Restore-Heap168151118122027333016121511188202733301611151218820273330Now it is a correct heapCS 10328Time complexity of insert and deletminBoth operations t

28、akes time proportional to the height of the treeWhen restoring the heap, the bug moves from level to level until, in the worst case, it es a leaf (in deletemin) or the root (in insert)Each move to a new level takes constant timeTherefore, the time is proportional to the number of levels, which is th

29、e height of the tree.But the height is O(log n)Therefore, both insert and deletemin take O(log n) time, which is very fast.CS 10329Inserting into a minheapSuppose you want to insert a new value x into the heapCreate a new node at the “end” of the heap (or put x at the end of the array)If x is = its parent, doneOtherwise, we have to restore the heap:Repeatedly swap x with its parent until either x reaches the root of x es = its parentCS 10330Illustration of Insertion Into the Hea