foreach DFS/BFS for tree data-structure?
Steven Schveighoffer
schveiguy at yahoo.com
Thu Jun 14 12:55:55 UTC 2018
On 6/14/18 8:35 AM, Robert M. Münch wrote:
> On 2018-06-14 11:46:04 +0000, Dennis said:
>
>> On Thursday, 14 June 2018 at 11:31:50 UTC, Robert M. Münch wrote:
>>> Is this possible? I read about Inputranges, took a look at the RBTree
>>> code etc. but don't relly know/understand where to start.
>>
>> You can also use opApply to iterate over a tree using foreach, see:
>> https://tour.dlang.org/tour/en/gems/opdispatch-opapply
>
> Ah... that looks very good. Need to dig a bit deeper on how to use it.
> Thanks.
>
Just to clarify, RBTree can easily do DFS without a real stack because
there are a finite number of children (2) for each node, and it's an
O(1) operation to figure out which child the current node is in relation
to the parent (am I a left child or right child?).
Now, with your C version, if your children are stored in the array
itself, figuring out the "next" child is a matter of doing &this + 1.
But if you are storing pointers instead, then figuring out the next
child would be an O(n) operation.
Using the stack to track where you are (via opApply) is a valid way as
well. You could also unroll that into a malloc'd stack, but the code is
not as pretty of course.
-Steve
More information about the Digitalmars-d-learn
mailing list