课堂上跟老师小争论了一下,确实是自己写的判断算法有问题。一直闭门造车了,有时候适当的上网找一下资料会事半功倍的。恩……
二叉排序树很重要的一个概念是整个左(右)子树都小于(大)于根,符合这个条件的才是真正的二叉排序树。之前的算法一是证明根的值与左右节点的值符合关系,这是错误的。
具体一想就可以明白……
最简单的算法,就是中序遍历了。闲话少说,代码为证:
#include<iostream.h>
typedef struct node
{
int data;
struct node *left, *right;
}NODE,*BSTree;
//递归判断二叉树是否为排序树,leftbound,rightbound位左右界限,即最小最大值
bool judge(NODE *p, int leftbound, int rightbound)
{
if (p==NULL)
return true;
if (p-> data <= leftbound || p-> data >= rightbound)
return false;
if (!judge(p-> left,leftbound,p-> data))
return false;
if (!judge(p-> right, p-> data,rightbound))
return false;
return true;
}
//扩展的前序遍历结果建立二叉树
void PreOrderCreate(BSTree &T)
{
int data;
BSTree NewNode;
cin>>data;
if(data==0)
return;
NewNode=new NODE;
T=NewNode;
T->left=NULL;
T->right=NULL;
T->data=data;
PreOrderCreate(T->left);
PreOrderCreate(T->right);
}
//中序遍历二叉树
void InOrderTraverse(BSTree &T)
{
if(T==NULL)
return;
InOrderTraverse(T->left);
cout<<T->data<<" ";
InOrderTraverse(T->right);
}
void main()
{
BSTree BStree=NULL;
PreOrderCreate(BStree);
cout<<"The tree already built!"<<endl;
cout<<endl<<"Inorder sort:"<<endl;
InOrderTraverse(BStree);
cout<<endl;
if(judge(BStree,0,20))
cout<<"Yes! this is binary sort tree!"<<endl;
else
cout<<"No! this is not binary sort tree!"<<endl;
}
分享到:
相关推荐
判别给定二叉树是否为二叉排序树
通过以上分析,我们可以看出无论是递归还是非递归的方法,都能够有效地解决判断二叉树是否为二叉排序树的问题。递归方法虽然简洁易懂,但可能会导致较大的递归深度;而非递归方法虽然稍微复杂一些,但能够有效地控制...
//该程序用于判断二叉树是否为二叉排序树
3. **判断二叉树是否为二叉排序树**:通过`judge()`函数实现。该函数接收中序遍历得到的数组`B`作为参数,检查数组中的元素是否严格递增。如果数组中的所有元素都是递增的,则说明原二叉树满足二叉排序树的定义,...
二叉排序树(Binary Sort Tree,BST),也称为二叉搜索树,是一种特殊的二叉树数据结构,它的每个节点都包含一个键(key)、一个关联的值、一个指向左子节点的指针和一个指向右子节点的指针。在二叉排序树中,对于...
数据结构课程设计-判别给定的二叉树是否为二叉排序树 本课程设计的主要目的是设计一个判别给定的二叉树是否为二叉排序树的程序,通过建立一棵二叉树及判定二叉树的过程来实现该功能。下面是该设计的详细知识点: 1...
一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;...3.通过函数判断是否为一颗二叉排序树
现在大二,学数据结构,实验可写的程序,希望大家会喜欢
接着,判断一棵二叉树是否为二叉排序树,可以通过递归检查每个节点是否满足上述二叉排序树的性质。对于每个节点,我们需要确保它的左子树中的所有节点的值都小于它,右子树中的所有节点的值都大于它,并且它的左右...
然后,我们将实现IsBST函数,该函数用于判断一个二叉树是否为二叉排序树。如果当前节点的左子树不为空且左子树的关键字大于或等于当前节点的关键字,或者右子树不为空且右子树的关键字小于当前节点的关键字,则返回0...
**判断二叉树是否为二叉排序树的伪代码**: ```python def is_bst(node, min_value=float('-inf'), max_value=float('inf')): if node is None: return True if node.value < min_value or node.value > max_...
**二叉排序树问题**是数据结构课程设计中常见的一个课题,旨在让学生深入理解并实践二叉树、查找表的逻辑结构和存储结构。在这个任务中,学生需要设计一个程序来实现二叉排序树的基本操作,同时提升自身的编程能力和...
二叉排序树(Binary Sort Tree,BST),也称为二叉搜索树,是一种特殊的二叉树数据结构,它的每个节点都包含一个键值,且满足以下性质:对于任意节点,其左子树中所有节点的键值均小于该节点的键值;其右子树中所有...
综上所述,这些知识点涵盖了静态查找表的定义与线性查找、折半查找及其递归实现、判断二叉树是否为二叉排序树的方法以及递归输出二叉排序树中满足条件的数据元素。通过对这些算法的理解和实践,可以帮助学生深入掌握...
本课设的目标是编写一个程序,判断给定的二叉树是否满足这一特性,即是否为二叉排序树。为简化问题,我们限定树中节点的关键字各不相同,并采用二叉链表作为存储结构。设计中需提供正反两组测试用例,确保程序的正确...
而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关: ①在最坏情况下,二叉排序树是通过把一个有序表的n个结点依次插入而生成的,此时所得的二叉排序树蜕化为棵深度为n的单支树,它的平均查找长度和...
- **定义**:二叉排序树是一种特殊的二叉树结构,其中每个节点都具有以下特性: - 节点的左子树只包含键值小于该节点的节点。 - 节点的右子树只包含键值大于该节点的节点。 - 左右子树也各自是二叉排序树。 二叉...
二叉排序树,也称为二叉搜索树,是一种特殊类型的二叉树,它的每个节点都遵循以下规则: 1. 左子树中的所有节点的值都小于当前节点的值。 2. 右子树中的所有节点的值都大于当前节点的值。 3. 左右子树也必须是二叉...
二叉排序树(Binary Search Tree),也称作二叉查找树或有序二叉树,是一种特殊的二叉树数据结构。它具有以下性质: 1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 2. 若任意节点的右子树...