Contents |
A binary tree is a two-dimensional linked-list. Typically, a node in a binary tree has two next pointers, named left and right, and a value pointer. Binary tree nodes may have parent pointers, as well
class binaryTreeNdde { var value; var left; var right; } class binaryTree { var root; //points to the root binary node //operations ... }
The terms used in describing a binary tree are:
Complete binary trees (heaps) are used in heapsorting and other higher-order algorithms.
The most common use of a binary tree is when it is formulated as a binary search tree.
Binary trees are implemented with nodes.
The common operations on a binary tree are insert, find, and delete. The actual implementation of these operations depends on the kind of binary tree, say a binary search tree or a heap.
In an in-order traversal is easily implemented using a recursive process that implements the following steps:
Note that the node processing step occurs "in the middle". Hence the name, in-order. Processing the node is a phrase meant to capture the purpose of the traversal. For printing out the nodes of a tree, processing the node means printing the value of the node. Here is such a traversal:
function print-in-order(node) { if (node.get-left() == null) print-in-order(node.get-left()); println(node.get-value()); if (node.get-right() == null) print-in-order(node.get-right()); }
This code can be simplified by the strategy of "falling off the tree". One detects a falling off by seeing if the given node has become null. If so, no processing is done. Recall that the null value is used to signify that a node pointer does not point to any node.
function print-in-order(node) { if (node != null) { print-in-order(node.get-left()); println(node.get-value()); print-in-order(node.get-right()); } }
A pre-order traversal is like an in-order traversal, except node processing happens first:
In a post-order traversal, node processing happens last.
A level order uses a queue as an auxilliary structure. The traversal starts be enqueuing the root node. Next a loop:
The loop continues until the queue is empty.
Contents |