判断二叉树是否为二叉排序树的算法_如何判断一颗二叉树是否是二叉搜索树？...

鉴于二叉搜索树做中序遍历之后得到的序列是严格单调递增的，所以最简单的方法当然是先对二叉树做中序遍历，然后对得到的序列进行有序性判断。这个方法唯一的缺点是效率不好：它需要遍历每个节点的值两次（至少一次），并且需要

的辅助空间。

对这中序遍历的方法稍作修改，目标是当遇到某个节点违反二叉搜索树的性质时就返回False，并且消除高达

的辅助空间的利用。

一个简单的办法是在进行中序遍历时，只保留一个最大值（当前已经遍历过节点的最大值）。在遍历开始的时候，该最大值被初始化为负无穷（或者树节点类型的最小值）。之后按照中序遍历的顺序处理每一个节点，当某个节点的值不满足条件（也就是比已经遍历过的节点的最大值要大）的时候，就中断遍历返回False，否则用当前节点的值更新最大值。直到遍历完整棵二叉树，返回True。

这样我们就达到了提升算法效率的目的，并将算法所需的辅助空间降低到

。

编码实现

想必用C、Java等命令式语言实现该算法是挺简单的，因为我们可以将最大值的更新与中序遍历算法的实现分离开来。但是如果限制对变量的值进行修改，实现这个算法就稍微需要一点技巧了。下面是某个Racket子语言（一个Racket语言不完整的实现，不支持赋值操作）的版本

(define-struct node [left value right])
(define-struct leaf [value])
; A [BT X Y] is one of:
; - (make-leaf Y)
; - (make-node [BT X Y] X [BT X Y])
; Interpretation: A [BT X Y] represents a binary tree with values _X_ at each
; node and values _Y_ at each leaf.
; Note: that a [BT X Y] may not be a binary search tree.

;           0
;          / 
;        100  -3
;            /  
;           5   100

; [BT Number String] -> Boolean
(define (is-bt-a-bst?/inorder bt)
  (cond
    [(node? bt) (number? (inorder-travel-compare bt))]
    [(leaf? bt) #false]))

; [BT Number String] -> [Maybe Number]
(define (inorder-travel-compare bt)
  (local ((define -inf (tan (/ pi -2)))
          (define (inorder-travel root m)
            (cond
              [(node? root)
               (let ((m (inorder-travel (node-left root) m))
                     (v (node-value root)))
                 (cond
                   [(and (number? m) (< m v))
                    (inorder-travel (node-right root) v)]
                   [(number? m) (list v m)]
                   [else (cons v m)]))]
              [(leaf? root) m])))
         ((lambda (x) (if (number? x) x (reverse x)))
          (inorder-travel bt -inf))))

另外一种算法，是使用前缀遍历的方式。

它的原理是：在获取当前节点的值之后，我们就知道了它的左子树和右子树各自的值域。比如，从根节点开始，假设它的值为

，于是我们就可以知道其左子树的值域

，右子树的值域为

。之后，在下降到各子树的过程中，根据行走的方向（左子树向左，右子树向右），不断调整值域，并判断遇到的节点的值是否处在达到那个位置时动态调整出来的值域的范围内。如果不在，那么这个节点就违反了二叉搜索树的性质，返回

False；如果一棵树的所有的节点都处在达到它的位置时动态调整出来的值域中，那么这棵树就是一棵二叉搜索树，返回 True。

编码实现

;           4
;          / 
;         2   17
;        /|   | 
;       s 3  15 19
;        /|  /   |
;       s s s   s s s
; ; [BT Number String] -> Boolean
(define (is-bt-a-bst? bt)
  (local (; Number -> Number -> [BT Number String] -> Boolean
          (define (in-range? minval maxval root)
            (cond
              [(node? root)
               (let ((value (node-value root)))
                 (and (< minval value) (< value maxval)
                      (in-range? minval value (node-left root))
                      (in-range? value maxval (node-right root))))]
              [(leaf? root) #true])))
     (cond
       [(node? bt)
        (let ([-inf (tan (/ pi -2))]
              [value (node-value bt)]
              [+inf (tan (/ pi +2))])
          (and (in-range? -inf value (node-left bt))
               (in-range? value +inf (node-right bt))))]
       [(leaf? bt) #false])))

原文链接：https://blog.csdn.net/weixin_39863161/article/details/111372232