Chapter 8 Binary and other trees
Chapter 8 Binary and other trees
Two kinds of data structure Linear: list, stack, queue, string Non-linear: tree, graph
Two kinds of data structure • Linear: list, stack, queue, string • Non-linear: tree, graph
8. 1 Tree 1. Definition: A tree t is a finite nonempty set of elements One of these elements is called the root, and the remaining elements(if any are partitioned into trees which are called the subtrees of t
8.1 Tree 1.Definition: A tree T is a finite nonempty set of elements. One of these elements is called the root, and the remaining elements(if any) are partitioned into trees which are called the subtrees of T
8. 1 Tree example B C ①D E)①G①① KL
8.1 Tree • example A B C D E F G H I J K L M
8. 1 Tree Terminology Degree of an elememts: the number of children it has Degree of a tree: the maximum of its element d legree Leaf: element whose degree is o Branch: element whose degree is not o
8.1 Tree 2.Terminology • Degree of an elememts: the number of children it has. • Degree of a tree: the maximum of its element degrees • Leaf: element whose degree is 0 • Branch: element whose degree is not 0
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