October 15, 2006

Scheme数据结构——简单二叉树


终于把用Scheme写的二叉树发出来了,前两天网卡没钱拉。

层序例遍算法写出来了,可惜用不了——没法儿用Scheme实现队列!我折腾了半天,写出这么一个怪物:
(define queue list)
(define (queue-push! q o)
(set-cdr! (list-tail q (- (length q) 1)) (cons o null)))

可pop还是实现不了——不知道怎么删除pair,于是放弃。
把简单二叉树的实现贴在这儿吧,虽然没有一点实用价值。

(define null '()) ;用null代替空list

(define (child data left right) ;用它来申明一个“孩子”
(cons data (cons left right)))
(define (child? o)
(and (pair? o) (pair? (cdr o))))
(define (child.data o)
(if (child? o)
(car o)))
(define (set-child.data! o data)
(if (child? o)
(set-car! o data)))
(define (child.left o)
(if (child? o)
(cadr o)))
(define (set-child.left! o p)
(if (child? o)
(set-car! (cdr o)) p))
(define (child.right o)
(if (child? o)
(cddr o)))
(define (set-child.right! o p)
(if (child? o)
(set-cdr! (cdr o) p)))

;先序例遍递归版,用一句(if (not (null? o)...)省了不少判断
(define (child-tree-pre o func)
(if (not (null? o))
(begin
(func (child.data o))
(child-tree-pre (child.left o) func)
(child-tree-pre (child.right o) func))))
;后序例遍
(define (child-tree-post o func)
(if (not (null? o))
(begin
(child-tree-post (child.left o) func)
(child-tree-post (child.right o) func)
(func (child.data o)))))
;。。。中序~~可怜没有层序和分步例遍~~
(define (child-tree-mid o func)
(if (not (null? o))
(begin
(child-tree-mid (child.left o) func)
(func (child.data o))
(child-tree-mid (child.right o) func))))

1 comment:

Anonymous said...

[url=http://vtyupdr.com]KXBGrwfw[/url] - NvtkahAlIi - http://iluubcb.com