Array representation of a complete binary tree

xholonWorkbook.xml

<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Mon Mar 13 2023 17:02:16 GMT-0400 (Eastern Daylight Saving Time)-->
<XholonWorkbook>

<Notes><![CDATA[
Xholon
------
Title: Array representation of a complete binary tree
Description: 
Url: http://www.primordion.com/Xholon/gwt/
InternalName: 92b4a281efec66e1f6ead519335fca54
Keywords: 

My Notes
--------
13 March 2023


#TODO
- 

#Data structure for gathering level-based data
{
  0: [A],
  1: [B,C],
  2: [D,E,F]
}

// this code works in Dev Tools
var ds = {
  0: ["A"],
  1: ["B","C"],
  2: ["D","E","F"]
}
console.log(ds);
console.log(ds[0]);
console.log(ds[0][0]);
for (var i = 0; i < 3; i++) {
  console.log(ds[i]);
}

#References
-----------
(1) https://www.manning.com/books/advanced-algorithms-and-data-structures
    Advanced Algorithms and Data Structures,  Marcello La Rocca, May 2021
    Starting on p.24, the author descries how to represent a complete binary tree using an array.

(2) https://www.geeksforgeeks.org/complete-binary-tree/

(3) https://en.wikipedia.org/wiki/Binary_tree
    A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled,
    and all nodes in the last level are as far left as possible.
    It can have between 1 and 2h nodes at the last level h.
    A perfect tree is therefore always complete but a complete tree is not necessarily perfect
    An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed.
    Some authors use the term complete to refer instead to a perfect binary tree as defined above,
    in which case they call this type of tree (with a possibly not filled last level)
    an almost complete binary tree or nearly complete binary tree.
    A complete binary tree can be efficiently represented using an array.

(4) https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html
    A complete binary tree has 2k nodes at every depth k < n and between 2n and 2n+1-1 nodes altogether.
    It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and
    a parent at index i/2, with 1-based indexing. If child index is greater than the number of nodes, the child does not exist.

(5) https://xlinux.nist.gov/dads/
    Dictionary of Algorithms and Data Structures

]]></Notes>  

<_-.XholonClass>
  <PhysicalSystem/>
  <Behaviors/>
  
  <Node/>
  
</_-.XholonClass>

<xholonClassDetails>
  
</xholonClassDetails>

<PhysicalSystem>
  
  <!--
first example from ref[2]; a Complete Binary Tree
as an array, this would be A,B,C,D,E,F
this is the same structure as Figure 2.4 in ref[1]
  -->
  <Node roleName="A" goalarr="A,B,C,D,E,F">
    <Node roleName="B">
      <Node roleName="D"/>
      <Node roleName="E"/>
    </Node>
    <Node roleName="C">
      <Node roleName="F"/>
    </Node>
  </Node>
  
  <!--
another example from ref[2]; a Complete Binary Tree
as an array, this would be A,B,D,E,F,H,I
  -->
  <Node roleName="A" goalarr="A,B,D,E,F,H,I">
    <Node roleName="B">
      <Node roleName="E"/>
      <Node roleName="F"/>
    </Node>
    <Node roleName="D">
      <Node roleName="H"/>
      <Node roleName="I"/>
    </Node>
  </Node>
  
  <!--
example from Figure 2.4 in ref[1]
  -->
  <Node roleName="A" goalarr="A,3,2,4,9,6">
    <Node roleName="3">
      <Node roleName="4"/>
      <Node roleName="9"/>
    </Node>
    <Node roleName="2">
      <Node roleName="6"/>
    </Node>
  </Node>
  
  <Behaviors/>
</PhysicalSystem>

<Nodebehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  var me, dstruct, beh = {
  
    postConfigure: function() {
      me = this.cnode.parent();
      if (me.role() == "A") {
        me.println(me.name() + "  goal  : " + me.goalarr);
        dstruct = {0:[],1:[],2:[]};
        $wnd.xh.root().first().last().append(this.cnode.remove());
      }
      else {
        this.cnode.remove()
      }
    },
  
    act: function() {
      //me.println(me.name());
      this.collectData(me, 0, dstruct);
      //me.print("\n");
      //me.println(JSON.stringify(dstruct));
      var arr = [];
      for (var j = 0; j < 3; j++) {
        arr.push(...dstruct[j]);
      }
      me.println(me.name() + "  result: " + arr);
      for (var k = 0; k < arr.length; k++) {
        this.displayDetails(arr, k);
      }
    },
  
    // correct
    collectData: function(node, level, dstruct) {
      //node.print(node.role() + " ");
      dstruct[level].push(node.role());
      if (node.first() != null) {
        this.collectData(node.first(), level + 1, dstruct);
      }
      if ((node.next() != null) && (node.role() !== "A")) {
        this.collectData(node.next(), level, dstruct);
      }
    },
    
    // display details for a single item in the array
    displayDetails: function(arr, ix) {
      const nthis   = arr[ix];
      const nparent = ix == 0 ? "_" : arr[Math.trunc((ix - 1) / 2)];
      const nleft   = arr[(2 * ix) + 1] || "_";
      const nright  = arr[2 * (ix + 1)] || "_";
      me.println(nthis + " " + nparent + " " + nleft + " " + nright);
    }
  }
  //# sourceURL=Nodebehavior.js
]]></Nodebehavior>

<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="http://www.w3.org/2000/svg">
  <g>
    <title>Block</title>
    <rect id="PhysicalSystem/Node" fill="#98FB98" height="50" width="50" x="25" y="0"/>
    <g>
      <title>Height</title>
      <rect id="PhysicalSystem/Node/Node" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
    </g>
  </g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>

</XholonWorkbook>