关于平衡二叉树的构建 清疚 2022-02-19 09:39 146阅读 0赞 ## 构建平衡二叉树 ## 最近在玩数据结构搞到平衡二叉树部分觉得平衡二叉树的构建,分享一下自己的二叉树构建: **首先是树的节点的构建:** public class BalanceNode { private int value; BalanceNode leftBalanceNode; BalanceNode rightBalanceNode; public BalanceNode(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public void add(BalanceNode balanceNode) { if (balanceNode == null) { return; } //如果添加的节点在左边 if (balanceNode.value < this.value) { if (this.leftBalanceNode == null) { this.leftBalanceNode = balanceNode; } else { this.leftBalanceNode.add(balanceNode); } //添加的节点在右边 } else { if (this.rightBalanceNode == null) { this.rightBalanceNode = balanceNode; } else { this.rightBalanceNode.add(balanceNode); } } //判断是否平衡把树搞成平衡二叉树 //首先是左边的比右边的高 搞成右旋转 System.out.println(leftHeight()+"---------"+rightHeight()); if (leftHeight() - rightHeight() >= 2) { //如果出现左子树的右子树比左子树的左子树要高 双旋转 if (leftBalanceNode != null && leftBalanceNode.leftHeight() < leftBalanceNode.rightHeight()) { //先让小左子树左旋转 然后让大左子树右旋转 leftBalanceNode.leftRoate(); rightRoate(); } else { rightRoate(); } } if (rightHeight() - leftHeight() >= 2) { if (rightBalanceNode != null && rightBalanceNode.leftHeight() > rightBalanceNode.rightHeight()) { //先让小左子树左旋转 然后让大左子树右旋转 rightBalanceNode.rightRoate(); leftRoate(); } else { leftRoate(); } } } //左旋转方法 private void leftRoate() { BalanceNode node = new BalanceNode(this.value); node.leftBalanceNode = this.leftBalanceNode; node.rightBalanceNode = this.rightBalanceNode.leftBalanceNode; this.value = this.rightBalanceNode.value; this.rightBalanceNode = this.rightBalanceNode.rightBalanceNode; this.leftBalanceNode = node; } //右旋转方法 private void rightRoate() { BalanceNode node = new BalanceNode(this.value); node.rightBalanceNode = this.rightBalanceNode; node.leftBalanceNode = this.leftBalanceNode.rightBalanceNode; this.value = this.leftBalanceNode.value; this.leftBalanceNode = this.leftBalanceNode.leftBalanceNode; this.rightBalanceNode = node; } //定义一个取树的高度的方法 public int height() { return Math.max(leftBalanceNode == null ? 0 : leftBalanceNode.height(), rightBalanceNode == null ? 0 : rightBalanceNode.height())+ 1; } //获取左子树的高度 public int leftHeight() { if (leftBalanceNode == null) { return 0; } return leftBalanceNode.height(); } //获取右子树的高度 public int rightHeight() { if (rightBalanceNode == null) { return 0; } return rightBalanceNode.height(); } public void midlShow() { if (this.leftBalanceNode != null) { this.leftBalanceNode.midlShow(); } System.out.println(this.value); if (this.rightBalanceNode != null) { this.rightBalanceNode.midlShow(); } } public BalanceNode search(int value) { if (this.value == value) { return this; } else { if (this.value > value) { //对左右为空进行判断 if (this.leftBalanceNode == null) { return null; } return this.leftBalanceNode.search(value); } else { if (this.rightBalanceNode == null) { return null; } return this.rightBalanceNode.search(value); } } } **接下来是树的创建:** public class BalanceBinaryTree { private BalanceNode root; public void add(BalanceNode balanceNode) { if (root == null) { root = balanceNode; } else { root.add(balanceNode); } } public void midlShow() { if (root != null) { root.midlShow(); } } public BalanceNode search(int value) { if (root == null) { return null; } else { return root.search(value); } } public void delete(int value) { if (root == null) { return; } else { BalanceNode t = search(value); if (t == null) { return; } else { BalanceNode target = searchParent(value); // System.out.println(target.getValue()); if (target == null) { return; } else { //判断如果被删除的节点为叶子节点 if (t.leftBalanceNode == null && t.rightBalanceNode == null) { //如果被删除的节点为左节点 if (target.leftBalanceNode.getValue() == t.getValue()) { target.leftBalanceNode = null; //被删除的节点为右节点 } else { target.rightBalanceNode = null; } //被删除节点有两个子树 } else if (t.leftBalanceNode != null && t.rightBalanceNode != null) { int i = delmin(t.rightBalanceNode); t.setValue(i); //被删除节点有一个子树 } else { //如果有一颗左子树 if (t.leftBalanceNode == target) { //如果被删除的节点为左节点 if (target.leftBalanceNode.getValue() == t.getValue()) { target.leftBalanceNode = null; //被删除的节点为右节点 } else { target.rightBalanceNode = null; } //有一棵右子树 } else { //如果被删除的节点为左节点 if (target.leftBalanceNode.getValue() == t.getValue()) { target.leftBalanceNode = null; //被删除的节点为右节点 } else { target.rightBalanceNode = null; } } } } } } } public BalanceNode searchParent(int value) { if (root == null) { return null; } else { return root.searchParent(value); } } private int delmin(BalanceNode balanceNode) { BalanceNode target = balanceNode; while (target.leftBalanceNode != null) { target = target.leftBalanceNode; } //递归调用删除方法 delete(target.getValue()); return target.getValue(); } public int height() { return root.height(); } 这样就创建了一棵平衡二叉树,具体的测试方法就不展示了,可以自行造假数据然后测试。
相关 平衡二叉树 <table style="width:1615px; margin-bottom:20px; background-color:transparent"> <tbody> 淡淡的烟草味﹌/ 2022年06月02日 07:59/ 0 赞/ 224 阅读
相关 平衡二叉树 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. 墨蓝/ 2022年05月28日 08:57/ 0 赞/ 392 阅读
相关 平衡二叉树 写在前面 > 剑指offer:平衡二叉树 题目要求 > 输入一棵二叉树,判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。 浅浅的花香味﹌/ 2022年05月17日 01:54/ 0 赞/ 265 阅读
相关 平衡二叉树 平衡二叉树又称AVL树。它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定 骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 237 阅读
相关 平衡二叉树 时间限制:1秒 空间限制:32768K 热度指数:160212 [ 算法知识视频讲解][Link 1] 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 向右看齐/ 2022年03月08日 01:44/ 0 赞/ 282 阅读
相关 平衡二叉树 平衡二叉树介绍 是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出,因此一般也称作AVL树,AVL树本质还是一棵二叉查找树,只是在其基础 青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 321 阅读
相关 关于平衡二叉树的构建 构建平衡二叉树 最近在玩数据结构搞到平衡二叉树部分觉得平衡二叉树的构建,分享一下自己的二叉树构建: 首先是树的节点的构建: public cl 清疚/ 2022年02月19日 09:39/ 0 赞/ 147 阅读
相关 平衡二叉树 (平衡查找树) 平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上 小咪咪/ 2021年10月29日 07:24/ 0 赞/ 435 阅读
相关 平衡二叉树 package com.avl; / @Auther: 大哥的叔 @Date: 2019/8/18 06:12 @ 忘是亡心i/ 2021年10月15日 05:37/ 0 赞/ 385 阅读
相关 二叉平衡树 二叉平衡树 说起这个树,我找了整整两天的时间,刚开始考虑的不周全,然后就一直该一直该,一直加一直加。 定义: 它是一颗空疏或它的左右两个子树的高度差的绝对值不超过 Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 434 阅读
还没有评论,来说两句吧...