Transcript Binary Trees

Binary Trees
Page 1
Binary Trees
•
•
•
•
A binary tree is a linked structure that allows for a binary
search strategy.
A binary tree consists of a finite number of nodes
(structured data objects).
Each node can point to either 0, 1, or (at most) 2
different nodes (structures).
Assume we have the following array of random integers:
9
12
7
14
10
4
3
8
13
If We wished to find an element on the list:
• We could perform a sequential search (easy but slow)
• We could sort and do a binary search (fast but difficult to
sort and maintain)
• A binary tree provides a compromise
Data Structures in C for Non-Computer Science Majors
Kirs and Pflughoeft
Binary Trees
Page 2
Setting Up a Binary Tree
Assume that each element on our list:
9
12
7
14
10
4
3
8
13
Is a node in our tree. The structure of each node will be:
struct treetemplate
{ int
value;
struct treetemplate *left, *right; };
Take 1 element from the list (e.g., the first one), and set it in as the
first (root) node
9
Data Structures in C for Non-Computer Science Majors
The first element is now
the root of the tree
Kirs and Pflughoeft
Binary Trees
Page 3
Assume that this element were assigned location 12622 in RAM:
12622 - 12623
12624-12627
12628-12631
9
NULL
NULL
Field: value
Field: left
Field: right
Notice that the pointer fields (left and right) initially point to nothing
To insert the remaining elements from our array onto the list:
1. Starting at the root, determine if the element is larger or
smaller
2. Assume that larger elements will go the right, and smaller
elements will go to the left.
3. Continue with the remaining elements on the list putting them
in place in the tree.
Data Structures in C for Non-Computer Science Majors
Kirs and Pflughoeft
Binary Trees
Page 4
Now add the next (second) element into the tree:
9
12
7
14
10
4
3
8
13
Since 12 is greater than
9, go to the right
Root
9
If the second element (structure)
were assigned to address 12720,
RAM might appear as:
12
12622 - 12623
12624-12627
12628-12631
9
NULL
12720
12720 - 12721
12722-12725
12726-12721
12
NULL
NULL
Data Structures in C for Non-Computer Science Majors
Kirs and Pflughoeft
Binary Trees
Page 5
Now add the next (third) element into the tree:
9
12
7
14
Since 7 is less
than 9, go to
the left
10
4
3
8
13
9
If the third element were
assigned to address 12730,
RAM might appear as:
12
7
12622 - 12623
12624-12627
12628-12631
9
12730
12720
12720 - 12721
12722-12725
12726-12729
12730 - 12731
12732-12735
12736-12739
12
NULL
NULL
7
NULL
NULL
Data Structures in C for Non-Computer Science Majors
Kirs and Pflughoeft
Binary Trees
Page 6
Now add the next (fourth) element into the tree:
9
12
7
14
10
4
3
8
13
Since 14 is greater than 9,
go to the right
9
7
If the fourth element
were assigned to address 12756, RAM
might appear as:
Since 14 is greater
than 12, go right
12
14
12622 - 12623
12624-12627
12628-12631
9
12730
12720
12720 - 12721
12722-12725
12726-12729
12730 - 12731
12732-12735
12736-12739
12
NULL
12756
7
NULL
NULL
12756 - 12757
12758-12761
12762-12765
14
NULL
NULL
Data Structures in C for Non-Computer Science Majors
Kirs and Pflughoeft
Binary Trees
Page 7
Now add the next (fifth) element into the tree:
9
12
7
14
10
4
12
If the fifth element
were assigned to address 12824, RAM
might appear as:
10
8
13
Since 10 is greater than
9, go to the right
Since 10 is less than
12, go left
9
7
3
14
12622 - 12623
12624-12627
12628-12631
9
12730
12720
12720 - 12721
12722-12725
12726-12729
12730 - 12731
12732-12735
12736-12739
12
12824
12756
7
NULL
NULL
12756 - 12757
12758-12761
12762-12765
12824 - 12825
12826-12829
12830-12833
14
NULL
NULL
10
NULL
NULL
Data Structures in C for Non-Computer Science Majors
Kirs and Pflughoeft
Binary Trees
Page 8
Adding the remaining elements onto the list:
9
12
7
14
10
4
3
8
13
9
7
4
3
Data Structures in C for Non-Computer Science Majors
12
8
10
14
13
Kirs and Pflughoeft
Binary Trees
Page 9
RAM might
appear as:
9
7
12622 -12623
12624-12627
12628-12631
9
12730
12720
12
4
8
14
10
3
13
12720 -12721
12722-12725
12
12824
12756 -12757
12758-12761
12762-12765
12824 -12825
12826-12829
12830-12833
14
13310
NULL
10
NULL
NULL
12900 -12901
12902-12905
4
12910
12726-12729 12730-12731
12756
12906-12909 12910 -12911
NULL
13300 -12301
12302-12305
8
NULL
Data Structures in C for Non-Computer Science Majors
3
12736-12739
12900
13300
7
12912-12915
12916-12919
NULL
NULL
12306-12309 13310 -12311
NULL
12732-12735
13
12312-12315
12316-12319
NULL
NULL
Kirs and Pflughoeft
Binary Trees
Data Structures in C for Non-Computer Science Majors
Page 10
Kirs and Pflughoeft
Binary Trees
Data Structures in C for Non-Computer Science Majors
Page 11
Kirs and Pflughoeft
Binary Trees
Data Structures in C for Non-Computer Science Majors
Page 12
Kirs and Pflughoeft
Binary Trees
Data Structures in C for Non-Computer Science Majors
Page 13
Kirs and Pflughoeft
Binary Trees
Data Structures in C for Non-Computer Science Majors
Page 14
Kirs and Pflughoeft
Binary Trees
Data Structures in C for Non-Computer Science Majors
Page 15
Kirs and Pflughoeft
Binary Trees
Page 16
Binary Trees
RECURSION
• Recursion is a programming technique which allows a
function to call itself.
• Without recursion, traversing (moving about) binary trees
becomes very difficult.
Leaf
Data Structures in C for Non-Computer Science Majors
Kirs and Pflughoeft