Editing Binary tree (section)

== Methods for storing binary trees ==<!-- This section is linked from [[Ahnentafel]] -->
Binary trees can be constructed from [[programming language]] primitives in several ways.

=== Nodes and references ===

In a language with [[record (computer science)|records]] and [[reference (computer science)|references]], binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child. Sometimes it also contains a reference to its unique parent. If a node has fewer than two children, some of the child pointers may be set to a special null value, or to a special [[sentinel node]].

This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time; a more conservative representation alternative is [[threaded binary tree]].<ref name="Samanta2004">{{cite book|author=D. Samanta|title=Classic Data Structures|year=2004|publisher=PHI Learning Pvt. Ltd.|isbn=978-81-203-1874-8|pages=264–265}}</ref>

In languages with [[tagged union]]s such as [[ML (programming language)|ML]], a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple of data, left child, and right child, and the other of which is a "leaf" node, which contains no data and functions much like the null value in a language with pointers. For example, the following line of code in [[OCaml]] (an ML dialect) defines a binary tree that stores a character in each node.<ref name="Scott2009">{{cite book|author=Michael L. Scott| title=Programming Language Pragmatics |year=2009| publisher=Morgan Kaufmann|isbn=978-0-08-092299-7|page=347| edition=3rd}}</ref>

<!-- the source gives the example in Standard ML, which has "datatype" instead of "type", but wikipedia's source tag doesn't support Standard ML. -->
<syntaxhighlight lang="ocaml">
type chr_tree = Empty | Node of char * chr_tree * chr_tree
</syntaxhighlight>

=== Arrays ===

Binary trees can also be stored in breadth-first order as an [[implicit data structure]] in [[array data structure|arrays]], and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index ''i'', its children are found at indices <math>2i + 1</math> (for the left child) and <math>2i +2</math> (for the right), while its parent (if any) is found at index ''<math>\left \lfloor \frac{i-1}{2} \right \rfloor</math>'' (assuming the root has index zero). Alternatively, with a 1-indexed array, the implementation is simplified with children found at <math>2i</math> and <math>2i+1</math>, and parent found at <math>\lfloor i/2 \rfloor</math>.<ref>{{Cite book| title=Introduction to algorithms| date=2001|publisher=MIT Press|others=Cormen, Thomas H., Cormen, Thomas H.|isbn=0-262-03293-7|edition=2nd|location=Cambridge, Mass.| pages=128| oclc=46792720}}</ref>

This method benefits from more compact storage and better [[locality of reference]], particularly during a preorder traversal. It is often used for [[binary heap]]s.<ref>{{Cite web |last=Laakso |first=Mikko |title=Priority Queue and Binary Heap |url=http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html |access-date=2023-10-11 |website=University of Aalto}}</ref>

[[Image:Binary tree in array.svg|upright=1.2|center|A small complete binary tree stored in an array]]