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 Access website using i2p


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