当前位置: 首页 > 编程笔记 >

C语言判定一棵二叉树是否为二叉搜索树的方法分析

郭兴文
2023-03-14
本文向大家介绍C语言判定一棵二叉树是否为二叉搜索树方法分析,包括了C语言判定一棵二叉树是否为二叉搜索树的方法分析的使用技巧和注意事项,需要的朋友参考一下

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

问题

给定一棵二叉树,判定该二叉树是否是二叉搜索树(Binary Search Tree)?

解法1:暴力搜索

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

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

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

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

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

     10
   /  \
  5   15     -------- binary tree (1)
     /  \
    6    20

那么,根据二叉搜索树的定义,可以想到一种暴力搜索的方法来判定二叉树是否为二叉搜索树。

假定当前结点值为k。则对于二叉树中每个结点,其左子树所有结点的值必须都小于k,其右子树所有结点的值都必须大于k。

暴力搜索算法代码如下,虽然效率不高,但是它确实能够完成工作。该解法最坏情况复杂度为O(n^2),n为结点数目。(当所有结点都在一边的时候出现最坏情况)

/*判断左子树的结点值是否都小于val*/
bool isSubTreeLessThan(BinaryTree *p, int val)
{
 if (!p) return true;
 return (p->data < val &&
     isSubTreeLessThan(p->left, val) &&
     isSubTreeLessThan(p->right, val));
}
/*判断右子树的结点值是否都大于val*/
bool isSubTreeGreaterThan(BinaryTree *p, int val)
{
 if (!p) return true;
 return (p->data > val &&
     isSubTreeGreaterThan(p->left, val) &&
     isSubTreeGreaterThan(p->right, val));
}
/*判定二叉树是否是二叉搜索树*/
bool isBSTBruteForce(BinaryTree *p)
{
 if (!p) return true;
 return isSubTreeLessThan(p->left, p->data) &&
     isSubTreeGreaterThan(p->right, p->data) &&
     isBSTBruteForce(p->left) &&
     isBSTBruteForce(p->right);
}

一个类似的解法是:对于结点node,判断其左子树最大值是否大于node的值,如果是,则该二叉树不是二叉搜索树。如果不是,则接着判断右子树最小值是否小于或等于node的值,如果是,则不是二叉搜索树。如果不是则接着递归判断左右子树是否是二叉搜索树。(代码中的maxValue和minValue函数功能分别是返回二叉树中的最大值和最小值,这里假定二叉树为二叉搜索树,实际返回的不一定是最大值和最小值)

int isBST(struct node* node)
{
 if (node==NULL) return(true);
 //如果左子树最大值>=当前node的值,则返回false
 if (node->left!=NULL && maxValue(node->left) >= node->data)
  return(false);
 // 如果右子树最小值<=当前node的值,返回false
 if (node->right!=NULL && minValue(node->right) <= node->data)
  return(false);
 // 如果左子树或者右子树不是BST,返回false
 if (!isBST(node->left) || !isBST(node->right))
  return(false);
 // 通过所有测试,返回true
 return(true);
}

解法2:更好的解法

以前面提到的binary tree(1)为例,当我们从结点10遍历到右结点15时,我们知道右子树结点值肯定都在10和+INFINITY(无穷大)之间。当我们遍历到结点15的左孩子结点6时,我们知道结点15的左子树结点值都必须在10到15之间。显然,结点6不符合条件,因此它不是一棵二叉搜索树。该算法代码如下:

int isBST2(struct node* node)
{
   return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
给定的二叉树是BST则返回true,且它的值 >min 以及 < max.
*/
int isBSTUtil(struct node* node, int min, int max)
{
   if (node==NULL) return(true);
   // 如果不满足min和max约束,返回false
   if (node->data<=min || node->data>=max) return(false);
   // 递归判断左右子树是否满足min和max约束条件
   return
     isBSTUtil(node->left, min, node->data) &&
     isBSTUtil(node->right, node->data, max)
   );
}

由于该算法只需要访问每个结点1次,因此时间复杂度为O(n),比解法1效率高很多。

解法3:中序遍历算法

因为一棵二叉搜索树的中序遍历后其结点值是从小到大排好序的,所以依此给出下面的解法。该解法时间复杂度也是O(n)。

bool isBSTInOrder(BinaryTree *root)
{
 int prev = INT_MIN;
 return isBSTInOrderHelper(root, prev);
}
/*该函数判断二叉树p是否是一棵二叉搜索树,且其结点值都大于prev*/
bool isBSTInOrderHelper(BinaryTree *p, int& prev)
{
 if (!p) return true;
 if (isBSTInOrderHelper(p->left, prev)) { // 如果左子树是二叉搜索树,且结点值都大于prev
  if (p->data > prev) { //判断当前结点值是否大于prev,因为此时prev已经设置为已经中序遍历过的结点的最大值。
   prev = p->data;
   return isBSTInOrderHelper(p->right, prev); //若结点值大于prev,则设置prev为当前结点值,并判断右子树是否二叉搜索树且结点值都大于prev。
  } else {
   return false;
  }
 }
 else {
  return false;
 }
}

希望本文所述对大家C语言程序设计有所帮助。

 类似资料:
  • 我有一个很严重的问题,就是在一棵树中重复搜索子树。 我试过了,但是。。。 似乎没有正确的形式。containsTree函数在找到与另一个节点不同的节点时停止搜索。 下面是两棵树的例子。 在这种情况下,当函数比较右边的子树和左边的子树时,当find等于父节点但它有不同的子节点时,它会停止搜索。我需要函数不要停止搜索,而是抛出这一点,搜索所有其他子节点及其子树。

  • 我写了一个函数,如果给定的二叉树是二叉搜索树,则返回true,否则返回false。 我的功能对吗?

  • 编写一个Lisp程序来检查一个二叉树是否是二叉搜索树。 我正在尝试编写一个二进制递归方法,但我是一个初学者,我不知道从这里去哪里。

  • 我正试图解决这个问题,但我遇到了一些麻烦: 在二进制搜索树(BST)中: 节点左子树中每个节点的数据值小于该节点的数据值。 节点右侧子树中每个节点的数据值大于该节点的数据值。 如您所见,节点(4)位于节点(3)的左侧子树中,尽管4大于3,因此方法应该返回。但是,我的代码返回。 我怎么能控制这个案子?如何检查左/右子树中的所有值都低于/大于根(不仅是直接子树)?

  • 树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: 树有多个节点(node),用以储存元素。某些节点之间存在一定的关系,用连线表示,连线称为边(edge)。边的上端节点称为父节点,下端称为子节点。树像是一个不断分叉的树根。 每个节点可以有多个子节点(children),而该节点是相应子节点的父节点(parent)。比如说,3,5是6的子节点,6是3,