StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The following should work. It takes care of the subtrees one by one.</p> <pre><code>let mark bst = let rec number = function | (x, I a) -> (x+1, I x) | (x, Node(a, b, c)) -> let p1 = number (x,b) in let p2 = number ((fst p1),c) in ((fst p2),Node(a,(snd p1), (snd p2))) in snd (number (0,bst)) </code></pre> <p>Here is what I got when running it on your example. Honestly, it's the only example I have tried, though.</p> <pre><code># let tr = Node("a", Node("b", I 25, I 54), Node("c", I 12, I 47));; val tr : btree = Node ("a", Node ("b", I 25, I 54), Node ("c", I 12, I 47)) # markit tr;; - : btree = Node ("a", Node ("b", I 0, I 1), Node ("c", I 2, I 3)) </code></pre> <p><strong>Explanation of the code:</strong> To label each leaf uniquely in ascending order, left to right, you have to look at each subtree, one at the time. After looking at the left subtree, you need to know how far you have come in the labelling-process, i.e. what the next label is. To do obtain this ability, my function <code>number</code> returns a pair of type <code>int * btree</code>, whereas yours return a <code>btree</code>. The <code>int</code> in the pair is the next unused label. Returning a pair, allows us to have two return-values. Clever!</p> <p>I suppose you understand the first two lines, since they are identical to yours (almost - remember to use <code>let rec</code> when defining recursive functions). Within the function <code>mark</code> the <code>number</code> function is initiated in the last line - just like in your code as well. The difference is that, instead of giving the function two input-values, as you do, I give it one; a pair of values. In the end, though, all we want is the second entry in the pair, which we extract by using <code>snd</code>. In lines 3-4, we check if we are looking at an integer or a node (i.e. a leaf or a subtree). Note that accordig to your type definition, these two cases are the only possibilities. If we are looking at a node, we will need to traverse the left subtree firstly, which happens in line 5. After traversing the righ subtree, we still need to pass the next unused label down to the parent node, which is why we need line 6. In line 7, the return-pair is assembled.</p> <p>Wow. That became quite lenghty. But I hope it clearified things somewhat. If not, please ask again!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload