• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(11.3)检查二分搜索树性质和平衡性

极客笔记 Geekerstar 10个月前 (07-11) 351次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

检查二分搜索树性质和平衡性

这一小节我们再来做一个辅助工作,设置两个函数来判断当前的这个树是不是二分搜索树,同时是不是平衡二叉树。

对于AVL树来说,它是对二分搜索树的一个改进,改进的是二分搜索树有可能退化成链表这种情况,因此引入了平衡因子的概念。

AVL树要保证每个节点中左右子树的差不超过1,但是要注意AVL树同时也是一个二分搜索树,所以也要满足二分搜索树的性质(每一个节点左子树的值要小于这个节点的值,右子树的值要大于这个节点的值)。

后续在添加AVL树这个自平衡机制的时候,如果代码里有问题,很有可能会打破这个性质。所以我们来设置一个函数可以方便我们检查AVL树是不是依然是一棵二分搜索树。

代码实现

 // 判断该二叉树是否是一棵二分搜索树
 public boolean isBST(){

     ArrayList<K> keys = new ArrayList<>();
     inOrder(root, keys);
     for(int i = 1 ; i < keys.size() ; i ++)
         if(keys.get(i - 1).compareTo(keys.get(i)) > 0)
             return false;
     return true;
 }

 private void inOrder(Node node, ArrayList<K> keys){

     if(node == null)
         return;

     inOrder(node.left, keys);
     keys.add(node.key);
     inOrder(node.right, keys);
 }

 // 判断该二叉树是否是一棵平衡二叉树
 public boolean isBalanced(){
     return isBalanced(root);
 }

 // 判断以Node为根的二叉树是否是一棵平衡二叉树,递归算法
 private boolean isBalanced(Node node){

     if(node == null)
         return true;

     int balanceFactor = getBalanceFactor(node);
     if(Math.abs(balanceFactor) > 1)
         return false;
     return isBalanced(node.left) && isBalanced(node.right);
 }

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(11.3)检查二分搜索树性质和平衡性
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00