Hot answers tagged

47

The short answer is that you use stacks. This is a good example, but I'll apply it to an AST. FYI, this is Edsger Dijkstra's Shunting-Yard Algorithm. In this case, I will use an operator stack and an expression stack. Since numbers are considered expressions in most languages, I'll use the expression stack to store them. class ExprNode: char c ...


27

Here is a general purpose tree traversal implementation that doesn't use recursion: public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector) { var stack = new Stack<T>(); stack.Push(item); while (stack.Any()) { var next = stack.Pop(); yield return next; ...


20

A parse tree is also known as a concrete syntax tree. Basically, the abstract tree has less information than the concrete tree. The concrete tree contains each element in the language, whereas the abstract tree has thrown away the uninteresting pieces. For example the expression: (2 + 5) * 8 The concrete looks like this ( 2 + 5 ) * 8 | \ | / | | |...


19

There is a significant difference between how an AST is typically depicted in test (a tree with numbers/variables at the leaf nodes and symbols at interior nodes) and how it is actually implemented. The typical implementation of an AST (in an OO language) makes heavy use of polymorphism. The nodes in the AST are typically implemented with a variety of ...


17

There's a couple simple categories you can fit graphs into that makes it easier to classify them. Directed: This is a graph wherein you have parent-child relations that are one way, that is the child may not directly reference the parent Undirected: This is a graph wherein you have node-node relations, they are not parent-child and may go either way Acyclic:...


17

You are looking for a kind of Directed Acyclic Graph (DAG). These graphs do not have a root node. However, the nodes have a partial order. I.e. when we look at two nodes we can sometimes tell which node is “higher”. In your example, we could say that power sources are higher than meters which are higher than consumers. Trees are a special kind of DAG where ...


16

A tree is a connected acyclic graph. In the case where we have "parent" links this would just be an undirected tree, but definitely still a tree. If you were to specify that the example is a directed graph it would not be considered a tree (but of course there's no way of telling from the code which was intended). Some computer science "trees" will include, ...


10

It is up to the visitor implementation to decide whether to visit child nodes and in which order. That's the whole point of the visitor pattern. In order to adapt the visitor for more situations it is helpful (and quite common) to use generics like this (it's Java): public interface ExpressionNodeVisitor<R, P> { R visitNumber(NumberNode number, P ...


10

The indentation in the code is important: if uncle.color == red: # Handle case else if z == z.p.right: # Handle case 2 # Handle case 3 The syntax is a bit quirky, because they squished the if to appear on the same line as the else, but case 2 is indented further inward compared to the remaining case 3, indicating that they do not belong ...


9

Trees are Graphs. They are specifically directed, acyclic graphs where all child nodes only have one parent. If you need more than one parent then you use a DAG. If you need cycles or the graph needs to be undirected you'd use some kind of graph implementation. Note that the time and space complexity increases dramatically once you move into full graphs.


9

pre order traversal is a traversal, it visits every node in a binary tree Depth First Search is a search, it goes around an arbitrary graph looking for a certain node (that it works best in a non cyclic graph (a.k.a. tree) is irrelevant) this alone is a large enough difference to call them difference names


9

Building the AST from the source text is "simply" parsing. How exactly it is done depends upon the parsed formal language and the implementation. You could use parser generators like menhir (for Ocaml), GNU bison with flex, or ANTLR etc etc. It is often done "manually" by coding some recursive descent parser (see this answer explaining why). The contextual ...


8

A tree is a special kind of graph. More specifically, it's "any connected graph without simple cycles". So, your graph is a tree. It doesn't matter if it grows or not. Yours is a directed graph so it doesn't really matter anyways. It's not a binary tree, if that's what you were asking =)


8

This heavily depends on definition of list and tree. Mathematically list doesn't mean anything and tree is just special subset of a graph. Inferring from your question, your teacher's definition of tree is nested lists. In which case, list of nesting depth of 0 is still a tree. So abc = [1, 2, 3, 4] Is a tree. In this case, the list is subset of tree. ...


7

The following algorithm should do almost what you've asked for. paths : List<String> ;; your list of paths tree : Folder = NEW Folder("") FOREACH path IN paths DO node : Folder = tree FOREACH component IN split(path, "/") DO next : Folder = node.getChild(component) IF next IS NULL THEN next := NEW Folder(...


7

I wouldn't go with the matrix idea. While it is less code, I don't see it as being any more readable. If anything, I think it's harder to read because I can't mentally evaluate one thing and then disregard half the code left in the method. I have to check everything. I would start by just working on reducing nesting. For example, looking at the ...


6

If your trees are isomorphic on principle, there is no point at all in actually maintaining three parallel trees - that's just a waste of pointers and processor cycles. instead you should define a composite type that holds what ever items you want to maintain in parallel, and build one tree containing such composite nodes. Remember, how you access or present ...


6

I have implemented the visitor pattern on a recursive tree before. My particular recursive data structure was extremely simple - just three node types: the generic node, an internal node that has children, and a leaf node that has data. This is much simpler than I expect your AST to be, but perhaps the ideas can scale. In my case I deliberately did not ...


6

Your solution seems to try to tackle average reading time of nodes and all paths from them. This will, of course, work, provided it's properly implemented. The problem with this approach is that the quantities you calculate are not reusable. The average reading time of a node depends on how you got to it. Hence the quadratic behaviour of your naive solution....


6

Binary trees are the most common kind of trees, but ternary trees also pop up sometimes. For generalized trees with (up to) k childs per node, the term k-ary tree (or n-ary tree) is used.


6

TreeSet is based on TreeMap, which is a Red-Black Tree implementation. Red-Black Trees are self-balancing binary search trees that guarantee O(log n) performance for search, insert and delete operations.


6

Robert Harvey is right, your problem can be solved in an elegant manner by memoization. However, since the paper of the article he mentioned seems not to be available any more, I try to give you a short explanation how this should work. Lets say A is an input variable, and B, C, and D calculations with memoized values mB, mC and mD. These values can either ...


6

Min-Max search (with or without ABP) is not supposed to "build the complete search tree" in memory. It is usually implemented as Depth First Search tree traversal, which traverses the complete search tree, but does not store it completely. In fact, at each point in time, there is only one node per level required in memory, so the memory usage is actually ...


5

By Wikipedia, it looks like your tree is specified by the two properties arborescence and ordered tree (scroll down to find the definition "ordered tree or plane tree.")


5

Unlike a plain binary tree, AVL trees are self-balancing. When an element is inserted into an AVL tree, the tree may need to perform node rotations in order to maintain a certain tree depth, which allows for logarithmic lookup time. So, if you try to build a second AVL tree using pre-order node traversal on an existing AVL tree, the resulting tree will not ...


5

Proof by induction: Every acyclic graph can be represented as a tree, if all the nodes are connected. So let's think about trees. You've got one root node. Let's look at the simplest, case, in which the tree only has one branch, and so it's a simple linked list. If there are two nodes, there's one edge between them. Add one node to the end of the ...


5

For me, the big advantage of the heterogeneous AST is that it forms a kind of forced, annotated switch statement (assuming a C-like language). For the homogeneous AST you usually end up with some kind of routine or class with a big switch statement. You need to keep track of which child node is what yourself. "First child is the conditional, second the true-...


5

I like to use the word Primary in situations where the word First isn't quite right, but is close. It indicates that it's special in some way, without actually depending on an ordered enumeration. First implies a Second, Third and so on, but Primary could be paired with everything else or Secondary, Tertiary, and only then everything else. Given an ...


5

I don't believe there is a special name for this, it's simply a tree. "Growing in both directions" is purely an artifact of how you drew the tree. Also, it's a little hard to tell from your ASCII art, but if the top and bottom are connected and you have cycles, then this is technically not a tree at all, but a graph (of which trees are a more specific case)....


Only top voted, non community-wiki answers of a minimum length are eligible