如何用C语言编写算法判断一棵二叉树是否为二叉搜索树？

本文共计1497个文字，预计阅读时间需要6分钟。

原文：本文字例讲述了C语言中判断一棵二叉树是否为二叉搜索树的方法。分享给广大读者，供大家参考，具体如下：

问题：给定一棵二叉树，判断该二叉树是否为二叉搜索树（Binary Search Tree）？解法：

本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法。分享给大家供大家参考，具体如下：

问题

给定一棵二叉树，判定该二叉树是否是二叉搜索树（Binary Search Tree）？

解法1:暴力搜索

首先说明一下二叉树和二叉搜索树的区别。二叉树指这样的树结构，它的每个结点的孩子数目最多为2个；二叉搜索树是一种二叉树，但是它有附加的一些约束条件，这些约束条件必须对每个结点都成立：

• 结点node的左子树所有结点的值都小于node的值。
• 结点node的右子树所有结点的值都大于node的值。
• 结点node的左右子树同样都必须是二叉搜索树。

该问题在面试中也许经常问到，考察的是对二叉搜索树定义的理解。初看这个问题，也许会想这样来实现：

假定当前结点值为k。对于二叉树中每个结点，判断其左孩子的值是否小于k，其右孩子的值是否大于k。如果所有结点都满足该条件，则该二叉树是一棵二叉搜索树。

很不幸的是，这个算法是错误的。考虑下面的二叉树，它符合上面算法的条件，但是它不是一棵二叉搜索树。