;Impliementing tree. and thus binary searching..... ;Checks whether the given node is a leaf... (define (leaf? tree) (if (and (null? (left-branch tree) (null? right-branch tree))) #t #f ) ) ;Checks wheter the tree has only left branch (define (left-only? tree) (if (and (null? (right-branch tree)) (not (null? (left-branch tree)))) #t #f ) ) ;Checks wheter the tree has only left branch (define (right-only? tree) (if (and (null? (left-branch tree)) (not (null? (right-branch tree)))) #t #f ) ) ;When node, left branch and right branch of the tree are passed as arguements, ;the function will make and return the tree (define (make-tree node left-branch right-branch) (list node left-branch right-branch) ) ;This function returns the node element of a given tree (define (node tree) (car tree) ) ;This function returns the left branch(subtree) of a given tree (define (left-branch tree) (cadr tree) ) ;This function returns the right branch(subtree) of a given tree (define (right-branch tree) (caddr tree) ) ;This function will insert an element into a tree and returns the new tree (define (insert e tree) (cond ((null? tree) (make-tree e '() '()));If the passed tree is null then a new tree of the form (e '() '()) ;will be created ((= e (node tree)) tree) ; If the node of the element is eqaual to the elemented to be inserted ; Then there is no need for inserting and the previous tree will be returned. ;If the element is greater than the node element, then the element shud be inserted ;somewhere in the right-branch ((> e (node tree)) (make-tree (node tree) (left-branch tree) (insert e (right-branch tree))) ) ;If the element is greater than the node element, then the element shud be inserted ;somewhere in the left-branch ((< e (node tree)) (make-tree (node tree) (insert e (left-branch tree)) (right-branch tree)) ) ) ) ;This function is called to make a tree from a given list.. ;It will call the function set->tree2 with cdr of set and a new tree with root node (car set) as arguement (define (set->tree set) (if (null? set) '() (set->tree2 (cdr set) (make-tree (car set) '() '())) ) ) ;This functon will extract each element of set and insert it into the given tree (define (set->tree2 set tree) (if (null? set) tree (set->tree2 (cdr set) (insert (car set) tree)) ) ) ;Searching an element in a binary search tree.. (define (search-tree e tree) (cond ((null? tree) #f) ; If the set is null result is boolean false ((= (node tree) e) #t) ; If the node of tree equals e, the result is true ((> e (node tree)) (search-tree e (right-branch tree))); if e is greater than node element, it shud be searched in right-branch ((< e (node tree)) (search-tree e (left-branch tree))) ; if e is lesser than node element, it shud be searched in right-branch ) ) ;The function which user calls for searching element in a set, ;It will call the functions make the set to a binary search tree and then to perform binary search (define (search e set) (search-tree e (set->tree set)) ) ;Inserting tree1 into ertreme right of tree2(function used while deletion...).. (define (join-trees tree1 tree2) (if (null? tree2) tree1 (make-tree (node tree2) (left-branch tree2) (join-trees tree1 (right-branch tree2))) ) ) ;Function to delete an element from a tree.. (define (delete e tree) (if (null? tree) '() ;If the tree is not null then.... (cond ((= e (node tree)) (cond ((leaf? tree) '() ) ((left-only? tree) (left-branch tree) ) ((right-only? tree) (right-branch tree) ) (else (join-trees (right-branch tree) (left-branch-tree) ) ) ) ) ((> e (node tree)) (make-tree (node tree) (left-branch tree) (delete e (right-branch tree)) ) ) ((< e (node tree)) (make-tree (node tree) (delete e (left-branch tree)) (right-branch tree) ) ) ) ) ) ;function for sorting.. (define (sort-tree tree) (if (null? tree) '() (append (sort-tree (left-branch tree)) (list (node tree)) (sort-tree (right-branch tree))) ) ) (define (tree-sort set) (sort-tree (set->tree set)) ) (define mylist (list 7 4 9 1 2 10 11 15 5)) (define mytree (set->tree mylist)) ;mytree
Wednesday, February 22, 2012
Binary Search Tree in Scheme
Subscribe to:
Post Comments (Atom)
can you please tell how to give the input
ReplyDeletePlease check the two function calls given in the end of that program:
Delete(define mylist (list 7 4 9 1 2 10 11 15 5))
(define mytree (set->tree mylist))
The first one will create a list from the given elements and assign that to the variable mylist.
Using the second one we are creating a binary search tree out of mylist using the function set->tree and we are assigning that to mylist.
You can insert other elements using insert function as
(define mylist (insert 5 mylist) )
In a similar way you can try other functions as well...