{"id":223,"date":"2018-07-18T12:23:11","date_gmt":"2018-07-18T12:23:11","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=223"},"modified":"2018-12-12T10:04:54","modified_gmt":"2018-12-12T10:04:54","slug":"tree-adt-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/tree-adt-i\/","title":{"rendered":"Tree ADT -I"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of an important Linear ADTs. In this module we will discuss Trees - an important hierarchical data structure.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022 To explain the concept of Trees\r\n\r\n\u2022 To discuss General Trees with some examples\r\n\r\n\u2022 To describe the representations of General Trees\r\n\r\n\u2022 To explain the different tree traversals\r\n\r\n\u2022 To discuss the conversion of General Trees to Binary Trees\r\n\r\n \r\n\r\n19.1 Introduction<\/strong>\r\n\r\n \r\n

So far in the previous modules we have discussed linear data structures such as lists, stacks and queues. We also have other types of data structures which are non-linear, for example trees and graphs. Trees are hierarchical data structures. Trees are used for applications such as sorting, searching, expression evaluation, etc. Trees are especially well suited to recursive algorithm implementations.<\/p>\r\n \r\n\r\n19.1.1 What are Trees?<\/strong>\r\n\r\n \r\n

A tree consists of a specially designated node called the root and zero or more sub-trees. A tree can also be empty containing no nodes. Figure 19.1 shows an example<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n<\/div>\r\n

\r\n

of a tree where A is the root of the tree, B and F are internal nodes that is they have children and C,D,E,G, H and I are all leaf nodes (that is they have no children.<\/p>\r\n \r\n\r\n19.1.2 Trees -Terminology<\/strong>\r\n\r\n \r\n

Generally trees can be used to represent relationships. Let us look at some terminologies associated with trees. Trees are hierarchical in nature and \u201cParent-child\u201d <\/strong>relationship exists between nodes in a tree. This concept can be generalized as ancestor and descendant<\/strong> relations. Lines between the nodes are called edges. Ancestors <\/strong>of a node are it\u2019s parent, grandparent, great-grandparent, etc. Similarly descendant <\/strong>of a node are it\u2019s child, grandchild, great-grandchild, etc. A sub-tree <\/strong>in a tree is any node in the tree together with all of its descendants. Depth<\/strong> of a node is the number of ancestors it has. Height<\/strong> of a tree is the maximum depth of any of it\u2019s node. Degree<\/strong> of a node is the number of its children the node has. On the other hand the degree<\/strong> of a tree is the maximum degree of it\u2019s nodes.<\/p>\r\n \r\n

Let us consider the example given in Figure 19.2, the root<\/strong> is the node without a parent (A), siblings<\/strong> are nodes that share the same parent, example are nodes E and F that share the same parent B. Internal nodes<\/strong> are nodes with at least one child (example - A, B, C, F), while external node<\/strong> (or leaf nodes ) are nodes without children (example -E, I, J, K, G, H, D). A subtree<\/strong> is a tree consisting of a node and its descendants (example subtree rooted at C and having descendants G and H). Each node in a tree may have a subtree. In other words, the subtree of each node includes one of its children and all descendants of that child (Figure 19.3).<\/p>\r\n \r\n\r\n\"\"\u00a0<\/strong>\r\n\r\nTo summarize we can divide the vertices of a tree into three categories: the <\/span>root<\/em>, <\/span>leaves <\/em>and the<\/span> internal nodes<\/em>. The root has no parent and can have zero or more children, the leaf has one parent and no children while the internal nodes has parent and one or more children.<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n19.2\u00a0 Kinds of Trees<\/strong>\r\n\r\n \r\n

One of the classifications of trees is based on the maximum number of children a tree are allowed to have. General trees are trees where a node can have any number of children. N-ary trees are trees where a node can have a maximum of N children. Binary trees are 2-ary trees where a node can have a maximum of two children.<\/p>\r\n \r\n\r\n19.2.1 General Tree<\/strong>\r\n\r\n \r\n

The general tree has a specially designated node r, called the root of the tree and sets that are general trees, called subtrees of r. Here there is no restriction on the number of subtrees a node can have.<\/p>\r\n \r\n\r\n19.2.2 N-ary Tree<\/strong>\r\n\r\n \r\n

The n -ary tree can be defined as a set T of nodes that is either empty or partitioned into disjoint subsets. It has a specially designated node r, called the root of the tree and n possibly empty sets that are n-ary subtrees of r.<\/p>\r\n \r\n\r\n19.2.3 Binary Tree<\/strong>\r\n\r\n \r\n

The binary tree can be defined as a set T of nodes that is either empty or partitioned into two disjoint subsets. It has a specially designated node r, called the root of the tree and two possibly empty subtrees called as left and right subtrees of r.<\/p>\r\n \r\n\r\n19.3\u00a0 Representation of Trees<\/strong>\r\n\r\n \r\n

The concept of a tree is verycommon as well as very important. Each node in the tree has only have only one parent, and a node has children. Of course leaf nodeshave no children and the root node which is at the top has no parent. We need to look at effective data structures to represent trees.<\/p>\r\n \r\n\r\n19.4 Importance of Trees<\/strong>\r\n\r\n \r\n

Trees are important since execution and processing for many applications can be expressed as a tree, e.g. method calls as a program runs, searching a maze or puzzle, etc.. Trees are important for cognition and computation in areas such as computer science, language processing (by humans or computers) for example parse trees and knowledge representation (or modeling of the \u201creal world\u201d) for example family trees; biological taxonomy (kingdom, phylum, \u2026, species); etc. Let us now look at some examples of trees.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n

Figure 19.4 shows an example of representing a file system organization of a computing system using trees. We can see that the file system is naturally represented using the hierarchical tree data structure. This example shows a 3-ary tree. Figure 19.5 shows the representation of semi-structured documents using trees.In both HTML and XML elements are identified in a document by their starttag<\/strong> and endtag<\/strong>. Complex elements are constructed from other elements hierarchically, whereas simple elements contain data values. We can see the correspondence between the HTML\/XML textual representation and the tree structure. HTML elements are represented by tree nodes and organized into a hierarchy. In the tree representation, internal nodes represent complex elements, whereas leaf nodes represent simple elements.<\/p>\r\n \r\n\r\n\"\"\r\n

In this representation, tags are associated with the edges which represent the schema names that is the names of attributes, object types (or entity types or classes), and relationships. The internal nodes represent individual objects or composite attributesand the leaf nodes represent actual data values of simple (atomic) attributes.<\/p>\r\n \r\n\r\n19.5 Recursive Data Structure<\/strong>\r\n\r\n \r\n\r\nIn general a recursive data structure is a data structure that contains a pointer or reference to an instance of itself. The tree data structure can be expressed as a recursive data structure. Figure 19.6 shows the recursive definition of the binary tree.Recursion is a <\/span>natural<\/em> way to express many algorithms.For recursive data-structures, recursive algorithms are a natural choice.<\/span>\r\n\r\n<\/div>\r\n\r\n\r\n\r\n
public class TreeNode<T><\/strong>\r\n\r\n \r\n\r\n{<\/strong>\r\n\r\nT\u00a0 <\/strong>nodeItem; TreeNode<T> left, right; TreeNode<T> parent;<\/strong>\r\n\r\n\u2026<\/strong>\r\n\r\n}<\/strong>\r\n

<\/p>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n

Figure 19.6Tree as a Recursive Data Structure<\/strong><\/p>\r\n\r\n

\r\n\r\n \r\n\r\n19.6 Tree ADT<\/strong>\r\n\r\n \r\n\r\nIn our discussion on trees as an ADT we use positions to abstract nodes. Generic functions include:\r\n\r\n \r\n\r\n\u2022 integersize<\/strong>() \u2013 This function gives the number of nodes in the tree.\r\n\r\n\u2022 booleanisEmpty<\/strong>() \u2013 This Boolean function signals true if the tree is empty\r\n\r\n\u2022 Iterator elements<\/strong>() \u2013 This function outputs all the elements of the tree in an iterative manner\r\n\r\n\u2022 Accessor functions: Some of the important functions to access the tree are:\r\n\r\n\u2013\u00a0 position root<\/strong>() \u2013 This function outputs the position of the root\r\n\r\n\u2013 position parent<\/strong>(p) - This function outputs the position of the parent of a node\r\n\r\n\u2013 positionIteratorchildren<\/strong>(p) - This function outputs the positions of all the children of a node\r\n\r\n\u2022 Query functions: These are some of the functions to query the tree data structure\r\n\r\n\u2013 booleanisInternal<\/strong>(p) \u2013 This Boolean function finds if a given node is an internal node.\r\n\r\n\u2013 booleanisExternal<\/strong>(p) -This Boolean function finds if a given node is an external or leaf node.\r\n\r\n\u00a0 \u2013 boolean<\/span>isRoot<\/strong>(p) - This Boolean function finds if a given node is a root node.<\/span>\r\n\r\n\u2022 Update functions: Some of the functions to update the tree are given below. Additional update functions may be defined by data structures implementing the Tree ADT<\/span>\r\n\r\n\u2013 <\/span>swapElements<\/strong>(p, q) \u2013 This functions swaps two elements of the tree given the tree T.<\/span>\r\n\r\n\u2013 <\/span>replaceElement<\/strong>(p, e) - This functions replaces an element of the tree given the tree T.<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\n19.7 Representation of the Tree<\/strong>\r\n\r\n \r\n

Before we discuss the details of the representation of the tree, let look at intuitive representation of Tree node. The tree can be represented by a list (Figure 19.7<\/strong>).<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Every tree node in general, how many ever children it can have contains data which stores useful information and pointers to its children and these nodes can be used\u00a0for the representation of the general tree (Figure 19.8 (a) and 19.8 (b)). However here we do not know the number of link fields needed since the number of children of each node is unknown.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n

Therefore the node of the general tree can be represented by a node storing the data, pointer to the parent node and information about where the sequence of children nodes are stored (Figure 19.9 (a)). Now let us look at different ways in which general trees can be represented.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n19.7.1 General Trees \u2013Implementation<\/strong>\r\n\r\n \r\n

One way to implement a general tree is to use a node whose structure uses a node consisting of the data element, pointer to the parent node and a pointer to the sequence of children nodes (Figure 19.9). In another link representation, specifically, a node left pointer points to its left-most child and it\u2019s right pointer points to a linked list of nodes that are it\u2019s siblings. Figure 19.10 shows the Left Child, Right Sibling Representationwhere we put the left child node to the node\u2019s left link and put the sibling to the node\u2019s right link.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n\r\n \r\n\r\n19.7.2 Parent Pointer Implementation<\/strong>\r\n\r\n \r\n

Figure 19.11 shows the parent pointer representation where we have an array where each element of the array stores the label of the node and the index to it\u2019s parent. For example the node C is stored in location of the array indexed 3, and its parent\u2019s index 1 which is the location of C\u2019s parent A.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n19.8 Tree Traversal<\/strong>\r\n\r\n \r\n

An important operation associated with trees is traversal of a tree. A traversal visits the nodes of a tree in a systematic manner. Depending on the order in which the nodes are traversed, there are three main types of traversal namely inorder, preorder and postorder traversals. These traversals can be defined recursively as given below:<\/p>\r\n \r\n

19.8.1 Inorder Traversal<\/strong><\/p>\r\n \r\n

In inorder traversal, the left most subtree of a node is visited in inorder, then the node is visited and then all the other subtrees are visited inorder. It is recursively as follows: Traverse in inorder the left subtree, visit the root and finally traverse in inorder the right subtree in case the tree has only two children. The algorithm for the inorder traversal of a general tree is given in Figure 19.12 where we traverse in inorder the left subtree, visit the root and finally traverse in inorder all children other than the leftmost subtree. Figure 19.13 shows the example for the Inorder traversal of a general tree.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n

In this traversalinorder(Become Rich)<\/em> we start at the root nodeBecome Rich<\/em>, but we need to inorder traverse its Left subtree. So we call inorder(Motivations).<\/em>Here again we need to inorder traverse its Left subtree. So we call inorder(Enjoy Life).<\/em> At this point Left subtree is empty so we go to the next step of the Inorder Traversal with Enjoy Life<\/em>which is visit node, so we visit this node Enjoy Life<\/strong>. <\/em>Now this node has no Right subtrees and hence this call is completed. This essentially means that the Inorder Left subtree call by inorder(Motivations)<\/em>is completed, so we visit this node, therefore the second node to be visited is Motivations.<\/em><\/strong>Now we go to the third step in the call inorder(Motivations)<\/em>which is inorder traversal of its children except leftsubtree. Therefore we call inorder(Help Poor Friends).<\/em> Since this node has no children, only step 2 takes place that is Help Poor Friends<\/em><\/strong> is the third node to be visited. Now we have completed the first step of inorder(Become Rich)<\/em>and so we go step to and Become Rich<\/em><\/strong>is the fourth node to be visited. The process continues by traversing the other children of Become Rich<\/em>and the nodes as visited in the order shown in Figure 19.13.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n19.8.2 Preorder Traversal<\/strong>\r\n\r\n \r\n

In preorder traversal we first visit the root and then traverse in preorder the children (subtrees). In other words in a preorder traversal, a node is visited before its descendants. A typical application of such a traversal is the printing of a structured document. The algorithm for the preorder traversal of a general tree is given in Figure 19.14 where we first visit the root, then traverse in inorderall the children of the root node. Figure 19.15 shows the example for the Preorder traversal of a general tree.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

In this traversal preorder(Become Rich)<\/em> we start at the root node Become Rich<\/em>, where we first visit this node, so Become Rich<\/em><\/strong>is thefirst node to be visited. Next we need to preorder traverse its Left subtree. So we call preorder(Motivations).<\/em>Here again we need to first visit the root node of this Left Subtree, so the second node to be visited is Motivations<\/em><\/strong>.<\/em>Next we need to preorder traverse left subtree of Motivations<\/em>. So we call preorder(Enjoy Life).<\/em>Here again we need to first visit the root node of this Left Subtree, so the third node to be visited isEnjoy Life<\/em><\/strong>.<\/em>At this point we see that Enjoy Life<\/em>has no children and hence we have completed the call preorder(Enjoy Life).<\/em>Therefore we go to the next child of preorder(Motivations)<\/em>and call preorder(Help Poor Friends).<\/em>Again here we first visit the node, so the fourth node to be visited is Help Poor Friends<\/em><\/strong>.<\/em>The process continues by traversing the other children of Become Rich<\/em>and the nodes as visited in the order shown in Figure 19.15.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n\u00a0<\/strong>\r\n\r\n19.8.3 Postorder Traversal<\/strong>\r\n\r\n \r\n\r\nIn postorder traversal we first traverse in postorder the children (subtrees) of the root before visiting the root. In other words, in a postorder traversal, a node is visited after its descendants. The organization of files in a directory and its subdirectories for accessing is a typical application of this type of traversal. The algorithm for postorder traversal of the general tree is given in Figure 19.16 where we first visit the root, then traverse in postorder all the children of the root node. Figure 19.17 shows the example for the postorder traversal of a general tree.<\/span>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n

In the example we see that all children of a node are visited before the root is visited. Considering the subtree homeworks\/, the node is visited after its children h1c.doc and h1nc.dov have been visited.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n19.9 Problems with General Trees and Solutions<\/strong>\r\n\r\n \r\n

The use of general trees is not very convenient and its implementation is not very efficient. One problem associated with general trees is that the number of references needed for each node must be equal to the maximum that will be used in the tree in some implementations and hence varies as the maximum number of children of a general tree changes. Moreover, most of the algorithms for searching, traversing, adding and deleting nodes havetodeal with the fact where there are not just two possibilities for any node but multiple possibilities. This makes the algorithms more\u00a0complex. However there are situations that some problems naturally map to general trees. The solution to handling general trees is to convert these general trees to binary trees. In this way the algorithms that are used for binary tree processing can be used with only minor modifications.<\/span><\/p>\r\n \r\n

19.10 Converting a General Tree to a Binary Tree<\/strong><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Now we will discuss the conversion of a general tree to a binary tree. The steps for this conversion are given below:<\/p>\r\n \r\n\r\n1. Use the root of the general tree as the root of the binary tree.\r\n\r\n2.Determine the first child of the root. This is the leftmost node in the general tree at the next level.\r\n\r\n3.Insert this node. The child reference of the parent node refers to this node.\r\n

4.Continue finding the first child of each parent node and insert it below the parent node with the child reference of the parent to this node.<\/p>\r\n

5.When no more first children exist in the path just used, move back to the parent of the previous node processed and repeat the above process that is we need to determine the first sibling of the last node encountered.<\/p>\r\n6. Complete the tree for all nodes.\r\n

7. For completing the tree, the sibling next to the first child is made its right child and its sibling becomes its right child and so on until all siblings are accounted for.<\/p>\r\n \r\n

We will illustrate these steps using an example. Figure 19.18 (a-g) shows steps in the conversion of general tree to binary tree. Figure 19.18 (a) shows a general tree. As per step 1 given in the conversion process A, the root of the general tree is also the root of the binary tree and as per step 2 & 3 the first child of A that is B is the left child of A (Figure 19.18 (b)). Again as per step 4 the first child of B that is K is the left child of B (Figure 19.18 (c)). Now we have exhausted the first children in the path A-B-K so we go to step 6 where we go to the last node processed K and see if it has other children. In this example K has no other children and neither does B. So we go back to A and start processing other children of A. Now C, the sibling of B becomes the right child of B, and C\u2019s right sibling D becomes it\u2019s right child (Figure 19.18 (d)). Now we process node C, it\u2019s first child H becomes C\u2019s left child, while H\u2019s sibling I becomes it\u2019s right child and I\u2019s sibling becomes it\u2019s right child (Figure 19.18 (e)). Now Now we process node D, it\u2019s first child E becomes D\u2019s left child, while E\u2019s sibling F becomes it\u2019s right child. F\u2019s first child G becomes it\u2019sleft child (Figure 19.18 (f)). Now all nodes of the general tree have been processed and the binary tree corresponding to the general tree has been obtained.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\nSummary<\/strong>\r\n\r\n \r\n\r\n<\/div>\r\n
\r\n\r\n\u00a0 \u00a0 \u2022 Explained the concept of Trees\r\n\r\n\u2022 Discussed General Trees with some examples\r\n\r\n\u2022 Described some representations of General Trees\r\n\r\n\u2022 Explained the different tree traversals\r\n\r\n\u2022 Outlined the conversion of General Trees to Binary Trees<\/span>\r\n\r\n<\/div>\r\n\r\n\r\n\r\n
you can view video on Tree ADT -I<\/strong><\/td>\r\n\"\"<\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"","rendered":"
\"epgp<\/a>
\n<\/span><\/div>\n
\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of an important Linear ADTs. In this module we will discuss Trees – an important hierarchical data structure.<\/p>\n

 <\/p>\n

Learning Objectives<\/strong><\/p>\n

 <\/p>\n

The learning objectives of the module are as follows:<\/p>\n

 <\/p>\n

\u2022 To explain the concept of Trees<\/p>\n

\u2022 To discuss General Trees with some examples<\/p>\n

\u2022 To describe the representations of General Trees<\/p>\n

\u2022 To explain the different tree traversals<\/p>\n

\u2022 To discuss the conversion of General Trees to Binary Trees<\/p>\n

 <\/p>\n

19.1 Introduction<\/strong><\/p>\n

 <\/p>\n

So far in the previous modules we have discussed linear data structures such as lists, stacks and queues. We also have other types of data structures which are non-linear, for example trees and graphs. Trees are hierarchical data structures. Trees are used for applications such as sorting, searching, expression evaluation, etc. Trees are especially well suited to recursive algorithm implementations.<\/p>\n

 <\/p>\n

19.1.1 What are Trees?<\/strong><\/p>\n

 <\/p>\n

A tree consists of a specially designated node called the root and zero or more sub-trees. A tree can also be empty containing no nodes. Figure 19.1 shows an example<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n<\/div>\n

\n

of a tree where A is the root of the tree, B and F are internal nodes that is they have children and C,D,E,G, H and I are all leaf nodes (that is they have no children.<\/p>\n

 <\/p>\n

19.1.2 Trees -Terminology<\/strong><\/p>\n

 <\/p>\n

Generally trees can be used to represent relationships. Let us look at some terminologies associated with trees. Trees are hierarchical in nature and \u201cParent-child\u201d <\/strong>relationship exists between nodes in a tree. This concept can be generalized as ancestor and descendant<\/strong> relations. Lines between the nodes are called edges. Ancestors <\/strong>of a node are it\u2019s parent, grandparent, great-grandparent, etc. Similarly descendant <\/strong>of a node are it\u2019s child, grandchild, great-grandchild, etc. A sub-tree <\/strong>in a tree is any node in the tree together with all of its descendants. Depth<\/strong> of a node is the number of ancestors it has. Height<\/strong> of a tree is the maximum depth of any of it\u2019s node. Degree<\/strong> of a node is the number of its children the node has. On the other hand the degree<\/strong> of a tree is the maximum degree of it\u2019s nodes.<\/p>\n

 <\/p>\n

Let us consider the example given in Figure 19.2, the root<\/strong> is the node without a parent (A), siblings<\/strong> are nodes that share the same parent, example are nodes E and F that share the same parent B. Internal nodes<\/strong> are nodes with at least one child (example – A, B, C, F), while external node<\/strong> (or leaf nodes ) are nodes without children (example -E, I, J, K, G, H, D). A subtree<\/strong> is a tree consisting of a node and its descendants (example subtree rooted at C and having descendants G and H). Each node in a tree may have a subtree. In other words, the subtree of each node includes one of its children and all descendants of that child (Figure 19.3).<\/p>\n

 <\/p>\n

\"\"\u00a0<\/strong><\/p>\n

To summarize we can divide the vertices of a tree into three categories: the <\/span>root<\/em>, <\/span>leaves <\/em>and the<\/span> internal nodes<\/em>. The root has no parent and can have zero or more children, the leaf has one parent and no children while the internal nodes has parent and one or more children.<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

19.2\u00a0 Kinds of Trees<\/strong><\/p>\n

 <\/p>\n

One of the classifications of trees is based on the maximum number of children a tree are allowed to have. General trees are trees where a node can have any number of children. N-ary trees are trees where a node can have a maximum of N children. Binary trees are 2-ary trees where a node can have a maximum of two children.<\/p>\n

 <\/p>\n

19.2.1 General Tree<\/strong><\/p>\n

 <\/p>\n

The general tree has a specially designated node r, called the root of the tree and sets that are general trees, called subtrees of r. Here there is no restriction on the number of subtrees a node can have.<\/p>\n

 <\/p>\n

19.2.2 N-ary Tree<\/strong><\/p>\n

 <\/p>\n

The n -ary tree can be defined as a set T of nodes that is either empty or partitioned into disjoint subsets. It has a specially designated node r, called the root of the tree and n possibly empty sets that are n-ary subtrees of r.<\/p>\n

 <\/p>\n

19.2.3 Binary Tree<\/strong><\/p>\n

 <\/p>\n

The binary tree can be defined as a set T of nodes that is either empty or partitioned into two disjoint subsets. It has a specially designated node r, called the root of the tree and two possibly empty subtrees called as left and right subtrees of r.<\/p>\n

 <\/p>\n

19.3\u00a0 Representation of Trees<\/strong><\/p>\n

 <\/p>\n

The concept of a tree is verycommon as well as very important. Each node in the tree has only have only one parent, and a node has children. Of course leaf nodeshave no children and the root node which is at the top has no parent. We need to look at effective data structures to represent trees.<\/p>\n

 <\/p>\n

19.4 Importance of Trees<\/strong><\/p>\n

 <\/p>\n

Trees are important since execution and processing for many applications can be expressed as a tree, e.g. method calls as a program runs, searching a maze or puzzle, etc.. Trees are important for cognition and computation in areas such as computer science, language processing (by humans or computers) for example parse trees and knowledge representation (or modeling of the \u201creal world\u201d) for example family trees; biological taxonomy (kingdom, phylum, \u2026, species); etc. Let us now look at some examples of trees.<\/p>\n<\/div>\n

\"\"<\/p>\n

\n

Figure 19.4 shows an example of representing a file system organization of a computing system using trees. We can see that the file system is naturally represented using the hierarchical tree data structure. This example shows a 3-ary tree. Figure 19.5 shows the representation of semi-structured documents using trees.In both HTML and XML elements are identified in a document by their starttag<\/strong> and endtag<\/strong>. Complex elements are constructed from other elements hierarchically, whereas simple elements contain data values. We can see the correspondence between the HTML\/XML textual representation and the tree structure. HTML elements are represented by tree nodes and organized into a hierarchy. In the tree representation, internal nodes represent complex elements, whereas leaf nodes represent simple elements.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

In this representation, tags are associated with the edges which represent the schema names that is the names of attributes, object types (or entity types or classes), and relationships. The internal nodes represent individual objects or composite attributesand the leaf nodes represent actual data values of simple (atomic) attributes.<\/p>\n

 <\/p>\n

19.5 Recursive Data Structure<\/strong><\/p>\n

 <\/p>\n

In general a recursive data structure is a data structure that contains a pointer or reference to an instance of itself. The tree data structure can be expressed as a recursive data structure. Figure 19.6 shows the recursive definition of the binary tree.Recursion is a <\/span>natural<\/em> way to express many algorithms.For recursive data-structures, recursive algorithms are a natural choice.<\/span><\/p>\n<\/div>\n\n\n\n
public class TreeNode<T><\/strong><\/p>\n

 <\/p>\n

{<\/strong><\/p>\n

T\u00a0 <\/strong>nodeItem; TreeNode<T> left, right; TreeNode<T> parent;<\/strong><\/p>\n

\u2026<\/strong><\/p>\n

}<\/strong><\/p>\n

\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Figure 19.6Tree as a Recursive Data Structure<\/strong><\/p>\n

\n

 <\/p>\n

19.6 Tree ADT<\/strong><\/p>\n

 <\/p>\n

In our discussion on trees as an ADT we use positions to abstract nodes. Generic functions include:<\/p>\n

 <\/p>\n

\u2022 integersize<\/strong>() \u2013 This function gives the number of nodes in the tree.<\/p>\n

\u2022 booleanisEmpty<\/strong>() \u2013 This Boolean function signals true if the tree is empty<\/p>\n

\u2022 Iterator elements<\/strong>() \u2013 This function outputs all the elements of the tree in an iterative manner<\/p>\n

\u2022 Accessor functions: Some of the important functions to access the tree are:<\/p>\n

\u2013\u00a0 position root<\/strong>() \u2013 This function outputs the position of the root<\/p>\n

\u2013 position parent<\/strong>(p) – This function outputs the position of the parent of a node<\/p>\n

\u2013 positionIteratorchildren<\/strong>(p) – This function outputs the positions of all the children of a node<\/p>\n

\u2022 Query functions: These are some of the functions to query the tree data structure<\/p>\n

\u2013 booleanisInternal<\/strong>(p) \u2013 This Boolean function finds if a given node is an internal node.<\/p>\n

\u2013 booleanisExternal<\/strong>(p) -This Boolean function finds if a given node is an external or leaf node.<\/p>\n

\u00a0 \u2013 boolean<\/span>isRoot<\/strong>(p) – This Boolean function finds if a given node is a root node.<\/span><\/p>\n

\u2022 Update functions: Some of the functions to update the tree are given below. Additional update functions may be defined by data structures implementing the Tree ADT<\/span><\/p>\n

\u2013 <\/span>swapElements<\/strong>(p, q) \u2013 This functions swaps two elements of the tree given the tree T.<\/span><\/p>\n

\u2013 <\/span>replaceElement<\/strong>(p, e) – This functions replaces an element of the tree given the tree T.<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

19.7 Representation of the Tree<\/strong><\/p>\n

 <\/p>\n

Before we discuss the details of the representation of the tree, let look at intuitive representation of Tree node. The tree can be represented by a list (Figure 19.7<\/strong>).<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

Every tree node in general, how many ever children it can have contains data which stores useful information and pointers to its children and these nodes can be used\u00a0for the representation of the general tree (Figure 19.8 (a) and 19.8 (b)). However here we do not know the number of link fields needed since the number of children of each node is unknown.<\/span><\/p>\n<\/div>\n

\n

\"\"<\/p>\n

 <\/p>\n

Therefore the node of the general tree can be represented by a node storing the data, pointer to the parent node and information about where the sequence of children nodes are stored (Figure 19.9 (a)). Now let us look at different ways in which general trees can be represented.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

19.7.1 General Trees \u2013Implementation<\/strong><\/p>\n

 <\/p>\n

One way to implement a general tree is to use a node whose structure uses a node consisting of the data element, pointer to the parent node and a pointer to the sequence of children nodes (Figure 19.9). In another link representation, specifically, a node left pointer points to its left-most child and it\u2019s right pointer points to a linked list of nodes that are it\u2019s siblings. Figure 19.10 shows the Left Child, Right Sibling Representationwhere we put the left child node to the node\u2019s left link and put the sibling to the node\u2019s right link.<\/p>\n<\/div>\n

\"\"<\/p>\n

\n

 <\/p>\n

19.7.2 Parent Pointer Implementation<\/strong><\/p>\n

 <\/p>\n

Figure 19.11 shows the parent pointer representation where we have an array where each element of the array stores the label of the node and the index to it\u2019s parent. For example the node C is stored in location of the array indexed 3, and its parent\u2019s index 1 which is the location of C\u2019s parent A.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

19.8 Tree Traversal<\/strong><\/p>\n

 <\/p>\n

An important operation associated with trees is traversal of a tree. A traversal visits the nodes of a tree in a systematic manner. Depending on the order in which the nodes are traversed, there are three main types of traversal namely inorder, preorder and postorder traversals. These traversals can be defined recursively as given below:<\/p>\n

 <\/p>\n

19.8.1 Inorder Traversal<\/strong><\/p>\n

 <\/p>\n

In inorder traversal, the left most subtree of a node is visited in inorder, then the node is visited and then all the other subtrees are visited inorder. It is recursively as follows: Traverse in inorder the left subtree, visit the root and finally traverse in inorder the right subtree in case the tree has only two children. The algorithm for the inorder traversal of a general tree is given in Figure 19.12 where we traverse in inorder the left subtree, visit the root and finally traverse in inorder all children other than the leftmost subtree. Figure 19.13 shows the example for the Inorder traversal of a general tree.<\/span><\/p>\n<\/div>\n

\n

\"\"<\/p>\n

 <\/p>\n

In this traversalinorder(Become Rich)<\/em> we start at the root nodeBecome Rich<\/em>, but we need to inorder traverse its Left subtree. So we call inorder(Motivations).<\/em>Here again we need to inorder traverse its Left subtree. So we call inorder(Enjoy Life).<\/em> At this point Left subtree is empty so we go to the next step of the Inorder Traversal with Enjoy Life<\/em>which is visit node, so we visit this node Enjoy Life<\/strong>. <\/em>Now this node has no Right subtrees and hence this call is completed. This essentially means that the Inorder Left subtree call by inorder(Motivations)<\/em>is completed, so we visit this node, therefore the second node to be visited is Motivations.<\/em><\/strong>Now we go to the third step in the call inorder(Motivations)<\/em>which is inorder traversal of its children except leftsubtree. Therefore we call inorder(Help Poor Friends).<\/em> Since this node has no children, only step 2 takes place that is Help Poor Friends<\/em><\/strong> is the third node to be visited. Now we have completed the first step of inorder(Become Rich)<\/em>and so we go step to and Become Rich<\/em><\/strong>is the fourth node to be visited. The process continues by traversing the other children of Become Rich<\/em>and the nodes as visited in the order shown in Figure 19.13.<\/p>\n

 <\/p>\n

\"\"<\/p>\n<\/div>\n

\n

 <\/p>\n

19.8.2 Preorder Traversal<\/strong><\/p>\n

 <\/p>\n

In preorder traversal we first visit the root and then traverse in preorder the children (subtrees). In other words in a preorder traversal, a node is visited before its descendants. A typical application of such a traversal is the printing of a structured document. The algorithm for the preorder traversal of a general tree is given in Figure 19.14 where we first visit the root, then traverse in inorderall the children of the root node. Figure 19.15 shows the example for the Preorder traversal of a general tree.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

In this traversal preorder(Become Rich)<\/em> we start at the root node Become Rich<\/em>, where we first visit this node, so Become Rich<\/em><\/strong>is thefirst node to be visited. Next we need to preorder traverse its Left subtree. So we call preorder(Motivations).<\/em>Here again we need to first visit the root node of this Left Subtree, so the second node to be visited is Motivations<\/em><\/strong>.<\/em>Next we need to preorder traverse left subtree of Motivations<\/em>. So we call preorder(Enjoy Life).<\/em>Here again we need to first visit the root node of this Left Subtree, so the third node to be visited isEnjoy Life<\/em><\/strong>.<\/em>At this point we see that Enjoy Life<\/em>has no children and hence we have completed the call preorder(Enjoy Life).<\/em>Therefore we go to the next child of preorder(Motivations)<\/em>and call preorder(Help Poor Friends).<\/em>Again here we first visit the node, so the fourth node to be visited is Help Poor Friends<\/em><\/strong>.<\/em>The process continues by traversing the other children of Become Rich<\/em>and the nodes as visited in the order shown in Figure 19.15.<\/p>\n

 <\/p>\n

\"\"<\/p>\n<\/div>\n

\u00a0<\/strong><\/p>\n

19.8.3 Postorder Traversal<\/strong><\/p>\n

 <\/p>\n

In postorder traversal we first traverse in postorder the children (subtrees) of the root before visiting the root. In other words, in a postorder traversal, a node is visited after its descendants. The organization of files in a directory and its subdirectories for accessing is a typical application of this type of traversal. The algorithm for postorder traversal of the general tree is given in Figure 19.16 where we first visit the root, then traverse in postorder all the children of the root node. Figure 19.17 shows the example for the postorder traversal of a general tree.<\/span><\/p>\n

\n

\"\"<\/p>\n

 <\/p>\n

In the example we see that all children of a node are visited before the root is visited. Considering the subtree homeworks\/, the node is visited after its children h1c.doc and h1nc.dov have been visited.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

19.9 Problems with General Trees and Solutions<\/strong><\/p>\n

 <\/p>\n

The use of general trees is not very convenient and its implementation is not very efficient. One problem associated with general trees is that the number of references needed for each node must be equal to the maximum that will be used in the tree in some implementations and hence varies as the maximum number of children of a general tree changes. Moreover, most of the algorithms for searching, traversing, adding and deleting nodes havetodeal with the fact where there are not just two possibilities for any node but multiple possibilities. This makes the algorithms more\u00a0complex. However there are situations that some problems naturally map to general trees. The solution to handling general trees is to convert these general trees to binary trees. In this way the algorithms that are used for binary tree processing can be used with only minor modifications.<\/span><\/p>\n

 <\/p>\n

19.10 Converting a General Tree to a Binary Tree<\/strong><\/p>\n<\/div>\n

\n

 <\/p>\n

Now we will discuss the conversion of a general tree to a binary tree. The steps for this conversion are given below:<\/p>\n

 <\/p>\n

1. Use the root of the general tree as the root of the binary tree.<\/p>\n

2.Determine the first child of the root. This is the leftmost node in the general tree at the next level.<\/p>\n

3.Insert this node. The child reference of the parent node refers to this node.<\/p>\n

4.Continue finding the first child of each parent node and insert it below the parent node with the child reference of the parent to this node.<\/p>\n

5.When no more first children exist in the path just used, move back to the parent of the previous node processed and repeat the above process that is we need to determine the first sibling of the last node encountered.<\/p>\n

6. Complete the tree for all nodes.<\/p>\n

7. For completing the tree, the sibling next to the first child is made its right child and its sibling becomes its right child and so on until all siblings are accounted for.<\/p>\n

 <\/p>\n

We will illustrate these steps using an example. Figure 19.18 (a-g) shows steps in the conversion of general tree to binary tree. Figure 19.18 (a) shows a general tree. As per step 1 given in the conversion process A, the root of the general tree is also the root of the binary tree and as per step 2 & 3 the first child of A that is B is the left child of A (Figure 19.18 (b)). Again as per step 4 the first child of B that is K is the left child of B (Figure 19.18 (c)). Now we have exhausted the first children in the path A-B-K so we go to step 6 where we go to the last node processed K and see if it has other children. In this example K has no other children and neither does B. So we go back to A and start processing other children of A. Now C, the sibling of B becomes the right child of B, and C\u2019s right sibling D becomes it\u2019s right child (Figure 19.18 (d)). Now we process node C, it\u2019s first child H becomes C\u2019s left child, while H\u2019s sibling I becomes it\u2019s right child and I\u2019s sibling becomes it\u2019s right child (Figure 19.18 (e)). Now Now we process node D, it\u2019s first child E becomes D\u2019s left child, while E\u2019s sibling F becomes it\u2019s right child. F\u2019s first child G becomes it\u2019sleft child (Figure 19.18 (f)). Now all nodes of the general tree have been processed and the binary tree corresponding to the general tree has been obtained.<\/p>\n<\/div>\n

\"\"<\/p>\n

\n

\"\"<\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

Summary<\/strong><\/p>\n

 <\/p>\n<\/div>\n

\n

\u00a0 \u00a0 \u2022 Explained the concept of Trees<\/p>\n

\u2022 Discussed General Trees with some examples<\/p>\n

\u2022 Described some representations of General Trees<\/p>\n

\u2022 Explained the different tree traversals<\/p>\n

\u2022 Outlined the conversion of General Trees to Binary Trees<\/span><\/p>\n<\/div>\n\n\n\n
you can view video on Tree ADT -I<\/strong><\/td>\n\"\"<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\"\"<\/p>\n

 <\/p>\n

\"\"<\/p>\n","protected":false},"author":3,"menu_order":19,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-v-geetha"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-223","chapter","type-chapter","status-publish","hentry","contributor-dr-t-v-geetha"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/223","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":11,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/223\/revisions"}],"predecessor-version":[{"id":939,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/223\/revisions\/939"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/223\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/media?parent=223"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapter-type?post=223"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/contributor?post=223"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/license?post=223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}