Software Engineering Stack Exchange
Software Engineering Stack Exchange

Questions tagged [trees]

A tree is a hierarchical data structure in which every node is accessed via a unique path that starts at a unique root node. Trees are often used for searching data and optimizing an ordered access to nodes. In the graph theory, a tree is a graph of connect nodes without cycles. Attention: use tag 'trie' for the tree like data structure aiming at string matching (prefix/suffix)

A tree is a hierarchical data structure of nodes and edges. It is build on a unique root node and every node is accessed via a unique path starting from the root.

In the graph theory, a tree is a graph of connect nodes without cycles. There's no special root node in this graph definition, because any node of the graph could be used as root.

A tree structure is by construction recursive: the root has edges to other nodes, which are each the root of a subtree. A node without sub-tree is called a leaf node.

Trees are often used for searching data and optimizing an ordered access to nodes:

Attention: use tag 'trie' for the tree like data structure aiming at string matching (prefix/suffix)

162 questions
51
votes
4 answers

How exactly is an Abstract Syntax Tree created?

I think I understand the goal of an AST, and I've built a couple of tree structures before, but never an AST. I'm mostly confused because the nodes are text and not number, so I can't think of a nice way to input a token/string as I'm parsing some…
Howcan
  • 721
  • 2
  • 7
  • 7
26
votes
3 answers

Implementing the Visitor Pattern for an Abstract Syntax Tree

I'm in the process of creating my own programming language, which I do for learning purposes. I already wrote the lexer and a recursive descent parser for a subset of my language (I currently support mathematical expressions, such as + - * / and…
marco-fiset
  • 8,721
  • 9
  • 35
  • 46
22
votes
3 answers

How do I traverse a tree without using recursion?

I have a very large in memory node tree and need to traverse the tree. Passing the returned values of each child node to their parent node. This has to be done until all the nodes have their data bubble up to the root node. Traversal works like…
Reactgular
  • 13,040
  • 4
  • 48
  • 81
21
votes
4 answers

Is Pre-Order traversal same as Depth First Search?

It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please correct me if I am wrong? Thanks in advance!
Srikanth Kandalam
  • 313
  • 1
  • 2
  • 4
14
votes
2 answers

What's the simplest example out there to explain the difference between Parse Trees and Abstract Syntax Trees?

To my understanding, a parser creates a parse tree, and then discards it thereafter. However, it can also pop out an abstract syntax tree, which the compiler supposedly makes use of. I'm under the impression that both the parse tree and the abstract…
Combinator Logic
  • 143
  • 1
  • 6
13
votes
2 answers

Is a tree with nodes that have reference to parent still a tree?

If we make reference to the parent for each node in a tree, do we still have a tree (by definition) anymore? Wikipedia definition is: In computer science, a tree is a widely used abstract data type (ADT) or data structure implementing this ADT…
Mohsen
  • 1,970
  • 3
  • 22
  • 32
12
votes
5 answers

How should I create a mutable, varied jtree with arbitrary/generic category nodes?

Please note: I don't want coding help here, I'm on Programmers for a reason. I want to improve my program planning/writing skills not (just) my understanding of Java. I'm trying to figure out how to make a tree which has an arbitrary category…
AncientSwordRage
  • 1,033
  • 1
  • 11
  • 24
11
votes
5 answers

Quadtree with duplicates

I'm implementing a quadtree. For those who don't know this data structure, I am including the following small description: A Quadtree is a data structure and is in the Euclidean plane what an Octree is in a 3-dimensional space. A common use of…
Pierre Arlaud
  • 1,329
  • 1
  • 13
  • 21
9
votes
4 answers

Most efficient way to generate all descendents of all nodes in a tree

I'm looking for the most efficient algorithm to take a tree (stored as either a list of edges; OR as a list of mappings from parent node to a list of child nodes); and produce, for EVERY node, a list of all nodes descended from it (leaf level and…
DVK
  • 3,576
  • 2
  • 24
  • 28
9
votes
1 answer

Menu building pattern

I'm having troubles getting my head around the active-state handling of a menu when the menu isn't used for routing. I come from Drupal where the menu system handles the routing as well. so setting active state and active-trail state is handled by…
Pinoniq
  • 538
  • 4
  • 9
8
votes
1 answer

Perform crossover operation on AST in genetic programming

So in general when you perform a crossover in GA, you directly flip a random section in the "genome", with the corresponding section in the other parent, and mutate it based on the mutation rate. Consider the sequences below: 0100 1000 0001…
Jordan LaPrise
  • 183
  • 5
7
votes
2 answers

some misunderstanding in concept of Huffman algorithm

What is difference between Average length of codes and Average length of codewords in Huffman Algorithm? is both the same meaning? I get stuck in some facts: I see a fact that marked as False: for a text that it's characters get from set of n…
Emma Nic.
  • 183
  • 5
7
votes
2 answers

How can one interpret an Abstract Syntax Tree without recursion?

I am busy building an interpreter for a Rebol-like language. I have previously built a Lisp interpreter where I used recursion, but now I just want to use a stack and not rely on the recursion capability of the host language. The parsing of the code…
mydoghasworms
  • 375
  • 2
  • 10
7
votes
2 answers

Is there a tree data structure with multiple root nodes?

I've read this post Name of data structure that's tree-like with multiple root nodes. What I'm asking for is not a forest. I would give you a simple example that easily depicts my case. You have a usual power source from EB and an inverter…
Vivek
  • 189
  • 1
  • 1
  • 6
7
votes
6 answers

How to represent a long if-else tree in a concise manner

Long story short, I've inherited a Java piece of code made of methods like this one: @Override public Action decide() { if (equalz(in.a, "LOC")) {//10 if(( //20 equalz(tmp.b, "BA") && notEquals(in.c,"U") …
Luigi Cortese
  • 399
  • 3
  • 9
1
2 3
…
10 11