-
Notifications
You must be signed in to change notification settings - Fork 1
Trees
https://github.com/codefellows/seattle-java-401d6/tree/master/class-14
Great simple drawing of inorder, postorder, preorder
From Michelle's lecture on Oct 10, 2019, Class 19.
See also Front Row video, if you can access it. This recording going through the above tree problems, including how to step through a recursive tree problem, on Oct 10, 2019.
Only contain at most 2 children. No particular sorting order exists for binary trees. Add nodes where ever there's space.
A tree in which every node other than the leaves has two children.
3
/ \
2 10
/ \ / \
14 1 6 7
A tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
3
/ \
2 10
/ \ /
14 1 6
A complete binary tree is a balanced binary tree... but not the other way around.
All values smaller than the root are placed to the left, and all values greater than the root are placed to the right. Note that this is different than a binary tree.
All leaves are within one 1 h of each other, where h is the height of the tree. if the person uses d, that is referring to depth of the tree.
If no two values of depth are no more than 1 away from each other, it's a balanced tree. If the depth of one branch is greater or lesser than the depth of another branch by > 1, it's not a balanced tree.
Careful, though, there are variations on the definition of a balanced tree.
- Sorting is O(log n) time
- log2(1000000000) is only 29.9
Big O is O(n) where n is the height of the tree. Usually written like O(h).
A treenode has a value, a left and a right.
- Depth First
- PreOrder
- InOrder
- PostOrder
- Breadth First
Depth First has three ways to travels the HEIGHT of a tree.
ALGORITHM PreOrder(node)
// INPUT <-- root Node
// OUTPUT <-- preorder output of tree nodes
OUTPUT <-- node.Value
if node.LeftChild is not Null
PreOrder(node.LeftChild)
if node.RightChild is not NULL
PreOrder(node.RightChild)
Also roughly written like:
preOrder Print(Node root) {
print(root.value);
if(left not null) preOrderPrint(root.left)
if(right not null) preOrderPrint(root.right)
}
ALGORITHM InOrder(node)
// INPUT <-- root node
// OUTPUT <-- inorder output of tree nodes
if node.LeftChild is not NULL
InOrder(node.LeftChild)
OUTPUT <-- node.Value
if node.RightChild is not null
InOrder(node.RightChild)
Also roughly written like:
InOrder Print(Node root) {
if(left not null) InOrderPrint(root.left)
print(root.value);
if(right not null) InOrderPrint(root.right)
}
ALGORITHM PostOrder(node)
// INPUT <-- root node
// OUTPUT <-- postorder output of tree nodes
if node.LeftChild is not NULL
InOrder(node.LeftChild)
if node.RightChild is not null
InOrder(node.RightChild)
OUTPUT <-- node.Value
Written roughly, this is:
PostOrder Print(Node root) {
if(left not null) PostOrderPrint(root.left)
if(right not null) PostOrderPrint(root.right)
print(root.value);
}
Iterates through a tree by traveling through each level of the tree, node by node.
- Uses a **queue **
ALGORITHM BreadthFirst(root)
//INPUT <-- root node
// OUTPUT <-- front node of queue to console
Queue breadth <-- new Queue()
breadth.Enqueue(root)
while breadth.Peek
Node front = breadth.Dequeue()
OUTPUT <-- front.Value
if front.LeftChild is not null
breadth.Enqueue(front.LeftChild)
if front.RightChild is not NULL
breadth.Enqueue(front.RightChild)