8. 1 Tree Level the level of root is 1 the level of an elementthe level of its parent+1 Depth of a tree the maximum level of its elements
8.1 Tree • Level: the level of root is 1 the level of an element=the level of its parent+1 • Depth of a tree: the maximum level of its elements
8.2 Binary Trees I Definition a binary tree t is a finite (possibly empty) collection of elements When the binary tree is not empty It has a root element The remaining elements(if any)are partitioned into two binary trees, which are called the left and right subtrees oft
8.2 Binary Trees 1.Definition: A binary tree t is a finite (possibly empty) collection of elements. When the binary tree is not empty: • It has a root element • The remaining elements(if any) are partitioned into two binary trees, which are called the left and right subtrees of t
8.2 Binary Trees 2.The essential differences between a binary tree and a tree are da binary tree can be empty, whereas a tree cannot 2 )Each element in a binary tree has exactly two subtrees(one or both of these subtrees may be empty). Each element in a tree can have any number of subtrees
8.2 Binary Trees 2.The essential differences between a binary tree and a tree are: 1)A binary tree can be empty,whereas a tree cannot. 2)Each element in a binary tree has exactly two subtrees(one or both of these subtrees may be empty).Each element in a tree can have any number of subtrees
8.2 Binary Trees 3)The subtrees of each element in a binary tree are ordered. That is, we distinguish between the left and the right subtrees.The subtrees in a tree are unordered
8.2 Binary Trees 3) The subtrees of each element in a binary tree are ordered. That is, we distinguish between the left and the right subtrees.The subtrees in a tree are unordered
8.2 Binary Trees Example of a binary tree b d
8.2 Binary Trees • Example of a binary tree + * / a b c d