三个题:

判断给定的二叉树是否是二叉排序树(方法1)

判断给定的二叉树是否是二叉排序树(方法2)

AVL树的判断

用到的adt我可以发给你们,主要是帮我写函数就好了,题目的描述在下面。

要能通过oj,函数部分能多写点注释就好了,谢谢。

判断给定的二叉树是否是二叉排序树(方法1)

问题描述 :

在二叉树的二叉链表存储形式建立的基础上,使用递归的程序设计方法,设计并完成判断一棵给定的二叉树是否是二叉排序树的算法。

初始条件:二叉树T。

操作结果:若T是二叉排序树,则返回true,否则返回false。

 

提示:

1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
3)它的左、右子树也分别为二叉排序树。

4)递归遍历,左孩子的key比根节点的key小,右孩子的key比根节点的key大,一旦有不满足条件的就判定不是。

 

参考函数原型:

//判断是否是二叉排序树 
template<class ElemType>
bool IsBST(BinaryTreeNode<ElemType> *root); //root为指向根结点的指针

 

输入说明 :

第一行:表示无孩子或指针为空的特殊分隔符

第二行:二叉树的先序序列(结点元素之间以空格分隔)

输出说明 :

第一行:二叉树的中序遍历结果

第二行:true(是二叉排序树)/false(不是二叉排序树)

输入范例 :

#

E B A # # D C # # # F # J G # I H # # # #

输出范例 :

A B C D E F G H I J

true

 

 

判断给定的二叉树是否是二叉排序树(方法2)

问题描述 :

在顺序表、二叉树的二叉链表ADT、冒泡排序的基础上,设计并完成判断一棵给定的二叉树是否是二叉排序树的算法。

初始条件:二叉树T。

操作结果:若T是二叉排序树,则返回true,否则返回false。

 

提示:

1)首先对二叉树T进行一次中序遍历,遍历结果存放在顺序表A中

2)针对顺序表A进行一趟冒泡排序。若交换标志不改变,则说明是一棵二叉排序树。

 

参考函数原型:

1)主函数:针对顺序表A进行一趟冒泡排序,判断是否是二叉排序树

template<class ElemType>
bool IsBST(SqList<ElemType> &A); //A为存放中序遍历结果的顺序表

 

2)辅助函数1

//重载二叉树的中序遍历(用户函数)

template<class ElemType>
bool InOrderTraverse(BinaryTree<ElemType> &T, SqList<ElemType> &A);

 

3)辅助函数2

//重写遍历的visit函数,将遍历结果依次存放在顺序表A中(为避免连锁改动,将函数名由visit改为visit1)

template<class ElemType>
bool visit1(BinaryTreeNode<ElemType> * root, SqList<ElemType> &A);

 

4)辅助函数3

//重载二叉树的中序遍历(成员函数)

bool InOrderTraverse( BinaryTreeNode<ElemType> *root, SqList<ElemType> &A, bool (*visit1)(BinaryTreeNode<ElemType> *root, SqList<ElemType> &A) ) const;

输入说明 :

第一行:表示无孩子或指针为空的特殊分隔符

第二行:二叉树的先序序列(结点元素之间以空格分隔)

 

输出说明 :

第一行:二叉树的中序遍历结果

第二行:true(是二叉排序树)/false(不是二叉排序树)

 

输入范例 :

#

E B A # # D C # # # F # J G # I H # # # #

输出范例 :

A B C D E F G H I J

true

 

AVL树的判断

问题描述 :

目的:设计并实现一个算法Judge_AVL,用来判断1棵给定的二叉排序树是否是平衡二叉树。

 

提示:

1)若一棵二叉排序树中每个结点的左、右子树的深度之差(平衡因子)的绝对值不超过1,则称这样的二叉树为平衡二叉树(AVL树)。

2)在小组任务12(13)的基础上,首先判断该二叉树是否是一棵二叉排序树。如不是,则可直接给出false(不是AVL树);如是,进入(3)

3)使用任意的遍历方式对该二叉树进行遍历(测试数据使用非递归的后序遍历得到),在visit函数中计算访问的结点的平衡因子。但要稍作修改(不需要通过数据元素的值,而是直接通过遍历到的结点地址来定位)。

4)如有结点的平衡因子的绝对值超过1,则可给出false;如所有结点的平衡因子的绝对值都不超过1,则可给出true。

 

参考函数原型:

1)判断是否是AVL树

template<class ElemType>
bool Judge_AVL(BinaryTree<ElemType> &T);

 

2)visit函数

template<class ElemType>
bool visit(BinaryTreeNode<ElemType> * root){
    int lheight, rheight, flag;    

    if(!root) return false; 
    else{

        cout<<root->data<<" ";
        lheight = GetBinaryTreeHeight_Cursive(root->LChild);
        rheight = GetBinaryTreeHeight_Cursive(root->RChild);
        flag = lheight - rheight;
        cout<<flag<<endl;     
        if( flag < -1 || flag > 1) return false; 
    }
    
    return true; 
}   

 

 

输入说明 :

第一行:表示无孩子或指针为空的特殊分隔符

第二行:二叉树的先序序列(结点元素之间以空格分隔)

 

输出说明 :

如不是AVL树,直接输出false

否则,按照后序遍历结点1的数据域的值 平衡因子(以空格分隔)

              (如遇到结点的平衡因子不在范围内,在下一行显示false,终止)

              (如所有结点的平衡因子都在范围内,在下一行显示true,终止)

 

输入范例 :

#

4 2 1 # # 3 # # 6 5 # # 7 # #

 

输出范例 :

1 0

3 0

2 0

5 0

7 0

6 0

4 0

true

 

代写计算机编程类/金融/高数/论文/英文


  u=199783060,2774173244&fm=58&s=188FA15AB1206D1108400056000040F6&bpow=121&bpoh=75.jpgalipay_pay_96px_533896_easyicon.net.pngpaypal_96px_533937_easyicon.net.pngchina_union_pay_96px_533911_easyicon.net.pngmastercard_pay_96px_533931_easyicon.net.pngasia_pay_96px_533902_easyicon.net.png

本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝或者Upwork交易!

E-mail:850190831@qq.com   微信:BadGeniuscs  工作时间:无休息工作日-早上8点到凌晨3点


如果您用的手机请先保存二维码到手机里面,识别图中二维码。如果用电脑,直接掏出手机果断扫描。

qr.png


编程类代写

C++/C

2018-01-13


判断给定的二叉树是否是二叉排序树(方法1) 判断给定的二叉树是否是二叉排序树(方法2) AVL树的判断 用到的adt我可以发给你们,主要是帮我写函数就好了,题目的描述在下面