博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
判断一棵二叉树是否为AVL树
阅读量:7214 次
发布时间:2019-06-29

本文共 1127 字,大约阅读时间需要 3 分钟。

思路:AVL树是高度平衡的二叉搜索树,这里为了清晰说明,分别判断是否为搜索树,是否为平衡树。

struct TreeNode{    struct TreeNode *left;    struct TreeNode *right;    int key;};//这里先判断是否为二叉搜索树,其次判断是否为平衡的bool IsAVL(TreeNode *root,int depth){    if (isBST(root)&&isBalance(root,&depth))    return true;    return false;}//判断是否为二叉搜索树bool isBST(TreeNode *root){    if(root == NULL)return true;    if (!isBST(root->left))return false;    if (!isBST(root->right))return false;    TreeNode *cur = root->left;    if (cur != NULL)    {        while(cur->right!=NULL)cur = cur->right;        if(root->key < cur->key)return false;    }    TreeNode *cur = root->right;    if (cur != NULL)    {        while(cur->left!=NULL)cur = cur->left;        if(root->key > cur->key)return false;    }    return true;}//判断是否平衡bool isBalance(TreeNode *root,int *depth){    if (root == NULL)    {        *depth = 0;        return true;    }    int depthl,depthr;    if(!isBalance(root->left,&depthl))return false;    if(!isBalance(root->right,&depthr))return false;    int diff = depthl - depthr;    if(diff > 1 || diff < -1)return false;    *depth = 1+(depthl>depthr?depthl:depthr);    return true;}

 

转载地址:http://wquym.baihongyu.com/

你可能感兴趣的文章
SpringCloudSpringBootmybatis分布式微服务云架构-hystrix参数详解
查看>>
(一)spring cloud微服务分布式云架构-Spring Cloud简介
查看>>
百家笔记网为什么选择采用读书笔记为博客写作主题?
查看>>
如果需要精确的答案,请避免使用float 和 double(48)
查看>>
假如高考考python编程,这些题目你会几个呢?
查看>>
计算机网络学习整理:Http协议
查看>>
单用户模式和救援模式
查看>>
ActiveMQ从入门到精通(一)
查看>>
时序数据库连载系列:指标届的独角兽Prometheus
查看>>
Vue slot的用法
查看>>
VS的Release模式下进行调试的VS修改和cmake修改
查看>>
利用NEO与Unity制作游戏(第2部分)
查看>>
microSD推新卡Express传输速度可达985MBps
查看>>
Java B2B2C多用户商城 springboot架构 (五)springboot整合 beatlsql
查看>>
面向对象
查看>>
linux:ubuntu安装mysql
查看>>
提升搬砖效率的神兵利器
查看>>
《Think in Java》读书笔记
查看>>
Ubuntu下安装samba
查看>>
iOS核心动画笔记4-图形几何学
查看>>