In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. Each node has zero or more child nodes, which are below it in the tree (in computer science, unlike in nature, trees grow down, not up). A node that has a child is called the child's parent node. A child has at most one parent; a node without a parent is called the root node (or root). Nodes with no children are called leaf nodes. Computer science (academically, CS, CSC or compsci) encompasses a variety of topics that relates to computation, like abstract analysis of algorithms, formal grammars, and subjects such as programming languages, program design, software and computer hardware. ... A binary tree, a simple type of branching linked data structure. ... A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ... A child node or descendant node is a node in a tree data structure that is linked to by a parent node. ... Computer science (academically, CS, CSC or compsci) encompasses a variety of topics that relates to computation, like abstract analysis of algorithms, formal grammars, and subjects such as programming languages, program design, software and computer hardware. ... A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ... A root node is a specially chosen node in a tree data structure at which all operations on the tree begin. ... In computer science, a leaf node is a node of a tree data structure that has zero child nodes. ...

In graph theory, a tree is a connected acyclic graph. A rooted tree is such a graph with a vertex singled out as the root. In this case, any two vertices connected by an edge inherit a parent-child relationship. An acyclic graph with multiple connected components or a set of rooted trees is sometimes called a forest. In mathematics and computer science, graph theory studies the properties of graphs. ... A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

There are two basic types of tree. In an unordered tree, there is no distinction between the various children of a node --- none is the "first child" or "last child". A tree in which such distinctions are made is called an ordered tree, and data structures built on them are called ordered tree data structures. Ordered trees are by far the most common form of tree data structure.

A simple example binary tree

Binary trees are one kind of ordered tree, and there is a one-to-one mapping between binary trees and general ordered trees. A simple binary tree, made by Derrick Coetzee in Illustrator. ... A simple binary tree, made by Derrick Coetzee in Illustrator. ... In computer science, a binary tree is an ordered tree data structure in which each node has at most two children. ...

There are many different ways to represent trees; common representations represent the nodes as records allocated on the heap with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap). In computer programming, an array, also known as a vector or list, is one of the simplest data structures. ... Binary heaps are a particularly simple kind of heap data structure created using a binary tree. ...

Stepping through the items of a tree, by means of the connections between parents and children, is called walking the tree, and the action is a walk of the tree. Often, an operation might be performed when a pointer arrives at a particular node. A walk where the operation happens to a node before it happens to its children is called a pre-order walk; a walk where the children are operated upon before the parent is called a post-order walk. See tree traversal for a discussion of pre-order, in-order and post-order traversal. In computer science, tree traversal is the process of visiting each node in a tree data structure. ...

Common operations on trees are:

• enumerating all the items;
• searching for an item;
• adding a new item at a certain position on the tree;
• deleting an item;
• removing a whole section of a tree (called pruning);
• adding a whole section to a tree (called grafting);
• finding the root for any node.

Common uses for trees are:

• to manipulate hierarchical data;
• to make information easily searchable (see also: tree search algorithm);
• to manipulate sorted lists of data.

A hierarchy (in Greek hieros = sacred, arkho = rule) is a system of ranking and organizing things. ... In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem. ... Tree search algorithms are specialized versions of graph search algorithms, which take the properties of trees into account. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

Examples

• http://www.aisee.com/graphs
• SDXF

SDXF stands for Structured Data eXchange Format. This Format is also published as an Internet RFC (see http://www. ...

Related Terms

• Binary space partitioning
• heap
• tree (graph theory)
• tree search algorithm
• tree structure
• exponential tree

Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. ... This page discusses the heap data structure. ... A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... Tree search algorithms are specialized versions of graph search algorithms, which take the properties of trees into account. ... A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ... An exponential tree is almost identical to a [binary search tree], with the exception that the dimension of the tree is not the same at all levels. ...

External links

• Description  (http://www.nist.gov/dads/HTML/tree.html) from the Dictionary of Algorithms and Data Structures
• STL-like C++ tree class (http://www.damtp.cam.ac.uk/user/kp229/tree/)
• List of data structures (http://www2.informatik.uni-halle.de/lehre/leda/MANUAL/List_data_structures.html) from LEDA