Description

This is a function that uses left and right and returns a list containing an in-order traversal of a binary tree BT.

Code

This script was tested and works on OpenSim version 0.7.5!

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
list wasBinaryTreeInOrder(list BT, string node) {
    string left = wasBinaryTreeLeft(BT, node);
    string right = wasBinaryTreeRight(BT, node);
    if(left == "" && right == "") return [node];
    if(left == "") return node + wasBinaryTreeInOrder(BT, right);
    if(right == "") return wasBinaryTreeInOrder(BT, left) + node;
    return wasBinaryTreeInOrder(BT, left) + node + wasBinaryTreeInOrder(BT, right);
}

Testing

Using the binary tree functions, we represent a flattened tree onto an array using the formulas described by the left and right functions.

$\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm, semithick] \tikzstyle{every state}=[fill=red,draw=none,text=white] \node[initial,state] (A) {$A$}; \node[state] (B) [right of=A] {$B$}; \node[state] (C) [right of=B] {$C$}; \node[state] (D) [right of=C] {$D$}; \node[state] (E) [right of=D] {$E$}; \node[state] (F) [right of=E] {$F$}; \node[state] (G) [right of=F] {$G$}; \path (A) edge node {left} (B) (A) edge[out=100,in=100] node {right} (C) (B) edge[out=-100,in=-100] node {left} (D) (B) edge[out=-100,in=-100] node {right} (E) (C) edge[out=100,in=100] node {left} (F) (C) edge[out=100,in=100] node {right} (G); \end{tikzpicture}$

Consider the above nodes to be a list, starting from index 0 and ended with index 6 which could represent a list with 7 elements. This could be, for example, the following list:

list BT = ["A", "B", "C", "D", "E", "F", "G"];

where element A is at index 0, element B is at index 1, and so on…

An in-order traversal means that we print the left-child, the root, then the right-child which means that the result we expect from an in-order traversal for this example is:

D B E A F C G

In order to test, we branch in the necessary functions and create a script:

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
string wasBinaryTreeLeft(list BT, string node) {
    // Left child index: 2*i + 1
    integer i = llListFindList(BT, (list)node);
    if(i == -1) return "";
    return llList2String(BT, 2*i+1);
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
string wasBinaryTreeRight(list BT, string node) {
    // Right child index: 2*i + 2
    integer i = llListFindList(BT, (list)node);
    if(i == -1) return "";
    return llList2String(BT, 2*i+2);
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
string wasBinaryTreeParent(list BT, string node) {
    // Parent child: | \frac{i-1}{2} |
    integer i = llListFindList(BT, (list)node);
    if(i == -1) return "";
    i = (i-1)/2;
    if(i < 0) i *= -1;
    return llList2String(BT, i);
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
list wasBinaryTreeInOrder(list BT, string node) {
    string left = wasBinaryTreeLeft(BT, node);
    string right = wasBinaryTreeRight(BT, node);
    if(left == "" && right == "") return [node];
    if(left == "") return node + wasBinaryTreeInOrder(BT, right);
    if(right == "") return wasBinaryTreeInOrder(BT, left) + node;
    return wasBinaryTreeInOrder(BT, left) + node + wasBinaryTreeInOrder(BT, right);
}
 
default {
    state_entry() {
        list BT = ["A", "B", "C", "D", "E", "F", "G"];
        llOwnerSay(llDumpList2String(wasBinaryTreeInOrder(BT, "A"), ","));
    }
}

And the output is:

[13:23]  Object: D,B,E,A,F,C,G

Table of Contents

Description

Code

Testing