Binary Search Tree

TYPE Node DECLARE leftPointer, rightPointer, data : INTEGER ENDTYPE DECLARE tree : ARRAY[1:9] OF Node DECLARE rootPointer, freePointer : INTEGER CALL InitialiseTree() CALL InsertNode(5) CALL InsertNode(3) CALL InsertNode(6) CALL InsertNode(2) CALL InsertNode(8) CALL InsertNode(4) CALL InsertNode(1) CALL InsertNode(9) CALL InsertNode(7) //populate with random values instead // FOR n ← 1 TO 9 // CALL InsertNode(INT(RAND(9) + 1)) // NEXT n OUTPUT Search(3) OUTPUT Search(2) OUTPUT Search(0) OUTPUT Search(7) OUTPUT RecursiveSearch(3, rootPointer) OUTPUT RecursiveSearch(2, rootPointer) OUTPUT RecursiveSearch(0, rootPointer) OUTPUT RecursiveSearch(7, rootPointer) CALL DisplayNodeArray() OUTPUT "---InOrderTraversal ---" CALL InOrderTraversal(rootPointer) OUTPUT "---PreOrderTraversal ---" CALL PreOrderTraversal(rootPointer) OUTPUT "---PostOrderTraversal ---" CALL PostOrderTraversal(rootPointer) CALL DrawTree() PROCEDURE InitialiseTree() rootPointer ← -1 //empty tree freePointer ← 1 //set start of free list to add new nodes frmo DECLARE index : INTEGER //each node in free list (except last) should point to next node FOR index ← 1 TO LENGTH(tree) - 1 tree[index].leftPointer ← index + 1 NEXT index //last node should point to null pointer tree[LENGTH(tree)].leftPointer ← -1 ENDPROCEDURE PROCEDURE InsertNode(data : INTEGER) DECLARE newNodePointer, currentPointer, previousPointer : INTEGER DECLARE turnedLeft : BOOLEAN //if tree not full IF freePointer <> -1 THEN newNodePointer ← freePointer //get pointer of node to add freePointer ← tree[freePointer].leftPointer //since we initialised the leftPointer as pointing to next node, use this to update freePointer to point to next node //insert new node data - assume it's a leaf node - pointers will be updated in subsequent code if not tree[newNodePointer].data ← data tree[newNodePointer].leftPointer ← -1 tree[newNodePointer].rightPointer ← -1 //if empty IF rootPointer = -1 THEN rootPointer ← newNodePointer //set root node ELSE //find insert position currentPointer ← rootPointer WHILE currentPointer <> -1 DO previousPointer ← currentPointer //store previousPointer - will be used to point to new node if correct position //data less that current node's data, go left IF data < tree[currentPointer].data THEN turnedLeft ← TRUE currentPointer ← tree[currentPointer].leftPointer //go left ELSE turnedLeft ← FALSE currentPointer ← tree[currentPointer].rightPointer //go right ENDIF ENDWHILE //found correct position to insert //update left or right pointer accordingly IF turnedLeft = TRUE THEN tree[previousPointer].leftPointer ← newNodePointer ELSE tree[previousPointer].rightPointer ← newNodePointer ENDIF ENDIF ENDIF ENDPROCEDURE FUNCTION Search(data : INTEGER) RETURNS BOOLEAN DECLARE currentPointer : INTEGER currentPointer ← rootPointer //start searching from root //while valid node WHILE currentPointer <> -1 DO //if found IF data = tree[currentPointer].data THEN RETURN TRUE ELSE //check direction to travel IF data < tree[currentPointer].data THEN currentPointer ← tree[currentPointer].leftPointer ELSE currentPointer ← tree[currentPointer].rightPointer ENDIF ENDIF ENDWHILE //if not found, then value doesn't exist - hence return false RETURN FALSE ENDFUNCTION FUNCTION RecursiveSearch(data : INTEGER, currentPointer : INTEGER) RETURNS BOOLEAN //base case - reached null pointer and not found item - hence return false IF currentPointer = -1 THEN RETURN FALSE ELSE //base case - found item IF data = tree[currentPointer].data THEN RETURN TRUE ELSE //general case - search correct sub-tree IF data < tree[currentPointer].data THEN RETURN RecursiveSearch(data, tree[currentPointer].leftPointer) ELSE RETURN RecursiveSearch(data, tree[currentPointer].rightPointer) ENDIF ENDIF ENDIF ENDFUNCTION //output nodes in ascending order PROCEDURE InOrderTraversal(currentPointer : INTEGER) //prevents empty tree giving an array index out of bounds error IF currentPointer <> -1 THEN //if left pointer doesn't point to leaf node, then traverse IF tree[currentPointer].leftPointer <> -1 THEN CALL InOrderTraversal(tree[currentPointer].leftPointer) ENDIF OUTPUT tree[currentPointer].data //if right pointer doesn't point to leaf node, then traverse IF tree[currentPointer].rightPointer <> -1 THEN CALL InOrderTraversal(tree[currentPointer].rightPointer) ENDIF ENDIF ENDPROCEDURE //outputs nodes in order they were visited PROCEDURE PreOrderTraversal(currentPointer : INTEGER) //prevents empty tree giving an array index out of bounds error IF currentPointer <> -1 THEN OUTPUT tree[currentPointer].data //if left pointer doesn't point to leaf node, then traverse IF tree[currentPointer].leftPointer <> -1 THEN CALL PreOrderTraversal(tree[currentPointer].leftPointer) ENDIF //if right pointer doesn't point to leaf node, then traverse IF tree[currentPointer].rightPointer <> -1 THEN CALL PreOrderTraversal(tree[currentPointer].rightPointer) ENDIF ENDIF ENDPROCEDURE //outputs nodes in order they are fully visited (i.e. both left and right subtrees) PROCEDURE PostOrderTraversal(currentPointer : INTEGER) //prevents empty tree giving an array index out of bounds error IF currentPointer <> -1 THEN //if left pointer doesn't point to leaf node, then traverse IF tree[currentPointer].leftPointer <> -1 THEN CALL PostOrderTraversal(tree[currentPointer].leftPointer) ENDIF //if right pointer doesn't point to leaf node, then traverse IF tree[currentPointer].rightPointer <> -1 THEN CALL PostOrderTraversal(tree[currentPointer].rightPointer) ENDIF OUTPUT tree[currentPointer].data ENDIF ENDPROCEDURE //helped procedure to output array details - for understanding/debugging PROCEDURE DisplayNodeArray() DECLARE index : INTEGER OUTPUT "---DisplayNodeArray --- \n" //left, right, data OUTPUT " L | R | D" FOR index ← 1 TO LENGTH(tree) OUTPUT " ", tree[index].leftPointer, " | ", tree[index].rightPointer, " | ", tree[index].data NEXT index OUTPUT "" ENDPROCEDURE //additional procedures - not required for exam. Just helps visualise the tree :) PROCEDURE DrawTree() CALL CREATECANVAS("tree", 500, 500) CALL DrawNode(rootPointer, 1, 0) ENDPROCEDURE PROCEDURE DrawNode(currentPointer, yLevel, xLevel : INTEGER) //prevents empty tree giving an array index out of bounds error IF currentPointer <> -1 THEN DECLARE x, y : INTEGER x ← 250 + (xLevel * 60) y ← 50 + (yLevel * 60) CALL DRAWTEXT("tree", NUM_TO_STR(tree[currentPointer].data), "center", x, y, 20, "Arial", "white", "white", 1) IF tree[currentPointer].leftPointer <> -1 THEN CALL DRAWLINE("tree", x, y + 5, x - 50, y + 42, "white", 2) CALL DrawNode(tree[currentPointer].leftPointer, yLevel + 1, xLevel - 1) ENDIF IF tree[currentPointer].rightPointer <> -1 THEN CALL DRAWLINE("tree", x, y + 5, x + 50, y + 42, "white", 2) CALL DrawNode(tree[currentPointer].rightPointer, yLevel + 1, xLevel + 1) ENDIF ENDIF ENDPROCEDURE