{small lecturenumber - heblocknumber :} Trees with $>$ 2 childrenaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Trees with $>$ 2 childrenaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Trees with $>$ 2 childrenaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Left Child / Right Siblingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Working with General Treeaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} General Trees -- NumNodesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} General Trees -- NumNodesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} General Trees -- NumNodes IIaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tree Operations -- Heightaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} General Trees -- Heightaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} General Trees -- Heightaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} General Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} General Trees -- numLeavesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} General Trees -- numLeavesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing General Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing General Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing General Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing General Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Serializing General Treesaddtocounter {blocknumber}{1}Data Structures and AlgorithmsCS245-2014S-09General TreesDavid GallesDepartment of Computer ScienceUniversity of San Francisco09-0: Trees with > 2 childrenHow can we implement trees with nodes that have > 2children?09-1: Trees with > 2 childrenArray of Chi ldren09-2: Trees with > 2 childrenLinked List of C hildren09-3: Left Child / Right SiblingWe can int egrate the linked lists with the nodesthemselves: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 – NumNodesReturns the number of nodes in a treeNumber 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 – HeightReturns the height of the tree(Length of the path t o the deepest leaf) + 1Height = 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 3Wr ite numLeaves and print09-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 TreesPrint a tree to a file, saving structure informati onFirst Try: Print out nodes, in order that they wouldappear in a PREOR D ER t raversal.Why doesn’t t hi s wor k?AB CD EGFABDEGCF09-15: Serializing Binary TreesPrinting out nodes, in order that they would appearin a PREORDER traversal does not work, becausewe don’t know when we’ve hi t a null pointerStore null pointers, too!AB CD EGFABD//EG///C/F//09-16: Serializing Binary TreesPrinting out nodes, in order that they would appearin a PREORDER traversal does not work, becausewe don’t know when we’ve hi t a null pointerStore null pointers, too!AB CDEGF09-17: Serializing Binary TreesPrinting out nodes, in order that they would appearin a PREORDER traversal does not work, becausewe don’t know when we’ve hi t a null pointerStore null pointers, too!AB CDEGFABD///CEG///F//09-18: Serializing Binary TreesPrinting out nodes, in order that they would appearin a PREORDER traversal does not work, becausewe don’t know when we’ve hi t a null pointerStore null pointers, too!ABDE//G///CF/H///09-19: Serializing Binary TreesPrinting out nodes, in order that they would appearin a PREORDER traversal does not work, becausewe don’t know when we’ve hi t a null pointerStore null pointers, too!ABDE//G///CF/H///AB CDE GFH09-20: