c# - Algorithm to reorder a tree structure -

i have tree this:

    abcdef    /      \   abc      def  /   \    / | \    bc  d  e  f     /  \    b    c 

what algorithm bring following form?

          abcdef          /     \         abcde   f        /    \       abcd   e      /    \     abc    d    /   \   bc     /  \ b    c 

edit:
idea first take b. node makes operation c bc.
use bc , make operation a abc.
continue upwards...

i not able find documentation on that.

background:
try use filter expression. expression may contain multiple tokens connected operator.

i use following class that:

public class filternode {     // node information     filternode next;      bool match(...) { ... } } 

the goal node able perform binary operation this , next.

so seems what's important here order nodes depth, , original order left right.

since didn't define node class, used following mine:

public class node {     public node()     {         children = new list<node>();     }     public string value { get; set; }     public list<node> children { get; set; } } 

the first thing want create method traverse tree. need of leaf nodes (without of non-leaf nodes) , want know depth of each node. it's simple enough modify traditional traversal algorithm accordingly:

public static ienumerable<tuple<node, int>> traverseleaveswithdepth(node root) {     var queue = new queue<tuple<node, int>>();     queue.enqueue(tuple.create(root, 0));      while (queue.any())     {         var next = queue.dequeue();         foreach (var child in next.item1.children)         {             queue.enqueue(tuple.create(child, next.item2 + 1));         }          if (!next.item1.children.any())             yield return next;     } } 

now breadth first search, means in reverse order of depth, we'll fix later.

now use create new tree. can take results of our previous method , order depth (descending) items want in order want them.

from there iterate results taking each leaf, pairing it's previous node, , creating new parent represent pair (and using parent new "previous" node).

public static node straighten(node root) {     var nodes = traverseleaveswithdepth(root)         .orderbydescending(pair => pair.item2)         .select(pair => pair.item1);      using (var iterator = nodes.getenumerator())     {         if (!iterator.movenext())             return null;          var previous = iterator.current;          while (iterator.movenext())         {             var next = iterator.current;             var parent = new node();             parent.value = new string(previous.value                 .asenumerable().concat(next.value)                 .orderby(c => c)                 .toarray());              parent.children.add(previous);             parent.children.add(next);              previous = parent;         }          return previous;     } } 

the actual construction of nodes differ based on implementation of node (and may want re-create leaves, rather referencing old ones, did).