6 More Terminologies Path A sequence of edges Length of a path number of edges on the path Depth of a node length of the unique path from the root to that node Height of a node length of the longest path from that node to a leaf all leaves are at height 0 The height of a tree= the height of the root the depth of the deepest leaf Ancestor and descendant If there is a path from n1 to n2 Proper ancestor and proper descendant of n1 n1 is an ancestor of n2. n2 is a descendant
6 More Terminologies Path A sequence of edges Length of a path number of edges on the path Depth of a node length of the unique path from the root to that node Height of a node length of the longest path from that node to a leaf all leaves are at height 0 The height of a tree = the height of the root = the depth of the deepest leaf Ancestor and descendant If there is a path from n1 to n2 n1 is an ancestor of n2, n2 is a descendant of n1 Proper ancestor and proper descendant
Example: UNIX Directory fuss mark* alex* bill* book course junk junk work* course+ chI.r ch2. r ch3. r cop3530* cop3212 fal198* spr99* sum99* fa!98* fa99米 yl.T syl. r grades progl r prog2 r prog2 r progl r grades Figure 4.5 UNIX directory
7 Example: UNIX Directory
Tree Operations Traversal, the most important we will not implement a general tree, so wont discuss Search Insertion Deletion
8 Tree Operations Traversal, the most important we will not implement a general ‘tree’, so wont discuss Search Insertion Deletion
Tree Traversal Used to print out the data in a tree in a certain order Pre-order traversal Print the data at the root Recursively print out all data in the leftmost subtree Recursively print out all data in the rightmost subtree
9 Tree Traversal Used to print out the data in a tree in a certain order Pre-order traversal Print the data at the root Recursively print out all data in the leftmost subtree … Recursively print out all data in the rightmost subtree
A drawing of tree with two pointers Struct TreeNode i double elementi // the data TreeNode* child; / FIRST child go to the next generation TreeNode* next;// next SIBLING: go to the same generation
10 A drawing of tree with two pointers … Struct TreeNode { double element; // the data TreeNode* child; // FIRST child : go to the next generation TreeNode* next; // next SIBLING : go to the same generation }