Given A List of Branches, How to Find a List of Tree List That Are Singly Connected Together

Let's say I have a list of branches, how to find a list of tree li开发者_StackOverflow社区st that are singly connected together? The below diagram should illustrate my point. The input is a list of branches in a single tree, as labeled, ie. 1, 2, 3 and so on

---

The process is as follows:

1. Create a function that accepts a tree node as a parameter
2. If the node has no children, print the value of the current node and return.
3. If the node has two children, end the current list of single node values, then recurse into the left node, then the right node
4. If the node has one child, add it to the list of values contained in the tree, then recurse into that node.
5. Continue.

---

According to image, there is a really simple solution. Let's make a list, with elements, that are lists of the same type. Procedure will be called tree_lists(list, tree). All you need to do is:

1. Looking at current joint, you have your list pointer on the first element of list.
2. If there are more than one child in current node: iterate through each subtree, incrementing list pointer and calling
   tree_lists(list[i],current_subtree) where i is list pointer and current_subtree is current subtree =)
3. If ony one child exists, just add this joint to the current list item and move on to next.
4. Of course, list pointer and list values must be somehow global and modified in recurion as well.