Last active
August 29, 2015 13:57
-
-
Save kenwebb/9548290 to your computer and use it in GitHub Desktop.
Rosetta Code - Tree traversal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?xml version="1.0" encoding="UTF-8"?> | |
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Fri Mar 14 2014 12:23:36 GMT-0400 (EDT)--> | |
<XholonWorkbook> | |
<Notes><![CDATA[ | |
Xholon | |
------ | |
Title: Rosetta Code - Tree traversal | |
Description: | |
Url: http://www.primordion.com/Xholon/gwt/wb/editwb.html?app=9548290&src=gist | |
InternalName: 9548290 | |
Keywords: | |
My Notes | |
-------- | |
Rosetta Code and Wikipedia both have pages on `Tree traversal`. | |
According to Wikipedia: | |
In computer science, tree traversal (also known as tree search) | |
refers to the process of visiting (examining and/or updating) | |
each node in a tree data structure, exactly once, in a systematic way. | |
Such traversals are classified by the order in which the nodes are visited. | |
The following algorithms are described for a binary tree, | |
but they may be generalized to other trees as well. | |
Here's the Rosetta Code task description, that I'll be using in this XholonWorkbook. | |
Implement a binary tree where each node carries an integer, | |
and implement preoder, inorder, postorder and level-order traversal. | |
Use those traversals to output the following tree: | |
1 | |
/ \ | |
/ \ | |
/ \ | |
2 3 | |
/ \ / | |
4 5 6 | |
/ / \ | |
7 8 9 | |
The correct output should look like this: | |
preorder: 1 2 4 7 5 3 6 8 9 | |
inorder: 7 4 2 5 1 8 6 9 3 | |
postorder: 7 4 5 2 8 9 6 3 1 | |
level-order: 1 2 3 4 5 6 7 8 9 | |
In the pure binary trees discussed on the Wikipedia and Rosetta Code pages, | |
each node has zero, one, or two child nodes. | |
The two possible child nodes are called the `left child node` and the `right child node`. | |
Tree structures are a fundamental part of Xholon. | |
Each Xholon app defines a composite structure hierarchy (CSH), | |
as a binary tree that contains nodes. | |
Each node references an optional `firstChild` and an optional `nextSibling`, | |
so each node references zero, one, or two other nodes. | |
The names `firstChild` and `nextSibling` are taken from the XML and HTML specifications. | |
To easily convert the example binary trees in the Wikipedia and Rosetta Code pages, | |
the tree diagrams must be rotated about 45 degrees counter clockwise. | |
Then it's pretty straight forward to manually construct the equivalent Xholon structure, | |
using the equivalences: | |
binary tree Xholon, XML, HTML | |
---------------- ----------------- | |
left child node --> firstChild | |
right child node --> nextSibling | |
So in the Rosetta Code example, the following nodes are siblings of each other: | |
1 3 | |
2 5 | |
6 9 | |
and the following nodes have a parent firstChild relationship: | |
1 2 | |
2 4 | |
4 7 | |
3 6 | |
6 8 | |
The natural Xholon order, the top-to-bottom order in the classic (clsc) Xholon GUI, is pre-order. | |
This is also the order that nodes are defined in the Composite Structure Hierarchy XML. | |
If I run this workbook, and use the built-in Xholon `<TreeTraversal/>` script on the RosettaCode-tree, | |
I get the following results, which agree with the results on the rosettacode page: | |
`pre-order` tree traversal for node rosettacode Tree traversal:binaryTreeRoot_36 | |
`1`:node_37 `2`:node_38 `4`:node_39 `7`:node_40 `5`:node_41 `3`:node_42 `6`:node_43 `8`:node_44 `9`:node_45 | |
`in-order` tree traversal for node rosettacode Tree traversal:binaryTreeRoot_36 | |
`7`:node_40 `4`:node_39 `2`:node_38 `5`:node_41 `1`:node_37 `8`:node_44 `6`:node_43 `9`:node_45 `3`:node_42 | |
`post-order` tree traversal for node rosettacode Tree traversal:binaryTreeRoot_36 | |
`7`:node_40 `4`:node_39 `5`:node_41 `2`:node_38 `8`:node_44 `9`:node_45 `6`:node_43 `3`:node_42 `1`:node_37 | |
http://rosettacode.org/wiki/Tree_traversal | |
http://en.wikipedia.org/wiki/Tree_traversal | |
http://en.wikipedia.org/wiki/File:Sorted_binary_tree_preorder.svg | |
]]></Notes> | |
<_-.XholonClass> | |
<TreeTraversalSystem/> | |
<BinaryTreeRoot/> | |
<Node/> | |
</_-.XholonClass> | |
<xholonClassDetails> | |
</xholonClassDetails> | |
<TreeTraversalSystem> | |
<!-- Rosetta Code example --> | |
<BinaryTreeRoot roleName="rosettacode Tree traversal"> | |
<Node roleName="1"> | |
<Node roleName="2"> | |
<Node roleName="4"> | |
<Node roleName="7"/> | |
</Node> | |
</Node> | |
<Node roleName="5"/> | |
</Node> | |
<Node roleName="3"> | |
<Node roleName="6"> | |
<Node roleName="8"/> | |
</Node> | |
<Node roleName="9"/> | |
</Node> | |
<!-- | |
Test the built-in Xholon tree traversal methods. | |
Please note: | |
default order is "pre-order" | |
"level-order" is not yet implemented | |
an invalid order such as "help" provides simple help information | |
--> | |
<!-- | |
<TreeTraversal/> | |
<TreeTraversal order="pre-order"/> | |
<TreeTraversal order="in-order"/> | |
<TreeTraversal order="post-order"/> | |
<TreeTraversal order="level-order"/> | |
<TreeTraversal order="help"/> | |
--> | |
</BinaryTreeRoot> | |
<!-- Wikipedia example --> | |
<BinaryTreeRoot roleName="wikipedia Tree traversal"> | |
<Node roleName="F"> | |
<Node roleName="B"> | |
<Node roleName="A"/> | |
</Node> | |
<Node roleName="D"> | |
<Node roleName="C"/> | |
</Node> | |
<Node roleName="E"/> | |
</Node> | |
<Node roleName="G"/> | |
<Node roleName="I"> | |
<Node roleName="H"/> | |
</Node> | |
<!--<TreeTraversal order="pre-order"/>--> | |
</BinaryTreeRoot> | |
</TreeTraversalSystem> | |
<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml, | |
<svg | |
xmlns:dc="http://purl.org/dc/elements/1.1/" | |
xmlns:cc="http://creativecommons.org/ns#" | |
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" | |
xmlns:svg="http://www.w3.org/2000/svg" | |
xmlns="http://www.w3.org/2000/svg" | |
xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" | |
version="1.1" | |
width="336.25092" | |
height="286.6962" | |
id="svg3953"> | |
<!-- adapted from http://en.wikipedia.org/wiki/File:Sorted_binary_tree_preorder.svg --> | |
<defs | |
id="defs3955"> | |
<marker | |
refX="0" | |
refY="0" | |
orient="auto" | |
id="SquareL" | |
style="overflow:visible"> | |
<path | |
d="M -5,-5 -5,5 5,5 5,-5 -5,-5 z" | |
transform="scale(0.8,0.8)" | |
id="path4940" | |
style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none" /> | |
</marker> | |
<marker | |
refX="0" | |
refY="0" | |
orient="auto" | |
id="DistanceStart" | |
style="overflow:visible"> | |
<g | |
id="g2300"> | |
<path | |
d="M 0,0 2,0" | |
id="path2306" | |
style="fill:none;stroke:#ffffff;stroke-width:1.14999998;stroke-linecap:square" /> | |
<path | |
d="M 0,0 13,4 9,0 13,-4 0,0 z" | |
id="path2302" | |
style="fill:#000000;fill-rule:evenodd;stroke:none" /> | |
<path | |
d="M 0,-4 0,40" | |
id="path2304" | |
style="fill:none;stroke:#000000;stroke-width:1;stroke-linecap:square" /> | |
</g> | |
</marker> | |
<marker | |
refX="0" | |
refY="0" | |
orient="auto" | |
id="DotL" | |
style="overflow:visible"> | |
<path | |
d="m -2.5,-1 c 0,2.76 -2.24,5 -5,5 -2.76,0 -5,-2.24 -5,-5 0,-2.76 2.24,-5 5,-5 2.76,0 5,2.24 5,5 z" | |
transform="matrix(0.8,0,0,0.8,5.92,0.8)" | |
id="path4931" | |
style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none;marker-end:none" /> | |
</marker> | |
<marker | |
refX="0" | |
refY="0" | |
orient="auto" | |
id="Arrow2Lend" | |
style="overflow:visible"> | |
<path | |
d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" | |
transform="matrix(-1.1,0,0,-1.1,-1.1,0)" | |
id="path4890" | |
style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" /> | |
</marker> | |
<marker | |
refX="0" | |
refY="0" | |
orient="auto" | |
id="Arrow1Lstart" | |
style="overflow:visible"> | |
<path | |
d="M 0,0 5,-5 -12.5,0 5,5 0,0 z" | |
transform="matrix(0.8,0,0,0.8,10,0)" | |
id="path4869" | |
style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none" /> | |
</marker> | |
<inkscape:path-effect | |
effect="spiro" | |
id="path-effect2940" /> | |
<inkscape:path-effect | |
effect="skeletal" | |
id="path-effect2942" /> | |
</defs> | |
<metadata | |
id="metadata3958"> | |
<rdf:RDF> | |
<cc:Work | |
rdf:about=""> | |
<dc:format>image/svg+xml</dc:format> | |
<dc:type | |
rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> | |
<dc:title></dc:title> | |
</cc:Work> | |
</rdf:RDF> | |
</metadata> | |
<g | |
transform="translate(-240.44597,-48.982663)" | |
id="layer1"> | |
<g | |
transform="matrix(1.0888617,-0.62345404,0.62345404,1.0888617,166.31803,135.83755)" | |
id="graph0" | |
style="font-size:14px;font-family:Times-Roman"> | |
<title | |
id="title5">sorted_binary_tree</title> | |
<g | |
id="node1"> | |
<title | |
id="title8">C</title> | |
<ellipse | |
cx="60" | |
cy="185" | |
rx="18" | |
ry="18" | |
id="ellipse10" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="60" | |
y="190" | |
id="text12" | |
style="text-anchor:middle">C</text> | |
</g> | |
<g | |
id="node2"> | |
<title | |
id="title15">E</title> | |
<ellipse | |
cx="132" | |
cy="185" | |
rx="18" | |
ry="18" | |
id="ellipse17" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="132" | |
y="190" | |
id="text19" | |
style="text-anchor:middle">E</text> | |
</g> | |
<g | |
id="node3"> | |
<title | |
id="title22">H</title> | |
<ellipse | |
cx="204" | |
cy="185" | |
rx="17" | |
ry="18" | |
id="ellipse24" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="204" | |
y="190" | |
id="text26" | |
style="text-anchor:middle">H</text> | |
</g> | |
<g | |
id="node4"> | |
<title | |
id="title29">A</title> | |
<ellipse | |
cx="24" | |
cy="131" | |
rx="17" | |
ry="18" | |
id="ellipse31" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="24" | |
y="136" | |
id="text33" | |
style="text-anchor:middle">A</text> | |
</g> | |
<g | |
id="node5"> | |
<title | |
id="title36">D</title> | |
<ellipse | |
cx="96" | |
cy="131" | |
rx="17" | |
ry="18" | |
id="ellipse38" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="96" | |
y="136" | |
id="text40" | |
style="text-anchor:middle">D</text> | |
</g> | |
<g | |
id="edge6"> | |
<title | |
id="title43">D->C</title> | |
<path | |
d="m 86,147 c -3,4 -7,9 -10,14" | |
id="path45" | |
style="fill:none;stroke:#000000" /> | |
<polygon | |
points="78,164 78,164 70,170 73,160 " | |
id="polygon47" | |
style="fill:#000000;stroke:#000000" /> | |
</g> | |
<g | |
id="edge8"> | |
<title | |
id="title50">D->E</title> | |
<path | |
d="m 106,147 c 3,4 7,9 10,14" | |
id="path52" | |
style="fill:none;stroke:#000000" /> | |
<polygon | |
points="119,160 119,160 122,170 114,164 " | |
id="polygon54" | |
style="fill:#000000;stroke:#000000" /> | |
</g> | |
<g | |
id="node6"> | |
<title | |
id="title57">I</title> | |
<ellipse | |
cx="240" | |
cy="131" | |
rx="18" | |
ry="18" | |
id="ellipse59" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="240" | |
y="136" | |
id="text61" | |
style="text-anchor:middle">I</text> | |
</g> | |
<g | |
id="edge12"> | |
<title | |
id="title64">I->H</title> | |
<path | |
d="m 230,146 c -3,5 -6,10 -10,15" | |
id="path66" | |
style="fill:none;stroke:#000000" /> | |
<polygon | |
points="223,163 223,163 214,169 217,159 " | |
id="polygon68" | |
style="fill:#000000;stroke:#000000" /> | |
</g> | |
<g | |
id="node7"> | |
<title | |
id="title71">B</title> | |
<ellipse | |
cx="60" | |
cy="77" | |
rx="18" | |
ry="18" | |
id="ellipse73" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="60" | |
y="82" | |
id="text75" | |
style="text-anchor:middle">B</text> | |
</g> | |
<g | |
id="edge3"> | |
<title | |
id="title78">B->A</title> | |
<path | |
d="m 50,92 c -3,5 -6,10 -10,15" | |
id="path80" | |
style="fill:none;stroke:#000000" /> | |
<polygon | |
points="43,109 43,109 34,115 37,105 " | |
id="polygon82" | |
style="fill:#000000;stroke:#000000" /> | |
</g> | |
<g | |
id="edge5"> | |
<title | |
id="title85">B->D</title> | |
<path | |
d="m 70,92 c 3,5 6,10 10,15" | |
id="path87" | |
style="fill:none;stroke:#000000" /> | |
<polygon | |
points="83,105 83,105 86,115 77,109 " | |
id="polygon89" | |
style="fill:#000000;stroke:#000000" /> | |
</g> | |
<g | |
id="node8"> | |
<title | |
id="title92">G</title> | |
<ellipse | |
cx="204" | |
cy="77" | |
rx="17" | |
ry="18" | |
id="ellipse94" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="204" | |
y="82" | |
id="text96" | |
style="text-anchor:middle">G</text> | |
</g> | |
<g | |
id="edge11"> | |
<title | |
id="title99">G->I</title> | |
<path | |
d="m 214,93 c 3,4 7,9 10,14" | |
id="path101" | |
style="fill:none;stroke:#000000" /> | |
<polygon | |
points="227,106 227,106 230,116 222,110 " | |
id="polygon103" | |
style="fill:#000000;stroke:#000000" /> | |
</g> | |
<g | |
id="node9"> | |
<title | |
id="title106">F</title> | |
<ellipse | |
cx="132" | |
cy="23" | |
rx="18" | |
ry="18" | |
id="ellipse108" | |
style="fill:#ffffff;stroke:#000000" /> | |
<text | |
x="132" | |
y="28" | |
id="text110" | |
style="text-anchor:middle">F</text> | |
</g> | |
<g | |
id="edge2"> | |
<title | |
id="title113">F->B</title> | |
<path | |
d="M 117,34 C 106,42 94,51 83,60" | |
id="path115" | |
style="fill:none;stroke:#000000" /> | |
<polygon | |
points="85,63 85,63 75,66 81,57 " | |
id="polygon117" | |
style="fill:#000000;stroke:#000000" /> | |
</g> | |
<g | |
id="edge10"> | |
<title | |
id="title120">F->G</title> | |
<path | |
d="m 147,34 c 11,8 23,17 34,26" | |
id="path122" | |
style="fill:none;stroke:#000000" /> | |
<polygon | |
points="183,57 183,57 189,66 179,63 " | |
id="polygon124" | |
style="fill:#000000;stroke:#000000" /> | |
</g> | |
</g> | |
</g> | |
</svg> | |
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient> | |
</XholonWorkbook> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment