Implementation of Trees One way to implement a tree would be to have in each node,besides its data,a pointer to each child of the node. However,since the number of children per node can vary so greatly and is not known in advance,it might be infeasible to make the children direct links in the data structure,because there would be too much wasted space. The solution is simple:Keep the children of each node in a linked list of tree nodes
Implementation of Trees ◼ One way to implement a tree would be to have in each node, besides its data, a pointer to each child of the node. ◼ However, since the number of children per node can vary so greatly and is not known in advance, it might be infeasible to make the children direct links in the data structure, because there would be too much wasted space. ◼ The solution is simple: Keep the children of each node in a linked list of tree nodes
Implementation of Trees struct TreeNode { char Element; TreeNode*FirstChild; TreeNode*NextSibling; )
Implementation of Trees struct TreeNode { char Element; TreeNode* FirstChild; TreeNode* NextSibling; }
Implementation of Trees A I A B C D E F H I H I J K K I Arrows that point downward are FirstChild pointers. Arrows that go left to right are NextSib/ing pointers. Node Ehas both a pointer to a sibling (A)and a pointer to a child (while some nodes have neither
Implementation of Trees A B C D E F G H I J K L A B C D E F G H I J K L ◼Arrows that point downward are FirstChild pointers. ◼Arrows that go left to right are NextSibling pointers. ◼Node E has both a pointer to a sibling (F) and a pointer to a child (I), while some nodes have neither
Implementation of Trees Example:Please give the first child/next sibling representation of the following tree. A B C D E F G H I J K
Implementation of Trees A B C D E H F G I J ◼ Example: Please give the first child/next sibling representation of the following tree. K L
Application of Trees There are many applications for trees.One of the popular uses is the directory structure in many common operating systems. /usr* mark* alex* bi训* course* junk.c prog1.r prog2.r The root of this directory is /usr. ■ The asterisk next to the name indicates that /usr is itself a directory
mark* alex* bill* course* junk.c prog1.r prog2.r /usr* Application of Trees ◼ There are many applications for trees. One of the popular uses is the directory structure in many common operating systems. ◼ The root of this directory is /usr. ◼ The asterisk next to the name indicates that /usr is itself a directory