{"id":1808,"date":"2012-03-07T08:52:40","date_gmt":"2012-03-06T21:52:40","guid":{"rendered":"http:\/\/blog.mozilla.org\/nnethercote\/?p=1808"},"modified":"2012-03-07T08:52:40","modified_gmt":"2012-03-06T21:52:40","slug":"n-ary-trees-in-c","status":"publish","type":"post","link":"https:\/\/blog.mozilla.org\/nnethercote\/2012\/03\/07\/n-ary-trees-in-c\/","title":{"rendered":"N-ary trees in C"},"content":{"rendered":"

If you want to implement an N-ary tree of integers in C, the obvious way to represent each node is something like the following.<\/p>\n

struct t {\r\n    int n;\r\n    int numKids;\r\n    struct t **kids;\r\n}<\/pre>\n
Here kids<\/code> is an array of kid pointers.\u00a0 Here’s an example tree.<\/p>\n
\"N-ary<\/a><\/p>\n
This representation is a bit annoying because the kids<\/code> array must be allocated separately from the node, and you need to reallocate the kids<\/code> array every time you add a new kid to a node. Alternatively, you could instead over-allocate in anticipation of more nodes being added, but then you have to record the array capacity within the node.\u00a0 (The latter representation is exactly what I used for the tree of stack traces in Massif<\/a>.)<\/p>\n
While reading through the code for trace-malloc<\/a> yesterday, I learnt a better representation.<\/p>\n
struct t {\r\n    int n;\r\n    struct t *kids;\r\n    struct t *siblings;\r\n}<\/pre>\n
This looks odd at first.\u00a0 Here’s the example tree with this new representation.<\/p>\n
\"N-ary<\/a><\/p>\n
From any single node you can only directly access its first kid, through the kids<\/code> pointer. You access the second kid through kids->siblings<\/code>, the third kid through kids->siblings->siblings<\/code>, and so on.\u00a0 In other words, instead of storing a node’s kids in an array, you store them in a list; it just so happens that this list can be embedded elegantly in the nodes themselves. (There’s an argument to be made that the fields should be called firstKid<\/code> and nextSibling<\/code>, though I can see the sense in both naming schemes.)<\/p>\n
There are several nice things about this representation.<\/p>\n