Tiêu đề Unit 4.pdf ✅

Data Structures X 03 October, 2015
Arrays, linked lists, stacks, queues have been used to represent linear or tabular data. These structures in general are not suitable for representing hierarchical data. In hierarchical data we have ancestor-descendant, superior-subordinate, whole-part, or similar relationships among data elements. Trees Parent Child 2 Grand Child 1 Grand Child 2 Child 3 Grand Child 3 Grand Child 4 Child 4 Grand Child 5 Child 1
A tree T is a finite nonempty set of elements. One of the elements is called the root, and the remaining elements, if any, are partitioned into trees, which are called the sub trees of T. The element at the highest level of the hierarchy is the root. The elements at the next level are the roots of the sub trees formed by partitioning of the remaining elements. Trees Parent Child 2 Grand Child 1 Grand Child 2 Child 3 Grand Child 3 Grand Child 4 Child 4 Grand Child 5 Child 1 Root Sub Tree Siblings Terminal Node
Level of an Element – root is at level 1 ; children, if any, are at level 2 ; their children, if any, are at level 3 ; and so on. Degree of an Element – the number of children it has. The degree of a leaf is zero. Degree of a Tree – the maximum of its element degrees. e.g. 4. Height/Depth of a Tree – the maximum level number of the tree. e.g. 3 Trees Parent Child 2 Grand Child 1 Grand Child 2 Child 3 Grand Child 3 Grand Child 4 Child 4 Grand Child 5 Child 1 Level 1 Degree = 4 Level 2 Degree = 0 Level 3