判断一棵二叉树是否是二叉排序树,可以通过中序遍历来检查,为此要设置一个指针pr指示二叉树中当前结点的中序直接前驱,每访问一个结点,就比较当前访问结点的关键值是否大于ptr所指结点的关键字值,如果遍历了所有结,各结点与其中序直接前驱点都 是后一个大于前一个,则为二叉排序树。
void binSearchTree(BSTree root,BSTree &ptr,int &bs){
//引用ptr是当前子树根结点root的前驱结点指针,开始时bs为1,如果bs为0则表示非二叉排序树
if(root!=NULL&&bs)
{
binSearchTree( root->lchild,ptr,bs);
if(ptr==NULL) {
ptr = root;
}else {
if(root->data>ptr->data)
{
ptr = root;
bs = 1;
} else bs = 0;
}
printf("the vlaue of ptr %d \n" ,ptr->data);
if(bs)binSearchTree( root->rchild,ptr,bs);
}
}
这是一个递归过程,有时间写一个非递归的程序
分享到:
相关推荐
写一算法,判断一棵二叉树是否是一棵二叉排序树。
一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;...3.通过函数判断是否为一颗二叉排序树
判别给定二叉树是否为二叉排序树
数据结构实验课,关于判断二叉树是不是二叉排序树》》》》》
//该程序用于判断二叉树是否为二叉排序树
现在大二,学数据结构,实验可写的程序,希望大家会喜欢
说明: 可实现:构造树,插入,查找,删除. 通过模式的选择,可以插入值相等的点.但是不建议使用.
而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关: ①在最坏情况下,二叉排序树是通过把一个有序表的n个结点依次插入而生成的,此时所得的二叉排序树蜕化为棵深度为n的单支树,它的平均查找长度和...
1,动态创建二叉排序树 2,输出二叉排序树 3.判断是否为二叉排序树 4.输出查找某元素的路径 5.删除特定关键字结点
创建二叉排序树;判断一颗二叉树是否为二叉排序树;完整代码和PPT演示
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
第一章 1.1数据结构课程设计要求。...其中二叉树节点由1个表示关键 字的key表示,还有指向该左孩子和右孩子的指针,通过key<p- >key的if语句来判断,其中p表示二叉排序树。 2.2.1系统功能的设计。 本程序设置了5个
(5)判断二叉排序树T是否为平衡二叉树,输出信息“OK!”/“NO!”; *(6)再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT; *(7)...
基于二叉排序树的二叉树建立
(1)输入字符序列,建立二叉链表。 (2)遍历二叉树输出。 (3)请设计一个算法,要求该算法把... (5)试写一算法判断某二叉树是否是二叉排序树。 (6)在主函数中设计一个简单的菜单,分别调试上述算法。
(1)输入字符序列,建立二叉链表。 (2)遍历二叉树输出。 (3)请设计一个算法,要求该算法把二叉树的...(5)试写一算法判断某二叉树是否是二叉排序树。 (6)在主函数中设计一个简单的菜单,分别调试上述算法。
2. 编程题:输入n个两两互不相等的整数,以这些整数为关键字建立平衡的二叉排序树。判断该二叉树是否为平衡的,输出判断结果;输出该二叉树的中序遍历关键字访问次序。 3. 从空树起连续插入以下20个关键字构建m=4的B...
二叉搜索树(二叉排序树)它的每个节点的数据结构为1个父节点指针,1个左孩子指针,1个有孩子指针,还有就是自己的数据部分了,因为只有左右两孩子,所以才叫二叉树,在此基础上,该二叉树还满足另外一个条件:每个结点的左...
1 实验一 1.1 实验环境与工具: ...(4) 判断二叉树是否为二叉排序树 (5) 输出中序遍历序列的结果 (6) 计算叶子结点数 (7) 计算二叉树深度 2 实验二:窗体应用程序设计 等等,已做好工程文件,可以直接运行
一、基本题 1. 一元多项式的表示和相加(链表、建立、相加、输出) 2. 表达式括号匹配检验(压栈、出栈) 3.... (3) 判断该二叉树是否为二叉排序树。 (4) 如果是二叉排序树,进行结点的插入或