What is a tree - ecology lab
Trees
What is a tree??
LINK/EDGE
Element/NODE
Other parts of a tree
|Other parts of a tree |
|root |internal nodes |leafs |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
|path |descendants | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
Length of a tree
|Determining the Length of a Tree |
|Height | |Level |
|1 | |0 |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
|2 | |1 |
|3 | |2 |
Relationships of a tree - Part 1
“A” – no parents
“A” - 2 children “K” and “Q”
“K” – Parent is “A” “Q” – Parent is “A”
“K” - 1 child “Z”
“Z” – Parent is “K”
“Z” – no children Z’s ancestors are “K” and “A”
Relationships of a tree - Part 2
None None
K Q
A A
Z None
K Parent
None Left Child
Parent
Right Child
Other Info on Trees
• Trees are SHALLOW – they can hold many nodes with very few levels
• A height of 21 can hold 1048575 nodes
2height -1 = How many TOTAL nodes can he held by this tree
• Tree is inherently recursive structure, because each node in a tree can itself be viewed as the root of a smaller tree.
Types of Trees
• also called classification
• Binary
o has only 2 children
o used in Binary Search
o used in Tree Traversals (covered later)
o built (usually) in order
• Regular Binary // ex. Which-Way books
o has only 2 children
o may have a link back up to the parent
o may be built OUT of order
o or data inside each node has a pattern
o each like (left and right) is traveled depending on choice
▪ yes = left link
▪ no = right link
• Regular Tree
o may have MANY links to MANY kids!!!
Representing a Tree
• There are two ways to represent trees
o Linked Lists
▪ use links to connect to the other nodes in the tree
o Array
▪ much like Heap Sort algorithm
|Representing a Tree |
|Linked List | |Array |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| |“Helter Skelter” | |
| | | |
| | | |
| | |[0] |
| | |[1] |
| | |[2] |
| | |[3] |
| | |[4] |
| | |[5] |
| | |[6] |
| | | |
| | |7 |
| | |5 |
| | |1 |
| | |2 |
| | |3 |
| | | |
| | |6 |
| | | |
| | | |
| | | |
| | |// it is possible to have an empty element |
// draw indices OVER middle tree
|DATA |
|parent->link |
|left->link |
|right->link |
Draw the tree from the given info.
|5 |
|9 |
|7 |
|1 |
|6 |
|3 |
|4 |
|8 |
|0 |
| |
|Array-> |
|Tree |Linked List // draw boxes and links |
| | |
| | |
| | |
| | |
| | |
|9 |
|5 |
|6 |
| |
|7 |
| |
|1 |
| |
| |
|2 |
|6 |
| |
| |
|8 |
|4 |
| |
|Tree |Linked List |
| | |
| | |
| | |
| | |
| | |
|Array( |
|Tree |Linked List |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
Binary Tree Traversals
• the process of “visiting” or performing some operations on, each node of a tree is called TREE TRAVERSAL
• a traversal is to process each node ONCE
• There are 3 commonly used to traversals
o preorder
o inorder
▪ they differ in the sequence in which the nodes are visited
o postorder
• PREORDER/PREFIX
1. process root first
2. if (left child present, and not visited already) move to left, restart with Step 1 at new node
3. if (right child present, and not visited already) move to right, restart with Step 1 at new node
4. Else, go back up to parent, and start at step 3
▪ overall, the algorithm reaches the root first
• INORDER/INFIX
1. if (left child present, and not visited already) move to left, restart with Step 1 at new node
2. process root
3. if (right child present, and not visited already) move to right, restart with Step 1 at new node
4. Else go back up to parent, and start at step 2
• POSTORDER/POSTFIX
1. if (left child present, and not visited already) move to left, restart with Step 1 at new node
2. if (right child present, and not visited already) move to right, restart with Step 1 at new node
3. Else process root, go back to parent, and start at step 2
▪ overall, the algorithm reaches the root LAST
Hints on Building Trees
• UNLIKE LINKED LISTS, YOU MUST HAVE A GAME PLAN!!
• The FIRST node is always the simplest since there are no other nodes
• The rest of the nodes placed, must be traveled to the precise location needed, then placed
• Just like Linked Lists, remember to assign your links
o most will be set to NULL (left and right)
o link back up to Parent
o link from Parent to new node
Creating a Binary Search Tree
• in a Binary Search Tree
o items to the left are smaller in value
o items to the right are larger in value
|Simple Binary Tree |Complex Binary Tree |
| |[pic] |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
Adding a Node to a Binary tree
• use the Linked List Class Ditto
|Drawing what adding should do |
|First Node (M) |Adding another (T) |Adding another (Z) |
| | | |
| | | |
| | | |
|Adding another (B) |Adding another (F) |Adding another (A) |
| | | |
| | | |
| | | |
| | | |
| | | |
|Coding when placing a Node |
|Psuedocode |Code |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
Traveling through a Binary tree
• use the Linked List Class Ditto
• let use the infix algorithm
|Drawing what traveling should do |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|Coding |
|Psuedocode |Code |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
Other items needed
• a class for the node we are creating
• the Linked/Binary Tree class should be GENERIC
• we will need a comparator
|Completing our first Tree implementation |
|Code for the node |
|use Employee from previous material |
|Binary Tree class |
|public class BinarySearchTree |
|{ |
|// what items should go here?? |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|} |
|Comparator |
| |
| |
| |
| |
| |
| |
| |
| |
Other functions that would be worth while
• Search function
o find a person within that tree
o use the binary search method
▪ (after target determined)
▪ define middle
▪ is middle == target
▪ go left or right
• Remove function
o much like the reheapify function
o find our target
▪ use the search algorithm above
o restructure the tree
▪ THIS CAN BE COMPLICATED!!
-----------------------
A
K
Q
F
A
K
Q
F
2
3
7
5
A
Q
K
Z
A
Q
K
Z
Z
A
Z
Z
Z
F
Q
K
Z
F
Q
K
A
Z
F
Q
K
A
Z
F
Q
K
A
F
Q
K
A
1
7
7
5
1
3
2
2
6
5
9
1
6
8
0
6
6
E
P
Z
S
N
M
K
Q
A
A
Q
K
M
N
S
Z
P
E
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- what is a theme of a story
- what is a theme in a story
- what is a widget on a smartphone
- what is a negative plus a negative
- what is a skill on a resume
- what is a complement in a sentence
- what is a clause in a sentence
- what is a bin in a histogram
- what is a negative plus a positive
- what is a conflict in a story
- what is a a percentage
- what is a cpu on a computer