Entry
BBCBASIC: Datastructure: Tree: Binary: Create: Simple: How to create a binary tree in BBCBASIC?
Jul 16th, 2006 05:27
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 29 October 2003 - 07:40 am --------------------
BBCBASIC: Data structure: Tree: Binary: Create: Simple: How to create
a binary tree in BBCBASIC?
---
Here an example of creating a representation of a binary tree, in an
array.
---
This tree is called a binary tree because each parent has maximum 2
children (there exist also trees with 3, 4, 5, ..., N children).
The simplest case, a tree with 1 child is called a linear list.
The binary tree is the next simplest case.
---
The binary tree for e.g.
3 + 4 * 5
looks for example like this
"+"
|
+--+--+
| |
"3" "*"
|
+--+--+
| |
"4" "5"
---
This binary tree is designed such, that the operation with the highest
(arithmetic) priority (which is the '*', which has a higher priority
than the '+') is done first (as you, by choice, start evaluating here
at the lowest part of the tree first, in the order 'left node', 'middle
node', 'right node').
---
1. To store this binary tree you create an array for this (thus a
table, or a rectangular structure with rows and columns)
1. With as many rows as there are nodes in the tree
(there are 5 nodes in the tree, thus you create minimally 5
rows).
2. With minimally 3 columns,
1. One column for the left pointer
2. One column for the data itself
3. One column for the right pointer
-------------------------------------------------
| NR | LEFT POINTER | DATA | RIGHT POINTER |
-------------------------------------------------
1
2
3
4
5
-------------------------------------------------
2. You then assign (rather arbitrary) a number (here between 1 and 5,
because there are five nodes in the tree) to each of the nodes of
the tree
1 "+"
|
+--+--+
| |
2 "3" "*" 3
|
+--+--+
| |
4 "4" "5" 5
3. Then you put that nodes in the corresponding rows of the array
(thus node 1 in row 1, node 2 in row 2, node 3 in row 3,
node 4 in row 4, node 5 in row 5)
-------------------------------------------------
| NR | LEFT POINTER | DATA | RIGHT POINTER |
-------------------------------------------------
1 "+"
2 "3"
3 "*"
4 "4"
5 "5"
-------------------------------------------------
4. Then you tell for each of the nodes to which of the other
nodes they point left and right.
(e.g. the node of '+' points to the left
to number 2, and to the right to number 3)
-------------------------------------------------
| NR | LEFT POINTER | DATA | RIGHT POINTER |
-------------------------------------------------
1 2 "+" 3
2 "3"
3 4 "*" 5
4 "4"
5 "5"
-------------------------------------------------
5. If the node does not point to any node,
you indicate this (for example) by filling
in -1 (this choice is rather arbitrary,
you just indicate somehow that that node does not
have children)
-------------------------------------------------
| NR | LEFT POINTER | DATA | RIGHT POINTER |
-------------------------------------------------
1 "+"
2 -1 "3" -1
3 "*"
4 -1 "4" -1
5 -1 "5" -1
-------------------------------------------------
6. So combining this all together, this becomes
-------------------------------------------------
| NR | LEFT POINTER | DATA | RIGHT POINTER |
-------------------------------------------------
1 2 "+" 3
2 -1 "3" -1
3 4 "*" 5
4 -1 "4" -1
5 -1 "5" -1
-------------------------------------------------
7. Now you have created the array and filled it systematically with the
representation of your tree, you take this array and put it in DATA
statements
1. Each row of the array becomes a DATA line
2. You work from top row to bottom row in the array
3. Thus you get as many data lines as there
are rows in the array (or thus as many
data lines as there are nodes in the
tree)
DATA 2, "+", 3
DATA -1, "3", -1
DATA 4, "*", 5
DATA -1, "4", -1
DATA -1, "5", -1
8. Now you create a program to read this binary tree
representation (from the given DATA in to such
an array)
1. You supply that program the following 3 parameters
1. You tell it the row where the root of the tree is located.
1. That is row 1 here
2. You tell it which symbol you have chosen to indicate the fact
that that node has no children there.
1. The number -1 was chosen
3. You tell it the total amount of rows of the array
1. The total amount of nodes in this particular
tree is 5.
Thus the minimum amount of rows in your array
should be 5.
4. You tell the maximum amount of rows in the array
In this program some more rows (that is 10) were chosen,
because you might have to use the same array later, but then
you have more nodes in that other binary tree. In order to
cope with that more general situation a higher number of rows
was chosen). The non existing nodes are indicated here with
"" in the DATA, and their nodes with -1.
DATA -1, "", -1
DATA -1, "", -1
DATA -1, "", -1
DATA -1, "", -1
DATA -1, "", -1
2. To supply the 3 columns, you have the choice to create
1 two dimensional array, with 3 columns and N rows
e.g.
DIM binaryTree$( 3, 5 )
-- or equivalently --
3 arrays with N rows
e.g.
DIM leftPointerP%( 5 )
DIM dataS$( 5 )
DIM rightPointerP%( 5 )
1. -The latter choice was chosen in this program
3. The program then
1. -Creates the 3 arrays
2. -Reads the representation of the binary tree
(here 3 + 4 * 5) in this arrays out of the
given DATA
3. -Prints this arrays,
1. -You will see each row, from top to bottom
4. Using other programs you can then manipulate that tree
1. -e.g.
1. Walk the tree
2. Insert new nodes in the tree
3. Remove nodes from the tree
4. Search the tree
5. ...
===
--- cut here ---------------------------------------------------------
PROCTreeCreateBinaryMain( 1, -1, 5, 10 )
END
:
:
:
DEF PROCTreeCreateBinaryMain( rootP%, nilP%, rowMaxI%, dimMaxI% )
REM e.g. PROCTreeCreateBinaryMain( 1, -1, 5, 10 )
REM e.g. END
PROCTreeCreateBinaryInitDim( dimMaxI% )
PROCTreeCreateBinaryStoreData
PROCTreeCreateBinaryInitData( dimMaxI% )
PROCTreeCreatePrintData( rowMaxI% )
ENDPROC
:
DEF PROCTreeCreateBinaryInitDim( maxI% )
DIM lP%( maxI% )
DIM rP%( maxI% )
DIM s$( maxI% )
ENDPROC
:
DEF PROCTreeCreateBinaryInitData( maxI% )
LOCAL I%
LOCAL minI%
minI% = 1
FOR I% = minI% TO maxI%
READ lP%( I% )
READ s$( I% )
READ rP%( I% )
NEXT I%
ENDPROC
:
DEF PROCTreeCreatePrintData( maxI% )
LOCAL I%
FOR I% = 1 TO maxI%
PRINT; lP%( I% ); " "; s$( I% ); " "; rP%( I% )
NEXT I%
ENDPROC
:
DEF PROCTreeCreateBinaryStoreData
REM
REM here 3 + 4 * 5 is stored in a binary tree
REM
REM ---
REM
REM the binary tree is represented by arrays
REM
REM ---
REM
REM format:
REM
REM leftpointer, data, rightpointer
REM
REM ---
REM
DATA 2, "+", 3
DATA -1, "3", -1
DATA 4, "*", 5
DATA -1, "4", -1
DATA -1, "5", -1
DATA -1, "" , -1
DATA -1, "" , -1
DATA -1, "" , -1
DATA -1, "" , -1
DATA -1, "" , -1
ENDPROC
:
--- cut here ---------------------------------------------------------
---
If you compile this source code, it will show
the rows:
+------------------------------------------------------+
| |
| 2 + 3 |
| |
| |
| |
| -1 3 -1 |
| |
| |
| |
| 4 * 5 |
| |
| |
| |
| -1 4 -1 |
| |
| |
| |
| -1 5 -1 |
| |
| |
+------------------------------------------------------+
---
---
Internet: see also:
---
BBCBASIC: Windows: Data structure: Link: Overview: Can you give an
overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/41639/fid/768
---
C#: Data structure: Tree: Binary: Create: Simple: How to create a
binary tree in C#?
http://www.faqts.com/knowledge_base/view.phtml/aid/26116/fid/791
---
C++: Data structure: Tree: Binary: Create: Simple: How to create a
binary tree in C++?
http://www.faqts.com/knowledge_base/view.phtml/aid/25923/fid/163
---
Delphi: Data structure: Tree: Binary: Create: Simple: How to create a
binary tree in Delphi?
http://www.faqts.com/knowledge_base/view.phtml/aid/26110/fid/175
---
Java: Data structure: Tree: Binary: Create: Simple: How to create a
binary tree in Java?
http://www.faqts.com/knowledge_base/view.phtml/aid/26106/fid/165
----------------------------------------------------------------------
