Karl Jones: /* External links */

2016-04-21T15:18:14Z

‎External links

Karl Jones: /* See also */

2016-02-20T19:56:04Z

‎See also

Karl Jones: Created page with "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..."

2016-02-20T19:55:43Z

Created page with "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..."

New page

In [[computer science]], a '''binary tree''' is a [[tree data structure]] in which each [[Node (computer science)|node]] has at most two [[children]], which are referred to as the [[left child]] and the [[right child]].

== Description ==

A [[recursive definition]] using just [[set theory]] notions is that a (non-empty) binary tree is a triple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.

Some authors allow the binary tree to be the [[empty set]] as well.

== Graph theory ==

From a [[graph theory]] perspective, binary (and K-ary) trees as defined here are actually [[Arborescence|arborescences]].

A binary tree may thus be also called a [[bifurcating arborescence]] -- a term which actually appears in some very old programming books, before the modern computer science terminology prevailed.

It is also possible to interpret a binary tree as an [[undirected graph]], rather than a [[directed graph]], in which case a binary tree is an ordered, rooted tree.

Some authors use rooted binary tree instead of binary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted.

A binary tree is a special case of an ordered K-ary tree, where k is 2.

== Applications ==

In [[computing]], binary trees are seldom used solely for their structure. Much more typical is to define a labeling function on the nodes, which associates some value to each node.

Binary trees labelled this way are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting.

The designation of non-root nodes as left or right child even when there is only one child present matters in some of these applications, in particular it is significant in binary search trees.

== Varying definitions in mathematics ==

In [[mathematics]], what is termed binary tree can vary significantly from author to author.

Some use the definition commonly used in [[computer science]], but others define it as every non-leaf having exactly two children and don't necessarily order (as left/right) the children either.

== See also ==

* [[Binary expression tree]]
* [[Computer science]]
* [[Mathematical expression]]
* [[Node (computer science)]]

== External links ==

* [https://en.wikipedia.org/wiki/Binary_tree Binary tree] @ Wikipedia

← Older revision		Revision as of 15:18, 21 April 2016
Line 45:		Line 45:

	* [https://en.wikipedia.org/wiki/Binary_tree Binary tree] @ Wikipedia		* [https://en.wikipedia.org/wiki/Binary_tree Binary tree] @ Wikipedia
		+
		+	[[Category:Computer science]]
		+	[[Category:Logic]]
		+	[[Category:Mathematics]]

@@ Line 37: / Line 37: @@
 * [[Binary expression tree]]
 * [[Computer science]]
 * [[Mathematical expression]]
 * [[Node (computer science)]]

Binary tree - Revision history

Karl Jones: /* External links */

Karl Jones: /* See also */

Karl Jones: Created page with "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..."