# 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

///////////////////////////////////////////////////////////////////////////
//    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.

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

secondlife/binary_trees/in_order.txt · Last modified: 2017/02/22 18:30 (external edit)

For the copyright, license, warranty and privacy terms for the usage of this website please see the license and privacy pages.