二进制搜索树到列表方案 [英] Binary Search Tree To List Scheme

问题描述

我在理解如何使用BST并将其转换为列表而不使用附加或任何高级技术时遇到了麻烦.例如，为您提供了一个BST，每个节点都有一个数字和名称(按从最小到最大的字符串排序)，并且您想要按顺序输出该BST中值为3或类似值的项目的列表.这些行.

I am having trouble understanding how to take in a BST and convert it into a list without using append or any advanced techniques. For example, you are given a BST with each node having a number and a name (sorted by string smallest to largest) and you want to output a list, in order, of the items in that BST with a value of 3 or something along these lines.

我知道这可以递归完成，但是我认为了解这一点的最大问题与左右节点的拆分有关，因为您在这两个节点上都使用了递归，但是您必须以某种方式将它们放在一起在最终列表中.

I understand this can be done recursively but I think my biggest problem with understanding this has to do with the splitting of the left and right nodes, because you are using recursion on both of these but then you somehow have to put them together in the final list.

感谢您对任何理解的帮助，在此先感谢您.

Any help in understanding this is appreciated, thank you in advance.

推荐答案

因此，假设您有一个值为(1 2 3 4)的二叉树.您知道不能cons 1放开已经有(2 3 4)等的东西，因此实际上您需要反向积累它们.

So imagine you have a binary tree with the values (1 2 3 4). You know that you cannot cons 1 unles you already have (2 3 4) etc. so actually you need to accumulate them in reverse.

在二叉搜索树中，遍历的左侧是左侧，此值右侧将使用cons创建列表，右侧将在此节点左侧.

In a binary search tree in order traversal is left side, this value, right side så making a list using cons would be doing right side, this node, left side.

(define (tree->list tree)
  (let rec ((tree tree) (lst '()))
    (if (tree-null? tree)
        lst
        (rec (tree-left tree)
             (cons (tree-value tree)
                   (rec (tree-right tree) lst))))))

它可能看起来不像首先在右侧进行操作，但是请记住，过程在应用自身之前需要先评估其参数.

It might not look like it does the right side first, but remember that a procedure needs to have evaluated it's arguments before itself can be applied.

没有提到如何实现树的数据结构，所以我只是做了一些程序.最终结果真的无关紧要.

How you have implemented the data structure for your tree is not mentioned so I just made some procedures up. It really doesn't matter for the end result.

这篇关于二进制搜索树到列表方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！