c# - tree data structure with data contained in leaf nodes and all other nodes having just a node name

Question

Need to implement a 3-level tree with labels for levels 1 and 2 and data in level 3. Need to be able to add nodes, remove nodes, traverse, and search. How would you implement it?

Could a regular tree with two data slots for node name and node data work? i.e. for all the leaf nodes the node name would be blank and node data would be filled, and vice versa for the non-leaf nodes. I feel like this would be a bit wasteful of memory though.

标签： c#data-structures

Answer 1

I feel like this would be a bit wasteful of memory though.

Agreed. Coming from an assembly language programming background decisions like these troubled me a lot :)

However, here definition of wasteful depends upon two factors -

1. How much data you are talking about
2. Where are you planning to run the program (Laptop/Mobile/RPi/low memory embedded system/...)

For simplicity lets consider node data is of type int(32 bits). Now to fill even 100 KB of memory you'll need have 25,600 entries in your tree.

Now if we talk about not wasting any memory, then we will end up writing two set of nodes, one with only node name and one with only node data. And more code to add nodes, remove nodes, traverse, and search.

I hope this answers your query.