Class Notes (835,507)
Canada (509,212)
CMPT 225 (60)
John Edgar (28)

CMPT 225 Week 8 Lecture 1

3 Pages
Unlock Document

Computing Science
CMPT 225
John Edgar

Tree: Set of nodes or vertices Has single starting point (root, at top) Each node is connected by an edge to another node Connected graph One less edge than number of nodes Can use descendants for children, even if not direct Also have ancestors - parents, grandparents, etc And siblings - have same parent Don't call cousins cousins but sometimes look at that relationship Root can be the leaf, if only one node in tree Subtree is any node in the tree with all its descendants. Subtree rooted at x. Paths are one way. How you get from one node to another. Height of a node: length of longest path from that node to leaf Height of tree = height of root. (length of longest path from root to leaf) Or height of different tree could be number of levels including root. Two definitions differ by one, neither is wrong. Depth is distance to root. Abinary tree is perfect if: No node has only one child All trees have the same depth Perfect binary tree of height h has 2^(h+1) - 1 nodes, 2^h of which are leaves Are also complete Each level doubles the number of nodes. Root level has one node. Just over half the nodes are leaves (because root has 1) Balanced binary tree: Leaves are all about same distance from the root Exact specification varies Sometimes balanced by comparing heights of nodes (height of right sub tree is at most +- 1 height of left sub tree) Sometimes compare height to number of nodes (used for red-black trees) Traversal algo for a binary tree visits every node in the tree. Typically, do something on visiting each node. Naturally recursive. 3 methods: Inorder, Preorder, Postorder InOrder: inOrder(Node* nd) { if (nd != null) { inOrder(nd->leftchild); visit(nd); inOrder(nd->rightchild); } } Visit between two recursive calls. On BST, will print contents in order. Preorder starts with a visit. First visit the root. preOrder(Node*
More Less

Related notes for CMPT 225

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.