如何知道二叉树是否为有序方案 [英] How to know if a binary tree is ordered scheme

问题描述

如果二叉树的所有子树都在左分支下，则将对其排序 正确年龄的根和分支的数据，然后是二叉树 左分支和右分支也进行排序.编写程序 (ordered-btree?btree)接收二叉树作为参数并返回 如果订购，则为True，否则为false.

A binary tree is ordered if all its children are under the left branch that the data of the root and branch of the right age and, in turn, binary trees of the left and right branches are also sorted. Write the procedure (ordered-btree? btree) receiving a binary tree as argument and returns True if ordered and false if not.

我该怎么做?

推荐答案

有几种方法可以解决此问题.我假设树中没有重复的元素，并且您编写了帮助程序来测试树是否为空，是否为叶(即，左子树和右子树都为空)，以返回左和右.正确的子树，每个节点中的值，树中的最小值和最大值-这些对于编写来说应该是微不足道的.第一个实现紧密遵循问题中提到的递归定义，但是效率不高:

There are several ways to solve this problem. I'll assume that there are no repeated elements in the tree and that you have written helper procedures for testing whether a tree is empty, whether it's a leaf (that is, both left and right subtrees are empty), for returning the left and right subtrees, the value in each node, the minimum value in a tree and the maximum - these should be trivial to write. The first implementation follows closely the recursive definition mentioned in the question, but it's not very efficient:

(define (ordered-btree? btree)
        ; if the tree is empty or is a leaf
  (cond ((or (is-empty? btree) (is-leaf? btree))
         ; then it's sorted
         true)
        ; else if the right subtree is empty
        ((is-empty? (right-tree btree))
         ; then test whether the current node's value is greater than
         ; the left subtree's maximum, and advance recursion over left
         (and (> (node-value btree) (max-value (left-tree btree)))
              (ordered-btree? (left-tree btree))))
        ; else if the left subtree is empty
        ((is-empty? (left-tree btree))
         ; then test whether the current node's value is less than
         ; the right subtree's minimum, and advance recursion over right
         (and (< (node-value btree) (min-value (right-tree btree)))
              (ordered-btree? (right-tree btree))))
        ; otherwise if both subtrees are non-empty
        (else                           
         ; then perform the same tests as above for both subtrees
         (and (> (node-value btree) (max-value (left-tree btree)))
              (< (node-value btree) (min-value (right-tree btree)))
              (ordered-btree? (left-tree btree))
              (ordered-btree? (right-tree btree))))))

第二种方法是使用按顺序遍历，然后检查返回的列表是否已排序.这是一个更有效的解决方案，我将对其进行概述-再次假设已建立适当的帮助程序:

A second approach would be to obtain a list of the tree's values using an in-order traversal, and then check if the returned list is sorted. This is a more efficient solution, I'll outline it - once again assuming that the proper helper procedures are in place:

(define (ordered-btree? btree)
  (is-sorted?         ; check whether a list of values is sorted
   (inorder-traversal ; return the in-order traversal of a tree as a list
    btree)))          ; a binary search tree

这篇关于如何知道二叉树是否为有序方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！