preorder(tree) if empty(tree) stop e⊥se print(element(tree) preorder(child(tree) preorder(next(tree))
11 preorder(tree) if empty(tree) stop else print(element(tree)) preorder(child(tree)) preorder(next(tree))
Example: Unix Directory Traversal Preorder PostOrder ch1 mark ch2.r ch3.r chi.r 240 ch2.r syl.r ch3.r fa1198 course sy1.「 cop3530 sprig a1198 12562 spr99 cop3530 12 course sum99 6 syl.r alex 8 bill work 1 work grades 3 progl r 4 course cop3212 og2r 1 fa198 fa1198 9 prog2 r 2 proglr faz,grades o progl.r prog2r cop3212 course bill grades /u
12 Example: Unix Directory Traversal PreOrder PostOrder
Binary Trees a tree in which no node can have more than two children Generic binary tree The depth of anaverage" binary tree is considerably smaller than N, even though in the worst case, the depth can be as large as n-1 Worst-case binary tree
13 Binary Trees A tree in which no node can have more than two children The depth of an “average” binary tree is considerably smaller than N, even though in the worst case, the depth can be as large as N – 1. Generic binary tree Worst-case binary tree
Binary Tree adt Implementation at most two children, we can keep direct pointers to them a linked list is physically a pointer, so is a tree Possible operations on the Binary Tree ADT Parent, left _child, right child, sibling, root, etc Tree operations Search insertion and deletion Make a Binary Tree ADT later
14 Binary Tree ADT Implementation at most two children, we can keep direct pointers to them a linked list is physically a pointer, so is a tree! Possible operations on the Binary Tree ADT Parent, left_child, right_child, sibling, root, etc Tree operations: Search, insertion and deletion Make a Binary Tree ADT later …
A drawing of linked list with one pointer a drawing of binary tree with two pointers Struct BinaryNode I double element // the data BinaryNode* lefti / left child BinaryNode* right; / right child
15 A drawing of linked list with one pointer … A drawing of binary tree with two pointers … Struct BinaryNode { double element; // the data BinaryNode* left; // left child BinaryNode* right; // right child }