Binary tree
In computer science, a binary tree is a type of tree (data structure) where each item within the tree has at most two children.
Types of binary trees
change- In a balanced binary tree the left and right branches of every item differ in height by no more than 1.
- In a complete binary tree every level, except possibly the last, is completely filled, and all items in the last level are as far left as possible.
- In a full binary tree every item has either 0 or 2 children.
- In a perfect binary tree all interior items have two children and all leaves have the same depth or same level. A perfect binary tree is also a full and complete binary tree.
Representations
changeArray
changeA binary tree can be implemented using an array by storing its level-order traversal.[1] In a zero-indexed array, the root is often stored at index 1.
For the nth item of the array its:
- left child is stored at the 2n index.
- right child is stored at the 2n+1 index.
- parent is stored at the n/2 index.
References
changeIn a programming language with references, binary trees are typically constructed by having a tree structure which contains references to its left child and its right child.
Traversals
changePre-order
changeThe current item is visited, then the left branch is visited, and then the right branch is visited.
void preOrder(Item item) {
if (item == null) return;
visit(item);
preOrder(item.left);
preOrder(item.right);
}
In-order
changeThe left branch is visited, then the current item is visited, and then the right branch is visited.
void inOrder(Item item) {
if (item == null) return;
inOrder(item.left);
visit(item);
inOrder(item.right);
}
Post-order
changeThe left branch is visited, the right branch is visited, and then the current item is visited.
void postOrder(Item item) {
if (item == null) return;
postOrder(item.left);
postOrder(item.right);
visit(item);
}
References
change- ↑ Adamchik, Victor. "Binary Heap". Computer Science - 121 Fall 2009. CMU. Archived from the original on 25 April 2020. Retrieved 11 October 2020.