Traversing Binary Trees

June 27, 2012
Revised: June 02, 2014

Code Baselined: December 03, 2002
Code Revised: June 13, 2012

Synopsis

I must have implemented linked list processing and/or stacks in almost every programming language I have had the opportunity to learn—scripting languages included. In this paper, both recursive and iterative binary tree algorithms are presented in the 4Test scripting language.

Introduction

My first exposure to computer science was in the Data Structures course I took at Monmouth College. The book for the course was The Art of Computer Programming: Volume 1 / Fundamental Algorithms which is sometimes affectionately referred to as Knuth Volume 1. Fortunately for us in the class, the professor skipped Chapter 1, Basic Concepts and went right into Chapter 2, Information Structures. During the course, I wrote all the assigned linked list and binary tree programming projects in IBM 360 Assembler.

Data are stored in singly linked lists as nodes made up of both a datum portion and a link portion. The link portion is a pointer to the next node in the list. The memory locations are not required to be sequential. When a new node is added to the list, the link in the last node is updated with a pointer to the next node in memory. Conversely, when a node is removed from the list, the deleted node or memory is returned to the free list and the link portion of the preceding node is updated with a pointer to the node which succeeded the deleted node—basically a pointer is swapped.

A binary tree is a special type of linked list. Nodes in a binary tree contain a datum portion, as in a singly linked list, but also contain both a left link and a right link. The left and right links are themselves pointers to new linked lists which are branches of the tree. Binary tree data structures are associated with efficient sorting and searching algorithms.

SilkTest Configuration

Whenever I develop scripts in SilkTest I normally create an options file (.opt) which is configured with a reference to an include file (.inc) that in turn contains references to all other include files required to support the 4Test script (.t). The Use Files parameter in the Runtime Options contains the entry Libs.inc as shown in Figure 1. The Libs.inc file contains a use statement for the additional include files: Algorithms.inc and Functions.inc. By using this technique only the Lib.inc file would need to be modified if new include files are added or existing ones deleted.

options_figure1
Figure 1

Libs.inc

// #############################################################
//
// Author: Gerard Sczepura
//
// Description:
//         Library (.inc) file which contains include files used by binary tree script.
//
// Date: 5/28/2012
//
// #############################################################

use "Algorithms.inc";
use "Functions.inc";

The Algorithms

The Algorithms.inc file contains the code for the following binary tree algorithms:

  • Build_BTree
  • Traverse_BTree
  • NestedSet_BTree
  • ComputeDepth_BTree

Build_BTree

Build_BTree is a procedure which inserts nodes in a binary tree. For our purposes, the data structure used to implement the binary tree is an ARRAY[10][3] OF ANYTYPE. The procedure populates the array by reading items from a list and then assigning each item to an array element or node. Assignments are made based on whether the new value is less than or greater than the value in the node being examined. If the new value is less than the value in the examined node, then search the left branch. If the new value is greater than the value in the examined node, then search the right branch. Values are inserted until either the binary tree is full or the list is expended. Duplicates are discarded.

Traverse_BTree

Traverse_BTree is a procedure which performs recursive preorder, inorder or postorder traversals based on an input argument in the procedure call. The following traversal definitions in Table 1 are taken from Knuth Vol. 1, 2nd Edition page 316:

Table 1
Preorder traversal Inorder traversal Postorder traversal
Visit the root Traverse the left subtree Traverse the left subtree
Traverse the left subtree Visit the root Traverse the right subtree
Traverse the right subtree Traverse the right subtree Visit the root

NestedSet_BTree

NestedSet_BTree is a procedure which computes the nested set representation of a binary tree structure. The procedure is an implementation of Algorithm T from Knuth Vol. 1, page 317. For this paper, I converted the iterative algorithm from inorder to preorder and modified it slightly in order to implement the nested set computation.

ComputeDepth_BTree

ComputeDepth_BTree is a function which computes the depth of a binary tree. The depth of a binary tree is commonly defined as “The number of nodes along the longest path from the root node down to the farthest leaf node.” The maximum depth of an empty tree is 0.

Code Listing

// #############################################################
//
// Author: Gerard Sczepura
//
// Description:
//         Algorithms to manipulate binary tree data structures.
//
// Date: 6/13/2012
//
// #############################################################

type BTree is ARRAY[10][3] OF ANYTYPE;

type SearchOrder is enum
{
    Pre,
    In,
    Post
}
const LLINK = 1;
const DATA  = 2;
const RLINK = 3;

const MAXFLDS = 3;
const NOLINK = 0;

const nil = "";

const lParend = "(";
const rParend = ")";

// Build_BTree
//     Create a Binary Tree from a list of input.
//     ------------------------------------------
//     Syntax   Build_BTree (btTree, laInput)
//            
//              btTree      The Binary Tree to create. BTree.
//                             BTree[n][1] = Left Link
//                             BTree[n][2] = Data
//                             BTree[n][3] = Right Link
//              laInput     Input data. LIST OF ANYTYPE
//
void Build_BTree (inout BTree btTree, LIST OF ANYTYPE laInput)
{
    INTEGER iCurrent, iLink;
    INTEGER iAvail = 1;
    
    ANYTYPE aItem;
    
    ResOpenList (">> Procedure::Build_BTree ({btTree}, {laInput})");
    
    for each aItem in laInput
    {
        iCurrent = 1;
        
        while (TRUE)
        {
            if (iAvail > ArraySize (btTree))
            {
                AppError ("Can't insert entry '{aItem}' -- B-Tree is Full!");
                break;
            }
            if (aItem == btTree[iCurrent][DATA])
            {
                LogWarning ("Warning: Duplicate entry '{aItem}' -- Item Not Inserted.");
                break;
            }
            if (aItem < btTree[iCurrent][DATA])
            {
                iLink = LLINK;
            }
            else
            {
                iLink = RLINK;
            }
            if (btTree[iCurrent][iLink] == NOLINK)
            {
                if (iCurrent != iAvail)
                {
                    btTree[iCurrent][iLink] = iAvail;
                }
                btTree[iAvail][DATA] = aItem;
                ++iAvail;
                break;
            }
            else
            {
                iCurrent = btTree[iCurrent][iLink];
            }
        }
    }
    Print ("<< Procedure::Build_BTree ({btTree}, {laInput})");
    ResCloseList ();

// Traverse_BTree
//     Recursive Binary Tree traversal.
//     Returns the binary tree values in pre/in/post order.
//     --------------------------------------------
//     Syntax   Traverse_BTree (btTree, iNode, sValues, ORDER)
//            
//              btTree      Binary Tree structure. BTree.
//              iNode       Node to traverse. INTEGER.
//              sValues     Values in traversal order. STRING
//              ORDER       Traversal order. SearchOrder.
//
void Traverse_BTree (BTree btTree, INTEGER iNode, inout STRING sValues, SearchOrder Order)
{
    INTEGER iNext;
    
    ResOpenList (">> Procedure::Traverse_BTree ({btTree}, {iNode}, {sValues}, {Order})");
    
    if btTree[iNode][DATA] == nil
    {
        sValues = nil;
        return;
    }
    switch Order
    {
        case Pre:
            sValues = sValues + " " + btTree[iNode][DATA];
            if btTree[iNode][LLINK] != NOLINK
            {
                iNext = btTree[iNode][LLINK];
                Traverse_BTree (btTree, iNext, sValues, Order);
            }
            if btTree[iNode][RLINK] != NOLINK
            {
                iNext = btTree[iNode][RLINK];
                Traverse_BTree (btTree, iNext, sValues, Order);
            }
        case In:
            if btTree[iNode][LLINK] != NOLINK
            {
                iNext = btTree[iNode][LLINK];
                Traverse_BTree (btTree, iNext, sValues, Order);
            }
            sValues = sValues + " " + btTree[iNode][DATA];
            if btTree[iNode][RLINK] != NOLINK
            {
                iNext = btTree[iNode][RLINK];
                Traverse_BTree (btTree, iNext, sValues, Order);
            }
        case Post:
            if btTree[iNode][LLINK] != NOLINK
            {
                iNext = btTree[iNode][LLINK];
                Traverse_BTree (btTree, iNext, sValues, Order);
            }
            if btTree[iNode][RLINK] != NOLINK
            {
                iNext = btTree[iNode][RLINK];
                Traverse_BTree (btTree, iNext, sValues, Order);
            }
            sValues = sValues + " " + btTree[iNode][DATA];
    }
    Print ("<< Procedure::Traverse_BTree ({btTree}, {iNode}, {sValues}, {Order})");
    ResCloseList ();
    
    return;

// NestedSet_BTree
//     Computes the binary tree as a nested set.
//        Ref. Knuth Vol 1, 2nd edition, page 309.
//     Algorithm from Knuth Vol. 1, 2nd edition, page 317.
//        Knuth's Algorithm T modified from inorder to preorder.
//     --------------------------------------------
//     Syntax   NestedSet_BTree (BTree btTree, inout STRING sParends)
//            
//              btTree      Binary Tree structure. BTree.
//              sParends    Nested Set representation. STRING.
//

void NestedSet_BTree (BTree btTree, inout STRING sParends)
{
    ARRAY[10] OF INTEGER A;   //stack
    
    INTEGER P, T;
    INTEGER i;
    
    BOOLEAN bRL;   //indicates RLink traversal
    
    ResOpenList (">> Procedure::NestedSet_BTree ({btTree}, {sParends})") ;
    
    T = 1;
    P = T;
    i = 0;
    bRL = false;
    
    while (TRUE)
    {
        if P != 0
        {
            sParends = sParends + lParend;
            sParends = sParends + btTree[P][DATA];
            A[++i] = P;   //push value on the stack
            P = btTree[P][LLINK];
        }
        else
        {
            if i == 0
            {
                break;
            }
            else
            {
                if bRL
                {
                    sParends = sParends + rParend;
                    bRL = false;
                }
                P = A[i];   //pop the stack
                --i;
            }
            P = btTree[P][RLINK];
            bRL = true;
        }
    }
    sParends = sParends + rParend;
    
    Print ("<< Procedure::NestedSet_BTree ({btTree}, {sParends})");
    ResCloseList ();
    
    return;

// ComputeDepth_BTree
//     Computes the depth of a binary tree.
//     Based on NestedParends_BTree procedure.
//     --------------------------------------------
//     Syntax   iDepth = ComputeDepth_BTree (BTree btTree)
//            
//              btTree      Binary Tree structure. BTree.
//              iDepth      Computed binary tree depth. INTEGER.
//
integer ComputeDepth_BTree (BTree btTree)
{
    ARRAY[10] OF INTEGER A;   //stack
    
    INTEGER P, T;
    INTEGER i;
    INTEGER iDepth, iCount;
    
    BOOLEAN bRL;   //indicates RLink traversal
    
    ResOpenList (">> Function::ComputeDepth_BTree ({btTree})") ;
    
    T = 1;
    P = T;
    i = 0;
    bRL = false;
    
    iDepth = 0;
    iCount = 0;
    
    if btTree[P][DATA] == nil   //empty tree?
    {
        return (iDepth);
    }
    while (TRUE)
    {
        if P != 0
        {
            A[++i] = P;   //push value on the stack
            P = btTree[P][LLINK];
            ++iCount;
            if iCount > iDepth
            {
                iDepth = iCount;
            }
        }
        else
        {
            if i == 0
            {
                break;
            }
            else
            {
                if bRL
                {
                    bRL = false;
                    --iCount;
                }
                P = A[i];   //pop the stack
                --i;
            }
            P = btTree[P][RLINK];
            bRL = true;
        }
    }
    Print ("<< Function::ComputeDepth_BTree ({btTree})");
    ResCloseList ();
    
    return (iDepth);
}

Supporting Functions & Procedures

The Functions.inc file contains the code for the functions and procedures:

  • ConvertListToCSV
  • ConvertCSVToList
  • Initialize_BTree
  • Print_BTree
  • Save_BTree
  • Load_BTree

ConvertListToCSV

ConvertListToCSV is a function which converts the binary tree to CSV format. This function is called by Save_BTree.

ConvertCSVToList

ConvertCSVToList is a function which converts the contents of a CSV file to a List. This function is called by Load_BTree.

Initialize_BTree

Initialize_BTree is a procedure which initializes the array representing the binary tree.

Print_BTree

Print_BTree is a procedure which dumps out the contents of the array representing the binary tree.

Save_BTree

Save_BTree is a procedure which writes the binary tree to a file in CSV format.

Load_BTree

Load_BTree is a procedure which retrieves the binary tree from a CSV file into a List.

Code Listing

// #############################################################
//
// Author: Gerard Sczepura
//
// Description:
//         Miscellaneous binary tree support functions.
//
// Date: 6/13/2012
//
// #############################################################

STRING ConvertListToCSV (LIST OF ANYTYPE laNode)
{
    ANYTYPE aStr;
    
    STRING sNew = " ";
    
    ResOpenList (">> Function::ConvertListToCSV ({laNode})");
    
    for each aStr in laNode
    {
        sNew = Stuff (sNew, Len (sNew), 0, "{aStr},");
    }
    sNew = RTrim (sNew);
    sNew = SubStr (sNew, 1, Len (sNew) - 1);
    
    Print ("<< Function::ConvertListToCSV");
    ResCloseList ();
    
    return (sNew);
}

LIST OF ANYTYPE ConvertCSVToList (STRING sCSV, INTEGER iFields)
{
    INTEGER i = 0;
    
    STRING sPrevious = " ";
    STRING sField;
    
    INTEGER iLink;
    
    LIST OF ANYTYPE laNode;
    
    ResOpenList (">> Function::ConvertCSVToList ({sCSV}, {iFields})");
    
    for (i = 1; i <= iFields; i++)
    {
        if i == 2
        {
            sField = GetField (sCSV, ",", i);
            ListAppend (laNode, sField);
        }
        else
        {
            iLink = Val(GetField (sCSV, ",", i));
            ListAppend (laNode, iLink);
        }
    }
    Print ("<< Function::ConvertCSVToList");
    ResCloseList ();
    
    return (laNode);
}

void Initialize_BTree (inout BTree btTree)
{
    INTEGER iRows = 0;
    
    INTEGER i;
    
    ResOpenList (">> Procedure::Initialize_BTree ({btTree})");
    
    iRows = ArraySize (btTree, 1);
    
    for (i = 1; i < iRows + 1; ++i)
    {
        btTree[i] [LLINK] = 0;
        btTree[i] [DATA]  = nil;
        btTree[i] [RLINK] = 0;
    }
    Print ("<< Procedure::Initialize_BTree");
    ResCloseList ();
}

void Print_BTree (BTree btTree)
{
    INTEGER i;
    
    ResOpenList (">> Procedure::Print_BTree ({btTree})");
    
    for (i = 1; i <= ArraySize (btTree); i++)
    {
        Print (btTree[i]);
    }
    Print ("<< Procedure::Print_BTree");
    ResCloseList ();
}

void Save_BTree (STRING sFileSpec, BTree btTree)
{
    HFILE hFile;
    
    INTEGER i;
    
    ResOpenList (">> Procedure::Save_BTree ({sFileSpec}, {btTree})");
    
    hFile = FileOpen (sFileSpec, FM_WRITE);
    
    for (i = 1; i <= ArraySize (btTree); i++)
    {
        FileWriteLine (hFile, ConvertListToCSV (btTree[i]));
    }
    FileClose (hFile);
    
    Print ("<< Procedure::Save_BTree");
    ResCloseList ();
}

void Load_BTree (STRING sFileSpec, inout BTree btTree)
{
    HFILE hFile;
    
    INTEGER i = 0;
    
    STRING sNode;
    
    LIST OF ANYTYPE laNode;
    
    ResOpenList (">> Procedure::Load_BTree ({sFileSpec}, {btTree})");
    
    hFile = FileOpen (sFileSpec, FM_READ);
    
    while (FileReadLine (hFile, sNode))
    {
        laNode = ConvertCSVToList (sNode, MAXFLDS);
        
        ++i;
        btTree[i][1] = laNode[1];
        btTree[i][2] = laNode[2];
        btTree[i][3] = laNode[3];
    }
    FileClose (hFile);
    
    Print ("<< Procedure::Load_BTree");
    ResCloseList ();
}

The Script

The BTree.t file is the 4Test script which manipulates the binary tree. The script exercises all the previously described procedures and functions.

Code Listing

// #############################################################
//
// Author: Gerard Sczepura
//
// Description:
//         Script which manipulates binary trees.
//
// Date: 6/13/2012
//
// #############################################################

BTree btList;

STRING sResultSet;
STRING sFilePath = "C:\Documents and Settings\Gerry\My Documents\BTree\BTree.txt";

INTEGER i;

SearchOrder Order;

 
LIST OF ANYTYPE laDataItems = 
{
    "Every",
    "good",
    "boy",
    "deserves",
    "favour"
};

main ()
{
    
    Initialize_BTree (btList);
    Build_BTree (btList, laDataItems);
    Print_BTree (btList);
    Save_BTree (sFilePath, btList);
    
    Load_BTree (sFilePath, btList);
    for i = 1 to 3
    {
        switch i
        {
            case 1:
                Order = Pre;
            case 2:
                Order = In;
            case 3:
                Order = Post;
        }
        sResultSet = "";
        Traverse_BTree (btList, 1, sResultSet, Order);
        Print ("Results = " + sResultSet);
        Print ();
    }
    sResultSet = "";
    NestedSet_BTree (btList, sResultSet);
    Print ("Nested Set Results = " + sResultSet);
    Print ();
    
    Print("Depth = " + Str(ComputeDepth_BTree (btList)));
}

The Results

BTree.t script results are displayed below.

Script BTree.t - Passed
Machine: (local)
Started: 07:07:46PM on 13-Jun-2012
Elapsed: 0:00:00
Totals:  0 errors, 0 warnings

 >> Procedure::Initialize_BTree ({<unset>, <unset>, <unset>, <unset>, <unset>, <unset>, <unset>, <unset>, <unset>, <unset>})
    << Procedure::Initialize_BTree

>> Procedure::Build_BTree ({{0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, {Every, good, boy, deserves, favour})
    << Procedure::Build_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, {Every, good, boy, deserves, favour})

>> Procedure::Print_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}})
    {3, Every, 2}
    {5, good, 0}
    {0, boy, 4}
    {0, deserves, 0}
    {0, favour, 0}
    {0, , 0}
    {0, , 0}
    {0, , 0}
    {0, , 0}
    {0, , 0}
    << Procedure::Print_BTree

>> Procedure::Save_BTree (C:\Documents and Settings\Gerry\My Documents\BTree\BTree.txt, {{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}})
    >> Function::ConvertListToCSV ({3, Every, 2})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({5, good, 0})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({0, boy, 4})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({0, deserves, 0})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({0, favour, 0})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({0, , 0})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({0, , 0})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({0, , 0})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({0, , 0})
        << Function::ConvertListToCSV
    >> Function::ConvertListToCSV ({0, , 0})
        << Function::ConvertListToCSV
    << Procedure::Save_BTree

>> Procedure::Load_BTree (C:\Documents and Settings\Gerry\My Documents\BTree\BTree.txt, {{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}})
    >> Function::ConvertCSVToList (3,Every,2, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (5,good,0, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (0,boy,4, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (0,deserves,0, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (0,favour,0, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (0,,0, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (0,,0, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (0,,0, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (0,,0, 3)
        << Function::ConvertCSVToList
    >> Function::ConvertCSVToList (0,,0, 3)
        << Function::ConvertCSVToList
    << Procedure::Load_BTree

>> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 1, , Pre)
    >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 3,  Every, Pre)
        >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 4,  Every boy, Pre)
            << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 4,  Every boy deserves, Pre)
        << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 3,  Every boy deserves, Pre)
    >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 2,  Every boy deserves, Pre)
        >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 5,  Every boy deserves good, Pre)
            << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 5,  Every boy deserves good favour, Pre)
        << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 2,  Every boy deserves good favour, Pre)
    << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 1,  Every boy deserves good favour, Pre)
Results =  Every boy deserves good favour

>> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 1, , In)
    >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 3, , In)
        >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 4,  boy, In)
            << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 4,  boy deserves, In)
        << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 3,  boy deserves, In)
    >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 2,  boy deserves Every, In)
        >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 5,  boy deserves Every, In)
            << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 5,  boy deserves Every favour, In)
        << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 2,  boy deserves Every favour good, In)
    << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 1,  boy deserves Every favour good, In)
Results =  boy deserves Every favour good

 >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 1, , Post)
    >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 3, , Post)
        >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 4, , Post)
            << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 4,  deserves, Post)
        << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 3,  deserves boy, Post)
    >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 2,  deserves boy, Post)
        >> Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 5,  deserves boy, Post)
            << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 5,  deserves boy favour, Post)
        << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 2,  deserves boy favour good, Post)
    << Procedure::Traverse_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, 1,  deserves boy favour good Every, Post)
Results =  deserves boy favour good Every

 >> Procedure::NestedSet_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, )
    << Procedure::NestedSet_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}}, (Every(boy(deserves))(good(favour))))
Nested Set Results = (Every(boy(deserves))(good(favour)))

 >> Function::ComputeDepth_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}})
    << Function::ComputeDepth_BTree ({{3, Every, 2}, {5, good, 0}, {0, boy, 4}, {0, deserves, 0}, {0, favour, 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}, {0, , 0}})
Depth = 3
Digiprove sealCopyright secured by Digiprove © 2020 Gerard Sczepura

Leave a Reply

Your email address will not be published. Required fields are marked *