[scheme学习笔记]二叉树的遍历
将二叉树的节点定义为
(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语言写出来是个麻烦的东西.指针满天飞..
2022年9月03日 01:33
Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. PSC Result 2022 dinajpur BoardThe DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.