.. _General:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "General";ODSA.SETTINGS.MODULE_LONG_NAME = "General Trees";ODSA.SETTINGS.MODULE_CHAPTER = "Week 14"; ODSA.SETTINGS.BUILD_DATE = "2016-11-29 20:59:56"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012-2013 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer


=============
General Trees
=============

General Trees
-------------

General Trees
~~~~~~~~~~~~~
   .. odsalink:: AV/General/GenTreeCON.css
   .. inlineav:: GenTreeCON dgm
      :align: justify

   .. odsascript:: AV/General/GenTreeCON.js


General Tree ADT
~~~~~~~~~~~~~~~~
   .. codeinclude:: General/GenTree
      :tag: GenTreeADT


General Tree Traversal
~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: GenTreePreTravCON ss
      :long_name: General Tree Preorder Traversal Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/General/GenTreePreTravCON.js


Rep: Lists of Children
~~~~~~~~~~~~~~~~~~~~~~
   .. odsafig:: Images/ChildLst.png
      :width: 500
      :align: center
      :capalign: justify
      :figwidth: 90%
      :alt: The "list of children" implementation for general trees.


Rep: Dynamic Node (Array)
~~~~~~~~~~~~~~~~~~~~~~~~~
   .. odsafig:: Images/GenLkFx.png
      :width: 500
      :align: center
      :capalign: justify
      :figwidth: 90%
      :alt: A dynamic general tree with fixed-size arrays


Rep: Dynamic Node (linked list)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   .. odsafig:: Images/GenLkLk.png
      :width: 500
      :align: center
      :capalign: justify
      :figwidth: 90%
      :alt: A dynamic general tree with linked lists of child pointers


Rep: Lift-Child/Right-Sibling
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   .. odsafig:: Images/FortoBin.png
      :width: 600
      :align: center
      :capalign: justify
      :figwidth: 90%
      :alt: Converting from a forest of general trees to a binary tree

           
Serialization
~~~~~~~~~~~~~
   Serialization is the process of storing an object as a series of
   bytes.

   A sequential tree serialization typically stores the node values as
   they would be enumerated by a preorder traversal, along with
   sufficient information to describe the tree's shape.


Binary tree serialization
~~~~~~~~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/General/SequentialTreeCON.css
   .. inlineav:: SequentialTreeCON ss
      :long_name: First sequential representation Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/General/SequentialTreeCON.js


Alternate serialization
~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: SequentialTreeAltCON ss
      :long_name: Second sequential representation Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/General/SequentialTreeAltCON.js

Bit Vector Serialization
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: SequentialTreeBitsCON ss
      :long_name: Bit vector sequential representation Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/General/SequentialTreeBitsCON.js


General Tree Serialization
~~~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: SequentialGenTreeCON ss
      :long_name: General Tree sequential representation Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/General/SequentialGenTreeCON.js