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

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

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

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

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

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

代码实现

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

     ArrayList 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 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);
 }

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(11.3)检查二分搜索树性质和平衡性

Leave a Reply