CS245-2014S-09 General Trees 109-0: Trees with > 2 childrenHow can we implement trees with nodes that have > 2 children?09-1: Trees with > 2 children• Array of Childr e n09-2: Trees with > 2 children• Linked List of ChildrenCS245-2014S-09 General Trees 209-3: Left Child / Right Sibling• We can integrate the linked lists with the nodes themselves:09-4: Working with General Treeclass Node {private Node leftchild_;private Node rightsib_;private Object element_;Node leftchild() { void setLeftchild(Node leftchild) {return leftchild_; leftchild_ = leftchild;} }Node rightsib() { void setRightsib(Node leftchild) {return rightsib_; rightsib_ = rightsib;} }Node element() { void setElement(Object element) {return element_; element_ = element;} }}09-5: General Trees – NumNodes• Returns the number of nodes in a treeCS245-2014S-09 General Trees 3Number of Nodes = 8 Number of Nodes = 609-6: General Trees – NumNodesint numnodes(Node tree) {int descendants = 0;Node tmp;if (tree == null)return 0;for (tmp = tree.leftchild(); tmp != null;tmp = tmp.rightsib())descendants = descendants + numnodes(tmp);return descendants + 1;}09-7: General Trees – NumNodes IIint numnodes(Node tree) {if (tree == null)return 0;return 1 + numnodes(tree.leftchild())+ numnodes(tree.rightsib());}09-8: Tree Operations – Height• Returns the height of the tree• (Length of the path to the deepest leaf) + 1CS245-2014S-09 General Trees 4Height = 5 Height = 609-9: General Trees – Heightint height(Node tree) {if (tree == null)return 0;int childHeight = 0;for (Node tmp = tree.leftchild(); tmp != null;tmp=tmp.rightsib()){childHeight = MAX(childHeight, height(tmp));}return childHeight + 1;}09-10: General Trees – Heightint height(Node tree) {if (tree == null)return 0;return MAX((1 + height(tree.leftchild())),height(tree.rightsib()));}09-11: General Trees12 3 45 6 7122 3 45 6713458 9Tree 1 Tree 2Tree 3CS245-2014S-09 General Trees 5Write numLeaves and print 09-12: General Trees – numLeavesint numLeaves(Node tree) {if (tree == null)return 0;if (tree.leftchild() == null)return 1 + numLeaves(tree.rightsib());return numLeaves(tree.leftchild()) +numLeaves(tree.rightsib());}09-13: General Trees – numLeavesvoid print(Node tree, int offset) {if (tree != null){for (int i = 0; i < offset; i++)System.out.print("\t");System.out.println(tree.element());print(tree.leftchild(), offset+1);print(tree.rightsib(), offset);}}09-14: Serializing Binary Trees• Print a tree to a file, saving structu re information• First Try: Print out nodes, in order that they would appear in a PREORDER traversal.• Why doesn’t this work?AB CD EGFABDEGCF09-15: Serializing Binary Trees• Printing out nodes, in order that they would appear in a PREORDER traversal does not work, be cause we don’tknow when we’ve hit a null poin ter• Store null p ointers, too!CS245-2014S-09 General Trees 6AB CD EGFABD//EG///C/F//09-16: Serializing Binary Trees• Printing out nodes, in order that they would appear in a PREORDER traversal does not work, be cause we don’tknow when we’ve hit a null poin ter• Store null p ointers, too!AB CDEGF09-17: Serializing Binary Trees• Printing out nodes, in order that they would appear in a PREORDER traversal does not work, be cause we don’tknow when we’ve hit a null poin ter• Store null p ointers, too!AB CDEGFABD///CEG///F//09-18: Serializing Binary Trees• Printing out nodes, in order that they would appear in a PREORDER traversal does not work, be cause we don’tknow when we’ve hit a null poin ter• Store null p ointers, too!ABDE//G///CF/H///09-19: Serializing Binary TreesCS245-2014S-09 General Trees 7• Printing out nodes, in order that they would appear in a PREORDER traversal does not work, be cause we don’tknow when we’ve hit a null poin ter• Store null p ointers, too!ABDE//G///CF/H///AB CDE GFH09-20: Serializing Binary Trees• If we ar e searializing a full binary tree (each node contains exactly 0 or 2 children), we can store a single extrabit for each node 0 for an internal node, 1 for a leaf:ACD GBFEA0B1C0D0E1F1G109-21: Serializing Binary Trees• If we ar e searializing a full binary tree (each node contains exactly 0 or 2 children), we can store a single extrabit for each node 0 for an internal node, 1 for a leaf:ABC DEGF09-22: Serializing Binary Trees• If we ar e searializing a full binary tree (each node contains exactly 0 or 2 children), we can store a single extrabit for each node 0 for an internal node, 1 for a leaf:CS245-2014S-09 General Trees 8ABC DEGFA0B0C1D1E0F1G109-23: Serializing Binary Trees• If we ar e searializing a full binary tree (each node contains exactly 0 or 2 children), we can store a single extrabit for each node 0 for an internal node, 1 for a leaf:A0B0C1D0E1F1G109-24: Serializing Binary Trees• If we ar e searializing a full binary tree (each node contains exactly 0 or 2 children), we can store a single extrabit for each node 0 for an internal node, 1 for a leaf:A0B0C1D0E1F1G1ABDEFGC09-25: Serializing General Trees• Store an “end of children” markerAB DE F ICG H JKABE)F K)))C)DG)H)I)J)))09-26: Serializing General TreesCS245-2014S-09 General Trees 9• Store an “end of children” markerAB D EF ICG H JK09-27: Serializing General Trees• Store an “end of children” markerAB D EF ICG H JKABF K)))CG)H))DI)J))E))09-28: Serializing General Trees• Store an “end of children” markerABDK)))CE)F)GI)J))H)))09-29: Serializing General Trees• Store an “end of children” markerABDK)))CE)F)GI)J))H)))CS245-2014S-09 General Trees 10ABD E FICG