The Way 2 Inner Peace.

[scheme学习笔记]scheme中的快速排序和合并排序
尾递归改写为递归

[scheme学习笔记]二叉树的遍历

Qians posted @ 2011年11月12日 01:52 in scheme with tags Scheme 算法 lisp 递归 数据结构 二叉树 , 1984 阅读

 

将二叉树的节点定义为
(define-struct node (number value left right))
则树的定义数据定义是
binary-tree(简称BT)是下列两者之一
1. false;
2. (make-node num value lft rgt),
其中 num是数,value是符号,lft 和rgt 是BT。
 
 
则如图的二叉树可以表示为
(define BT1 (make-node 63 'a
                       (make-node 29 'b
                                  (make-node 15 'c
                                             (make-node 10 'd false false)
                                             (make-node 24 'e false false)) false)
                       (make-node 89 'f
                                  (make-node 77 'g false false)
                                  (make-node 95 'h false
                                             (make-node 99 'i false false)))))
(define BT2 (make-node 63 'a
                       (make-node 29 'b
                                  (make-node 15 'c
                                             (make-node 87 'd false false)
                                             (make-node 24 'e false false)) false)
                       (make-node 89 'f
                                  (make-node 33 'g false false)
                                  (make-node 95 'h false
                                             (make-node 99 'i false false)))))
 
如果从左到右读出这两棵树中的数.可以得到两个序列
其中数A是按照升序排列的.将有序排列的二叉树称为二叉搜索树.
接下来开发函数inorder.中序遍历.该函数读入一棵二叉树,返回树中所有number数组成的表。该表以
从左到右的顺序(上图顺序)列出这些数.
 
;;inorder:BT->list
(define (inorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (inorder (node-left BT))
      (list (node-ssn BT))
      (inorder (node-right BT))))))
中序遍历按照左根右的顺序进行历遍.即首先遍历左子树,然后访问根结点,最后遍历右子树.在遍历左,右子树时.仍然先遍历左子树,再访问根结点,最后遍历右子树
 
而前序遍历按照根左右的顺序进行遍历.
后续遍历按照左右根的顺序进行遍历.
同理即可得到前序遍历和后续遍历的函数.
(define (preorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (list(node-ssn BT))
      (preorder (node-left BT))
      (preorder (node-right BT))))))
(define (postorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (postorder (node-left BT))
      (postorder (node-right BT))
      (list(node-ssn BT))))))
 
可以发现对二叉搜索树来说.中序遍历返回的是有序排列的表.
 
 
 
ps.写个博客都要翻墙.蛋疼死啊..
ps2.用递归的函数写递归的数据结构真是太清晰了.感觉就是C语言写出来是个麻烦的东西.指针满天飞..

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter