Table of Contents

Description

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

A pre-order traversal prints the root, then the left child and then the right child.

Code

This script was tested and works on OpenSim version 0.7.5!

///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
list wasBinaryTreePreOrder(list BT, string node) {
    string left = wasBinaryTreeLeft(BT, node);
    string right = wasBinaryTreeRight(BT, node);
    if(left == "" && right == "") return [ node];
    if(left == "") return node + wasBinaryTreePreOrder(BT, right);
    if(right == "") return node + wasBinaryTreePreOrder(BT, left);
    return node + wasBinaryTreePreOrder(BT, left) + wasBinaryTreePreOrder(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...

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

A B D E C F 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 wasBinaryTreePreOrder(list BT, string node) {
    string left = wasBinaryTreeLeft(BT, node);
    string right = wasBinaryTreeRight(BT, node);
    if(left == "" && right == "") return [ node];
    if(left == "") return node + wasBinaryTreePreOrder(BT, right);
    if(right == "") return node + wasBinaryTreePreOrder(BT, left);
    return node + wasBinaryTreePreOrder(BT, left) + wasBinaryTreePreOrder(BT, right);
}
 
default {
    state_entry() {
        list BT = ["A", "B", "C", "D", "E", "F", "G"];
        llOwnerSay(llDumpList2String(wasBinaryTreePreOrder(BT, "A"), ","));
    }
}

And the output is:

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

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

Access website using Tor


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