课堂上跟老师小争论了一下,确实是自己写的判断算法有问题。一直闭门造车了,有时候适当的上网找一下资料会事半功倍的。恩……
二叉排序树很重要的一个概念是整个左(右)子树都小于(大)于根,符合这个条件的才是真正的二叉排序树。之前的算法一是证明根的值与左右节点的值符合关系,这是错误的。
具体一想就可以明白……
最简单的算法,就是中序遍历了。闲话少说,代码为证:
#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;
}
分享到:
相关推荐
//该程序用于判断二叉树是否为二叉排序树
一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;...3.通过函数判断是否为一颗二叉排序树
写一算法,判断一棵二叉树是否是一棵二叉排序树。
说明: 可实现:构造树,插入,查找,删除. 通过模式的选择,可以插入值相等的点.但是不建议使用.
判别给定二叉树是否为二叉排序树
基于二叉排序树的二叉树建立
现在大二,学数据结构,实验可写的程序,希望大家会喜欢
数据结构实验课,关于判断二叉树是不是二叉排序树》》》》》
二叉搜索树(二叉排序树)它的每个节点的数据结构为1个父节点指针,1个左孩子指针,1个有孩子指针,还有就是自己的数据部分了,因为只有左右两孩子,所以才叫二叉树,在此基础上,该二叉树还满足另外一个条件:每个结点的左...
而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关: ①在最坏情况下,二叉排序树是通过把一个有序表的n个结点依次插入而生成的,此时所得的二叉排序树蜕化为棵深度为n的单支树,它的平均查找长度和...
创建二叉排序树;判断一颗二叉树是否为二叉排序树;完整代码和PPT演示
1,动态创建二叉排序树 2,输出二叉排序树 3.判断是否为二叉排序树 4.输出查找某元素的路径 5.删除特定关键字结点
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
二叉排序树 二叉查找树 前序遍历 中序遍历 后序遍历 根节点 算法: 1. 找到根节点 2. 遍历序列,找到第一个大于根节点的元素i,则i左侧为左子树,右侧为右子树 3. 判断i右侧的节点是否都比根节点大,如果有比根节点...
首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树;或者是具有下列性质的二元树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有...
今天小编就为大家分享一篇用Python实现二叉树、二叉树非递归遍历及绘制的例子,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧