Data structures are essential programming tools used to organize and store data.
ID: 3684469 • Letter: D
Question
Data structures are essential programming tools used to organize and store data. These structures allow programmers to use data more efficiently. With advanced data structures, programmers are able to create more robust structures. Trees are one of the most common advanced data structures. For this Discussion, consider the following questions: What is a data tree? How are data trees used in Java programming? For this Discussion: Provide a general explanation of data trees. Then, select two specific types of data trees and compare them. For this Discussion, you should provide at least one type of data tree
Explanation / Answer
A tree is widely used as a abstract data type-which simulates a hierarchial tree structure,with a root value and subtrees of children with parent nodes,represented as a set of linked nodes. To put it simply,a tree data structure is recursively defined as a group of nodes where each node is a data structure consisting of a value,together with a list of references to child nodes.
When actually represented as a data structure it is usually represented and worked with separately by node . For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent .
Terminology- A node is a structure which may contain a value or condition, or represent a separate data structure (which could be a tree of its own). Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn growing downwards). A node that has a child is called the child's parent node . A node has at most one parent.
An internal node is any node of a tree that has child nodes. Similarly, an external node is any node that does not have child nodes.
The topmost node in a tree is called the root node. Depending on definition, a tree may be required to have a root node , or may be allowed to be empty, in which case it does not necessarily have a root node. Being the topmost node, the root node will not have a parent. It is the node at which algorithms on the tree begin, since as a data structure, one can only pass from parents to children. Note that some algorithms begin at the root, but first visit leaf nodes, only visit the root last. All other nodes can be reached from it by following edges or links. In diagrams, the root node is conventionally drawn at the top. In some trees, such as heaps, the root node has special properties. Every node in a tree can be seen as the root node of the subtree rooted at that node.
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height 1.
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. Nodes thus correspond to subtrees (each node corresponds to the subtree of itself and all its descendants) – the subtree corresponding to the root node is the entire tree, and each node is the root node of the subtree it determines; the subtree corresponding to any other node is called a proper subtree .
Tree representation:- There are many different ways to represent trees; common representations represent the nodes as dynamically allocated records with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap).
Indeed, a binary tree can be implemented as a list of lists ,the head of a list is the left child (subtree), while the tail (the list of second and future terms) is the right child (subtree). This can be modified to allow values as well, as in Lisp S-expressions, where the head (value of first term) is the value of the node, the head of the tail is the left child, and the tail of the tail is the right child.
In general a node in a tree will not have pointers to its parents, but this information can be included or stored separately. Alternatively, upward links can be included in the child node data, as in a threaded binary tree.
Types of trees:-One such example of a treeis:- BINARY TREE-a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
Terminology-
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.