Binary tree: Difference between revisions

From Computer Science Wiki
Line 39: Line 39:
Traversal describes the order in which nodes are visited.  I used this image with great gratitude from the guys at Dartford Grammar School<ref>http://ib.compscihub.net/wp-content/uploads/2015/04/5.1.16.pdf</ref>
Traversal describes the order in which nodes are visited.  I used this image with great gratitude from the guys at Dartford Grammar School<ref>http://ib.compscihub.net/wp-content/uploads/2015/04/5.1.16.pdf</ref>


 
<br />
<br />
[[File:Binary tree traversal.png]]
[[File:Binary tree traversal.png]]



Revision as of 11:04, 9 December 2016

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]


Image of a tree[edit]

Binary tree.svg.png

tree vocabulary[edit]

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[edit]

  • 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[edit]

This video provides a basic introduction to binary trees.

Traversal[edit]

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

Standards[edit]

  • Describe how trees operate logically (both binary and non-binary).
  • Define the terms: parent, left-child, right-child, subtree, root and leaf.
  • State the result of inorder, postorder and preorder tree traversal.
  • Sketch binary trees.

See Also[edit]

External Links[edit]

high level discussion of binary trees

References[edit]