Recursive mapping of trees

Question

Recently, I worked a lot with the implementation of the tree and how we present and understand trees. My attention was focused on turning mathematical expressions into binary trees, I posed the problem of representing the tree in a linear form by saying a string or array, while preserving important information about the tree and its under the trees.

As such, I developed a very simple encoding for binary expression trees. However, I have some problems with the effectiveness of its implementation in a recursive estate, this, apparently, is one of the missing aspects of the concept.

The encoding is simple if the node is located as the left child, it is assigned card 1, if it is as the right child, it is assigned the value 0. This simple encoding allows me to encode all balanced and unbalanced trees, for example this:

## ## / \ / \ 1 0 OR 1 0 / \ / \ / \ 11 10 01 00 01 00 

Etc to trees of depth N

Does anyone have any suggestions on how to create a recursive function that would create a prefix string representing a match of this kind (e.g. ## 1 11 10 0 01 00).

I was told that it will be difficult / impossible due to the fact that you need to monitor the rotation between 1 and 0, while maintaining and concatenating the value of the parent.

I was wondering if anyone has any ideas or ideas how to do this using C #?

Answer 1

I'm not sure I understand your problem, but here is something that might help. One solution may be to implement a graph traversal procedure on the graph (remember that Tree is a specialized graph), where the visit occurs when the node / vertex is first received. I apologize for submitting Java code when you requested C #, but I know that Java ...

 public void depthFirstSearch(Graph graph, Vertex start){ Set<Vertex> visited = new HashSet<Vertex>(); // could use vertex.isVisited()... Deque<Vertex> stack = new ArrayDeque<Vertex>(); // stack implies depth first // first visit the root element, then add it to the stack so // we will visit it children in a depth first order visit(start); visited.add(start); stack.push(start); while(stack.isEmpty() == false){ List<Edge> edges = graph.getEdges(stack.peekFirst()); Vertex nextUnvisited = null; for(Edge edge : edges){ if(visited.contains(edge.getEndVertex)) == false){ nextUnvisited = edge.getEndVertex(); break; // break for loop } } if(nextUnvisited == null){ // check the next item in the stack Vertex popped = stack.pop(); } else { // visit adjacent unvisited vertex visit(nextUnvisited); visited.add(nextUnvisited); stack.push(nextUnvisited); // visit it "children" } } } public void visit(Vertex vertex){ // your own visit logic (string append, etc) } 

You can easily change this to be the first breadth-first search, using Deque as a queue instead of a stack as follows:

 stack.pop() >>>> queue.removeFirst() stack.push() >>>> queue.addLast() 

Note that for this purpose, the Graph and Edge classes support the following operations:

 public interface Graph { ... // get edges originating from Vertex v public List<Edge> getEdges(Vertex v); ... } public interface Edge { ... // get the vertex at the start of the edge // not used here but kind of implied by the getEndVertex()... public Vertex getStartVertex(); // get the vertex at the end of the edge public Vertex getEndVertex(); ... } 

Hope this gives you some ideas.

Answer 2

Well, I don’t know if I completely asked your question, but it looks like you need to bypass the preposition for the tree. I do not know the syntax of C #, but the pseudocode that I think will be as follows:

 preorder_traversal(node) if(node != NULL) print(node) preorder_traversal(left_sub_child) preorder_traversal(right_sub_child) else return 

Answer 3

Building a tree recursively is a difficult task even for an experienced programmer. I understand that I'm a little late to the party on this issue, given that it was originally published in March 2011. Better late than never?

One important factor when creating a tree is simply to make sure your dataset is properly formatted. You just need a way to associate a parent with a child. Once the association is clearly defined, you can start coding the solution. I decided to use a simple format:

 ParentId ChildId 1 2 1 3 2 4 3 5 

Etc.

Once this relationship is established, I developed a recursive method for iterating over the dataset to build the tree.

First, I identify all the parent nodes and store them in the collection, giving them each unique identifier using a combination of the parent identifier and the child identifier:

  private void IdentifyParentNodes() { SortedList<string, MyTreeNode> newParentNodes = new SortedList<string,MyTreeNode>(); Dictionary<string, string> parents = new Dictionary<string, string>(); foreach (MyTreeNode oParent in MyTreeDataSource.Values) { if (!parents.ContainsValue(oParent.ParentId)) { parents.Add(oParent.ParentId + "." + oParent.ChildId, oParent.ParentId); newParentNodes.Add(oParent.ParentId + "." + oParent.ChildId, oParent); } } this._parentNodes = newParentNodes; } 

Then the root invocation method will go through the parents and invoke the recursive method to build the tree:

 // Build the rest of the tree foreach (MyTreeNode node in ParentNodes.Values) { RecursivelyBuildTree(node); } 

Recursive Method:

 private void RecursivelyBuildTree(MyTreeNode node) { int nodePosition = 0; _renderedTree.Append(FormatNode(MyTreeNodeType.Parent, node, 0)); _renderedTree.Append(NodeContainer("open", node.ParentId)); foreach (MyTreeNode child in GetChildren(node.ParentId).Values) { nodePosition++; if (IsParent(child.ChildId)) { RecursivelyBuildTree(child); } else { _renderedTree.Append(FormatNode(MyTreeNodeType.Leaf, child, nodePosition)); } } _renderedTree.Append(NodeContainer("close", node.ParentId)); } 

Method used to get the children of the parent:

 private SortedList<string, MyTreeNode> GetChildren(string parentId) { SortedList<string, MyTreeNode> childNodes = new SortedList<string, MyTreeNode>(); foreach (MyTreeNode node in this.MyTreeDataSource.Values) { if (node.ParentId == parentId) { childNodes.Add(node.ParentId + node.ChildId, node); } } return childNodes; } 

Not that sophisticated or elegant, but he did his job. It was written in 2007, so this is old code, but it still works. :-) Hope this helps.