Created
August 25, 2011 09:29
-
-
Save fundon/1170314 to your computer and use it in GitHub Desktop.
Binary tree in JavaScript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function cons(x, y) { | |
| return function(w) { return w(x, y) }; | |
| }; | |
| function car(z) { | |
| return z(function(x, y) { return x }); | |
| }; | |
| function cdr(z) { | |
| return z(function(x, y) { return y }); | |
| }; | |
| function make_tree(entry, left, right) { | |
| return cons(entry, cons(left, cons(right, null))); | |
| } | |
| function entry(tree) { | |
| return car(tree); | |
| } | |
| function left_branch(tree) { | |
| return car(cdr(tree)); | |
| } | |
| function right_branch(tree) { | |
| return car(cdr(cdr(tree))); | |
| } | |
| /** assumes binary search tree **/ | |
| function element_of_set(value, tree) { | |
| if (!tree) return false; | |
| var current = entry(tree); | |
| if (current == value) return true; | |
| if (current > value) return element_of_set(value, left_branch(tree)); | |
| return element_of_set(value, right_branch(tree)); | |
| } | |
| /** make a simple binary search tree **/ | |
| var tree = make_tree(4, | |
| make_tree(2, | |
| make_tree(1, null, null), | |
| make_tree(3, null, null)), | |
| make_tree(6, | |
| make_tree(5, null, null), | |
| make_tree(7, null, null))); | |
| document.writeln(element_of_set(7, tree)); | |
| document.writeln(element_of_set(3.5, tree)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment