Binary tree

From Computer Science Wiki
Jump to: navigation, search
Programming basics[1]

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.[2] Please do not get confused between a binary tree and a binary search tree.

The difference between a binary tree and a binary search tree is binary trees are not ordered whilst a binary search tree is ordered. 


Image of a tree

Binary tree.svg.png

tree vocabulary

In addition to NORMAL tree vocabulary:

  • root node
  • parent node
  • child node
  • leaf node

Binary Trees have special vocabulary:

  • left-child
  • right-child
  • subtree

Practical applications of a tree

  • Trees can be used to store data that has an inherent hierarchical structure. For example, an operating system may use a tree for directories, files and folders in its file management system.
  • They are dynamic, which means that it is easy to add and delete nodes.
  • They are easy to search and sort using standard traversal algorithms.
  • They can be used to process the syntax of statements in natural and programming languages so are commonly used when compiling programming code.

Binary Tree - video example

This video provides a basic introduction to binary trees.

Traversal

Traversal describes the order in which nodes are visited. I used this image with great gratitude from the guys at Dartford Grammar School[3]

Binary tree traversal.png

Applications of different methods of traversals

I used these definition from wikipedia [4]

  • Pre-order traversal while duplicating nodes and edges can make a complete duplicate of a binary tree. It can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly.
  • In-order traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).
  • Post-order traversal while deleting or freeing nodes and values can delete or free an entire binary tree. It can also generate a postfix representation of a binary tree.

Standards

  • DescribeGive a detailed account or picture of a situation, event, pattern or process. how trees operate logically (both binary and non-binary).
  • DefineGive the precise meaning of a word, phrase, concept or physical quantity. the terms: parent, left-child, right-child, subtree, root and leaf.
  • StateGive a specific name, value or other brief answer without explanation or calculation.Give a specific name, value or other brief answer without explanation or calculation. the result of inorder, postorder and preorder tree traversal.
  • SketchRepresent by means of a diagram or graph (labelled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features. binary trees.

See Also

External Links

high level discussion of binary trees

References