《数据结构的算法在C++中的应用》（英文版）Chapter 8 Binary and other trees

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