THE TREE DATA MODEL Một danh sách được thảo luận trong Bản tin cuối cùng là một cấu trúc tuyến tính, trong khi một cái cây là một phi tuyến tính cơ cấu đại diện cho mối quan hệ thứ bậc của thông tin, chẳng hạn như các thư mục và các tập tin được lưu trữ trong máy tính. Chúng tôi có thể xác định chính thức một cây như là một tập hợp hữu hạn của các nút và các cạnh như vậy mà | INTRODUCTION TO COMPUTER SCIENCE HANDOUT 5. THE TREE DATA MODEL K5 K6 Computer Science Department Văn Lang University Second semester -- Feb 2002 Instructor Trăn Đức Quang Major themes 1. Basic Terminology 2. Implementation of Trees 3. Binary Trees and Binary Search Trees Reading Sections and . BASIC TERMINOLOGY A list discussed in the last handout is a linear structure whereas a tree is a non-linear structure representing hierachical relationships of information such as that of directories and files stored in a computer. We can define formally a tree as a finite set of nodes and edges such that 1. There is one specially designated node called the root of the tree. The root is generally drawn at the top. 2. Every node c other than the root is connected by an edge to some one other node p called the parent of c. c is also called a child of p. We draw the parent of a node above that node. 3. A tree is connected in the sense that if we start at any node n other than the root move to the parent of n to the parent of the parent of n and so on we eventually reach the root of the tree. n4 ni n5 n2 r n3 30 INTRODUCTION TO COMPUTER SCIENCE HANDOUT 5. THE TREE DATA MODEL In the figure r is the root and has three children n1 n2 and n3. We can define important concepts from the figure. 1. The node n1 has two children n4 and n5 but the nodes n2 and n3 both have no children. A node with no children is called a leaf otherwise they are interior. 2. n4 is a descendant of r and n1 conversely r and n1 are ancestors of n4. 3. Nodes n1 n2 and n3 are siblings so are n4 and n5. 4. The height of r is 2 this is also the height of the tree. The height of n1 is 1 and of n4 is 0. The depth or level of r is 0 of n1 is 1 and n4 is 2. IMPLEMENTATION OF TREES Many data structures can be used to represent trees. Which one we should use depends on the particular operations we want to perform. In this very short handout we use a common representation for a tree called .
