4 ms·
I like using a level-order traversal because it makes your indexing very simple. For a binary tree you start with 1 and each node has children 2 * i and 2 * i +
by ball_of_lint 8y ago
I like using a level-order traversal because it makes your indexing very simple. For a binary tree you start with 1 and each node has children 2 * i and 2 * i + 1, and parent i / 2. You can do a inorder/preorder/postorder traversal using the typical methods, but for a level-order traversal all you need to do is walk through the backing array.
This also generalizes to k-trees. Start at node k-1. your children are ((i - k + 2) * k) through ((i - k + 2) * k) + (k - 1), and your parent is ((i / k) - 2 + k) with integer division. Once again this all fits nicely into a flat backing array and requires no extra memory to store children or parents.
- deleted 8y ago[deleted]
- mlthoughts2018 8y agoThis assumes some type of array-backed tree, rather than a pointer / node implementation. In that case, level order usually requires pushing child nodes onto a queue or something similar, which I personally always find tedious by comparison to simpler traversals.
- rsc 8y agoI agree, this is a great representation - I think of it as the heap ordering - but it assumes a fixed-height tree. For my use case, I want to overlay increasingly large trees (with leaves appended to the right side) to a linear array, so heap order is a non-starter.