CINXE.COM

<!DOCTYPE HTML PUBLIC "-//IETF//DTD W3 HTML 2.0//EN"> <html lang="en-US"> <head> <title>tree</title> <meta name="description" content="Definition of tree, possibly with links to more information and implementations."> <meta name="keywords" content="tree"> <meta name="type" content="data structure"> <meta name="area" content="Trees">  <meta name="MSSmartTagsPreventParsing" content="TRUE"> <link rel="stylesheet" type="text/css" href="https://www.nist.gov/dads/dads.css"> </head> <body> <center> <a href="https://www.nist.gov/" target="_blank"><img src="../Images/webidblue_1linecentr.gif" border=0 height=43 width=229 alt="NIST"></a> </center> <h1>tree</h1> (data structure) Definition: (1) A data structure accessed beginning at the <a href="root.html">root</a> node. Each <a href="node.html">node</a> is either a <a href="leaf.html">leaf</a> or an <a href="internalnode.html">internal node</a>. An internal node has one or more <a href="child.html">child</a> nodes and is called the <a href="parent.html">parent</a> of its child nodes. All children of the same node are <a href="sibling.html">siblings</a>. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom. (2) A <a href="connectedGraph.html">connected</a>, <a href="undirectedGraph.html">undirected</a>, <a href="acyclicgraph.html">acyclic graph</a>. It is <a href="rootedtree.html">rooted</a> and <a href="orderedtree.html">ordered</a> unless otherwise specified. <img src="../Images/tree.png" height="219" width="318"> Thanks to Joshua O'Madadhain (jmadden@ics.uci.edu) for the figure, 6 October 2005. Formal Definition: (1) A tree is either <ul> <li>empty (no nodes), or <li>a root and zero or more subtrees. </ul> The subtrees are ordered. Specialization (... is a kind of me.) <a href="heap.html">heap</a>, <a href="btree.html">B-tree</a>, <a href="binarytree.html">binary tree</a>, <a href="balancedtree.html">balanced tree</a>, <a href="multiwaytree.html">multiway tree</a>, <a href="completetree.html">complete tree</a>, <a href="searchtree.html">search tree</a>, <a href="digitaltree.html">digital tree</a>, <a href="MerkleTree.html">Merkle tree</a>. See also other vocabulary: <a href="descendant.html">descendant</a>, <a href="ancestor.html">ancestor</a>, <a href="treeTraversal.html">tree traversal</a>, <a href="height.html">height</a>, <a href="depth.html">depth</a>, <a href="degree.html">degree</a> (3), technical terms: <a href="orderedtree.html">ordered tree</a>, <a href="rootedtree.html">rooted tree</a>, <a href="freetree.html">free tree</a>, <a href="arborescence.html">arborescence</a>. Note: Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. A tree in the data structure sense (1) is not the same as a tree in the graph sense (2). Consider possible <a href="binarytree.html">binary trees</a> with two nodes. There are two possible data structures: a root and a left subtree or a root and a right subtree. However there is only one possible graph: a root and a subtree. The graph definition doesn't allow for "the subtree is the right subtree and the left subtree is empty". Also there is no "empty" graph tree. Thanks to Sharat Chandran (sharat@cs.umd.edu) for clarifying the difference between these two senses. The formal definition is after <a href="../terms.html#CLR90">[CLR90, page 94]</a>. Authors: <a href="../Other/contrib.html#authorPEB">PEB</a>,<a href="../Other/contrib.html#authorCRC-A">CRC-A</a> <hr> Go to the <a href="https://www.nist.gov/dads/">Dictionary of Algorithms and Data Structures</a> home page. <hr> If you have suggestions, corrections, or comments, please get in touch with <a href="mailto:paul.black@nist.gov">Paul Black</a>. Entry modified 15 December 2017. HTML page formatted Wed Oct 30 12:15:31 2024. Cite this as: Paul E. Black and Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "tree", in <a href="https://www.nist.gov/dads/">Dictionary of Algorithms and Data Structures</a> [online], Paul E. Black, ed. 15 December 2017. (accessed TODAY) Available from: <a href="https://www.nist.gov/dads/HTML/tree.html">https://www.nist.gov/dads/HTML/tree.html</a> </body> </html>