Fandom

Programmer's Wiki

Tree

410pages on
this wiki
Add New Page
Talk0 Share

A tree is a data structure used for storing data. It is based on the mathematical tree, which is defined as a simple connected undirected acyclic graph. Trees in computer science represent a simple connected directed acyclic graph, where the origin of operations start with the root node.

Trees are especially efficient in the searching of sorting lists, as opposed to linked lists, which require strict sequential access. Trees are also important in some applications that require specifically the tree data structure.

Trees are made up of items known as nodes (equivalent to vertices in graphs). As in linked lists, nodes typically consists of pieces of useful data and one or more pointers to its children nodes.

OperationsEdit

Depending on the specific implementation, a tree may have different operations that may be done with it.

TraversalEdit

Traversal is a means of listing all the nodes in a tree.

  • breadth-first traversal: the nodes are traversed by level starting from the root node.
  • preorder or depth-first traversal: In binary trees, the nodes are traversed using a recursive algorithm: start with the root node of the tree, then traverse its left subtree, then traverse its right subtree.
  • inorder or symmetric traversal: Starts with the left subtree, then the root node, then the right subtree.
  • postorder traversal: Starts with the left subtree, then the right subtree, then the root node.

See also Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.