Scribd
Upload
281 views

Binary Tree Using A 2D Array

The document compares two methods for initializing and manipulating a binary search tree data structure - using a 1D array of tree nodes versus a 2D array. Both methods initialize the tree by setting the root pointer to -1 and free pointer to 1, then populate the left pointers of the array/2D array. Nodes are inserted by assigning data to the free node, setting left/right pointers to -1, updating free pointer. Nodes are found by recursively searching left/right of the root/parent nodes based on data comparison.

Uploaded by

Suhail Alam Khan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
281 views

Binary Tree Using A 2D Array

The document compares two methods for initializing and manipulating a binary search tree data structure - using a 1D array of tree nodes versus a 2D array. Both methods initialize the tree by setting the root pointer to -1 and free pointer to 1, then populate the left pointers of the array/2D array. Nodes are inserted by assigning data to the free node, setting left/right pointers to -1, updating free pointer. Nodes are found by recursively searching left/right of the root/parent nodes based on data comparison.

Uploaded by

Suhail Alam Khan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

INITIALIZE TREE USING 1-D Array And Nodes INITIALIZE TREE USING 2D Array

TYPE TreeNode CONSTANT LeftPointer = 1


DECLARE DATA:STRING CONSTANT Data = 2
DECLARE LeftPointer:INTEGER CONSTANT RightPointer = 3
DECLARE RightPointer:INTEGER DECLARE RootPointer:INTEGER
END TYPE DECLARE FreePtr:INTEGER
DECLARE TREE[1:7,1:3] OF INTEGER
DECLARE RootPointer:INTEGER
DECLARE FreePtr:INTEGER
DECLARE TREE[1:7] : TREENODE
PROCEDURE InitializeTree() PROCEDURE InitializeTree()
RootPointer = -1 RootPointer = -1
FreePtr = 1 FreePtr = 1
FOR index = 1 to 6 FOR index = 1 to 6
Tree[Index].LeftPointer = Index + 1 TREE[index][LeftPointer]= index + 1
ENDFOR ENDFOR
TREE[7].LeftPointer = -1 TREE[7][LeftPointer] = -1
END PROCEDURE END PROCEDURE
TREE USING 1-D Array And Nodes TREE USING 2D Array

Procedure InsertNode(DataItem) Procedure InsertNode(DataItem)


IF FreePtr<>-1 Then IF FreePtr<>-1 Then
Declare NewNodePointer:Integer Declare NewNodePointer:Integer
NewNodePointer = FreePtr NewNodePointer = FreePtr
Tree[NewNodePointer].Data = DataItem Tree[NewNodePointer][Data] = DataItem
Tree[NewNodePointer].LeftPointer = -1 Tree[NewNodePointer][LeftPointer] = -1
Tree[NewNodePointer].RightPointer = -1 Tree[NewNodePointer][RightPointer] = -1
FreePtr = Tree[FreePtr].LeftPointer FreePtr = Tree[FreePtr][LeftPointer]

IF RootPointer = -1 Then IF RootPointer = -1 Then


RootPointer = NewNodePointer RootPointer = NewNodePointer
ElSE ElSE
Declare TNP:INTEGER Declare TNP:INTEGER
DECLARE PNP:INTEGER DECLARE PNP:INTEGER
DECLARE TurnedRight:Boolean DECLARE TurnedRight:Boolean
TNP = RootPointer TNP = RootPointer
WHILE TNP<>-1 WHILE TNP<>-1
PNP = TNP PNP = TNP
IF DataItem > Tree[TNP].data IF DataItem > Tree[TNP][Data]
TurnedRight = True TurnedRight = True
TNP = Tree[TNP].RightPointer TNP = Tree[TNP][RightPointer]
ELSE ELSE
TurnedRight = False TurnedRight = False
TNP = Tree[TNP].LeftPointer TNP = Tree[TNP][LeftPointer]
ENDIF ENDIF
ENDWHILE ENDWHILE
END IF END IF

IF TurnedRight = True THEN IF TurnedRight = True THEN


Tree[PNP].RightPointer = NewNodePointer Tree[PNP][RightPointer] = NewNodePointer
ELSE ELSE
Tree[PNP].LeftPointer = NewNodePointer Tree[PNP][LeftPointer] = NewNodePointer
ENDIF ENDIF
END PROCEDURE END PROCEDURE
TREE USING 1-D Array And Nodes TREE USING 2D Array

FUNCTION FindNode(Searchitem) RETURNS INTEGER FUNCTION FindNode(Searchitem) RETURNS INTEGER


DECLARE TNP:INTEGER DECLARE TNP:INTEGER
TNP = RootPointer TNP = RootPointer
WHILE TNP < > -1 AND Tree[TNP].Data <> Searchitem WHILE TNP < > -1 AND Tree[TNP][Data] <> Searchitem
IF Tree[TNP].Data > Searchitem THEN IF Tree[TNP][Data] > Searchitem THEN
TNP = Tree [TNP] .LeftPointer TNP = Tree [TNP] [LeftPointer]
ELSE ELSE
TNP = Tree[TNP].RightPointer TNP = Tree[TNP][RightPointer]
ENDIF ENDIF
ENDWHILE ENDWHILE

RETURN TNP RETURN TNP


END FUNCTION END FUNCTION

You might also like