https://pickwiki.org/index.php?action=history&feed=atom&title=TreeTraversalTreeTraversal - Revision history2026-04-28T23:40:46ZRevision history for this page on the wikiMediaWiki 1.43.0https://pickwiki.org/index.php?title=TreeTraversal&diff=2319&oldid=prevConversion script: link fix2015-02-26T23:48:56Z<p>link fix</p>
<p><b>New page</b></p><div>A function to find the ultimate parent of a particular node, assuming that you provide the key, the file, and the field that holds keys to parents. It will return -1 if the tree contains more than one "top" node.<br />
<br />
<pre><br />
FUNCTION A51.ULTIMATE.PARENT( ID, FILENAME, FIELD.NUM )<br />
<br />
X.NODE.ID = ID<br />
<br />
;*OPEN FILENAME TO F.FILE ELSE RETURN -2<br />
<br />
;* Changed after posting to u2-users... seems to work from [[UniBasic]].<br />
IF NOT(FILEINFO(FILENAME,0)) THEN <br />
CRT 'Opening file'<br />
OPEN FILENAME TO F.FILE ELSE RETURN -2 <br />
END ELSE<br />
CRT 'Assigning file handle'<br />
F.FILE = FILENAME <br />
END<br />
<br />
X.PARENT = ''<br />
X.STACK = ''<br />
X.STATUS = '' <br />
<br />
LOOP<br />
CRT 'X.NODE.ID is ':X.NODE.ID<br />
READV X.DATA FROM F.FILE, X.NODE.ID, FIELD.NUM THEN <br />
X.STATUS = 0<br />
END ELSE<br />
X.STATUS = 1<br />
END<br />
IF X.DATA = '' AND X.STATUS = 0 THEN<br />
CRT X.NODE.ID: ' has no parents, keep it'<br />
IF X.PARENT NE '' AND X.PARENT NE X.NODE.ID THEN<br />
CRT 'We already found an ultimate parent, ':X.PARENT<br />
CRT 'and this would be a second one - ERROR'<br />
RETURN -1<br />
END ELSE<br />
CRT 'Setting X.PARENT to ':X.NODE.ID<br />
X.PARENT = X.NODE.ID<br />
END<br />
END ELSE<br />
CRT 'Pushing ':X.DATA:' onto stack'<br />
INS X.DATA BEFORE X.STACK<1,1><br />
END<br />
CRT 'X.STACK is ':X.STACK<br />
X.NODE.ID = X.STACK<1,1><br />
DEL X.STACK<1,1><br />
CRT 'Popping ':X.NODE.ID:' from stack'<br />
WHILE X.NODE.ID DO REPEAT<br />
<br />
RETURN X.PARENT<br />
</pre><br />
<br />
-----<br />
<br />
The companion function which, given a key to an 'ultimate parent', finds all of the children of that node. For any child that has<br />
multiple parents, it looks back up the tree to make sure they all trace to the same ultimate parent that we started with.<br />
<pre><br />
FUNCTION A51.ALL.CHILDREN( ID, FILENAME, CHILD.FIELD.NUM, PARENT.FIELD.NUM )<br />
<br />
DEFFUN A51.ULTIMATE.PARENT( ARG1, FILENAME, FIELD.NUM )<br />
<br />
CRT 'A51.ALL.CHILDREN CALLED'<br />
<br />
X.NODE.ID = ID<br />
;*OPEN FILE.NAME TO F.FILE ELSE RETURN -2<br />
IF NOT(FILEINFO(FILENAME,0)) THEN <br />
CRT 'Opening file'<br />
OPEN FILENAME TO F.FILE ELSE RETURN -2 <br />
END ELSE<br />
CRT 'Assigning file handle'<br />
F.FILE = FILENAME <br />
END<br />
<br />
X.STACK = ''<br />
X.LIST = ''<br />
<br />
LOOP<br />
READ R.DATA FROM F.FILE, X.NODE.ID THEN END<br />
X.DATA = R.DATA<CHILD.FIELD.NUM><br />
CRT 'Direct children of ':X.NODE.ID:' are ':X.DATA <br />
IF X.DATA NE '' AND NOT(STATUS()) THEN <br />
;* Check that this record has only one parent<br />
;* If not, look up the tree to make sure they<br />
;* all have the same ultimate parent<br />
X.COUNT = DCOUNT(R.DATA<CHILD.FIELD.NUM>,@VM)<br />
IF X.COUNT GT 1 THEN<br />
CRT X.NODE.ID:' has multiple parents '<br />
FOR X = 1 TO X.COUNT<br />
X.KEY = R.DATA<CHILD.FIELD.NUM,X><br />
X.PARENT = A51.ULTIMATE.PARENT(X.KEY,F.FILE,PARENT.FIELD.NUM)<br />
IF X.PARENT NE ID THEN<br />
CRT 'Ultimate parent of ':X.KEY:' is ':X.PARENT:' which differs from ':ID<br />
RETURN -1<br />
END<br />
NEXT X<br />
END<br />
<br />
INS X.DATA BEFORE X.LIST<1,1><br />
CRT 'Pushing ':X.DATA:' onto stack'<br />
INS X.DATA BEFORE X.STACK<1,1><br />
END<br />
X.NODE.ID = X.STACK<1,1><br />
DEL X.STACK<1,1><br />
CRT 'Popping ':X.NODE.ID:' from stack'<br />
WHILE X.NODE.ID DO REPEAT<br />
<br />
RETURN X.LIST<br />
</pre></div>Conversion script