The Self-Taught Computer Scientist
Download 1.48 Mb. Pdf ko'rish
|
books-library.net-11301817Az7X6
- Bu sahifa navigatsiya:
- Figure 14.2
- Figure 14.4
Figure 14.1: An example of a tree data structure
Data Structures 148 one or more child nodes is called a parent node. Sibling nodes share the same parent. The connection between two nodes in a tree is called an edge (Figure 14.2). You can move from one node to another as long as they share an edge (Figure 14.3). Every node in a tree except the root has a single parent node. A node without child nodes is called a leaf node, and a node with child nodes is called a branch node. A binary tree is a tree data structure where each node can have only two child nodes (sometimes called a child or children). Every node in a binary tree (except the root) is either the left or right child of a parent node (Figure 14.4). Everything else in a binary tree is the same as a general tree; the only difference is the child node limit. 5 Root Node Parent Node Child Node Sibling Nodes Edge 7 9 4 6 11 6 13 7 Figure 14.2: A tree with a root node, parent nodes, child nodes, and edges 5 Root Node Parent Node Child Node Edge 7 9 4 6 11 6 13 7 Sibling Nodes Figure 14.3: A path through a tree Chapter 14 Binary Trees 149 A binary search tree is a tree data structure where each node can have only two children, and the tree stores its nodes in sorted order where every node’s value is greater than any value in its left subtree and lower than any value in its right subtree (Figure 14.5). Like hash table keys, you cannot store duplicate values in a binary search tree. You can get around this restriction and handle duplicate values by adding a count field in your tree’s node objects to track the number of occurrences of a given value. Unlike linear data structures like arrays and linked lists, you cannot always traverse a tree without backtracking. You can reach any node in a tree by starting from the root node, but once you have moved away from the root node, you can reach only that node’s descendants. A node’s descendants are its children and their children and their children’s children, etc. For example, Figure 14.6 shows a simple tree with a root node A, leaf nodes B, D, and E, and a branch node C. The A node has two children (B and C), and the C node has two children (D and E). The nodes B, C, D, and E are the A node’s descendants. 5 Right child Left child 7 9 4 6 11 6 13 7 Figure 14.4: In a binary tree, a parent node can have only two child nodes. 9 12 5 3 8 16 15 9 6 Download 1.48 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling