平衡二叉树求解步骤:
(1)插入节点
(2)找出不平衡因子,在插入过程中找到不平衡因子
(3)旋转,根据不平衡因子判断旋转方式
(4)生成新的平衡二叉树
在求解过程中,最重要步骤详解:
找出不平衡因子(也就是左右子树的高度差值为2或-2的情况)
方法1步骤:
a.节点中添加两个属性,左子树高度、右子树高度。
b.插入节点
c.返回的过程中动态的计算插入节点过程中经过的节点的左子树或右子树的高度。并计算各个节点的因子.
d.当节点因子为0时,返回过程中停止计算树的高度。当节点因子为2或-2时,即为不平衡因子,进行旋转
e.所有的旋转分为四种类型:LL顺时针旋转, RR逆时针旋转, LR先逆时针、然后顺时针,RL先顺时针在逆时针,旋转过程中调整各个节点的左右子树高度
f.旋转完成周调整,父节点的对应的左子树或者右子树的高度
这个方法通过给节点添加左右子树高度属性的方法,优点:节点的左右子树,只需要管理自己的高度,分而自治减少复杂性。代码中实现的是这个方法
package ProductCosume; import java.util.Queue; import java.util.Stack; public class BinaryTreeTest { enum BalanceFactory { LeftFactory(1), RightFactory(-1), EqualFacotry(0), LeftLossBalanceFactory( 2), RightLossBalanceFactory(-2), InvalideFactory(-3); int value = 0; private BalanceFactory(int value) { this.value = value; } } // 节点 static class Node { public Node(int value) { key = value; } int key; private BalanceFactory af = BalanceFactory.EqualFacotry; Node leftNode = null; Node rightNode = null; Node parentNode = null; int leftNodeHeight = 0; int rightNodeHeight = 0; public int getNodeHeight() { return leftNodeHeight > rightNodeHeight ? leftNodeHeight : rightNodeHeight; } // 获取平衡因子 public BalanceFactory getAf() { int factor = leftNodeHeight - rightNodeHeight; BalanceFactory resultBalanceFactory = null; switch (factor) { case 0: resultBalanceFactory = BalanceFactory.EqualFacotry; break; case 1: resultBalanceFactory = BalanceFactory.LeftFactory; break; case -1: resultBalanceFactory = BalanceFactory.RightFactory; break; case 2: resultBalanceFactory = BalanceFactory.LeftLossBalanceFactory; break; case -2: resultBalanceFactory = BalanceFactory.RightLossBalanceFactory; break; default: resultBalanceFactory = BalanceFactory.InvalideFactory; break; } af = resultBalanceFactory; return af; } } boolean isTaller = false; // 插入新的节点 public Node inserNode(Node tree, Node node) { if (tree == null) { tree = node; return tree; } if (tree.key == node.key) return tree; Node parentNode = tree.parentNode; if (tree.key > node.key) { // 左路插入 if (tree.leftNode == null) { tree.leftNode = node; node.parentNode = tree; tree.leftNodeHeight = tree.leftNodeHeight + 1; tree.getAf(); isTaller = true; System.out.println("root:" + tree.key + " left insert " + " node:" + node.key); if (tree.getAf() == BalanceFactory.EqualFacotry) isTaller=false; return tree; } else { inserNode(tree.leftNode, node); if(isTaller){ tree.leftNodeHeight = tree.leftNode.getNodeHeight() + 1; if (tree.getAf() == BalanceFactory.EqualFacotry) isTaller = false; } } } else { // 右路插入 if (tree.rightNode == null) { tree.rightNode = node; node.parentNode = tree; tree.rightNodeHeight += 1; isTaller = true; System.out.println("root:" + tree.key + " right insert " + " node:" + node.key); if (tree.getAf() == BalanceFactory.EqualFacotry) isTaller=false; return tree; } else { inserNode(tree.rightNode, node); if(isTaller){ tree.rightNodeHeight = tree.rightNode.getNodeHeight() + 1; if (tree.getAf() == BalanceFactory.EqualFacotry) isTaller = false; } } } if (isTaller) { boolean isRightNode = false; //非常重要:通过父亲类来判断插入到那一边 if(parentNode!=null){ if(parentNode.leftNode!=null&&parentNode.leftNode.key==tree.key) isRightNode = false; else isRightNode= true; } if (BalanceFactory.LeftLossBalanceFactory == tree.getAf() || BalanceFactory.RightLossBalanceFactory == tree.getAf()) { tree = rotateTree(tree); if (parentNode != null){ if(isRightNode) parentNode.rightNode = tree; else parentNode.leftNode = tree; } } } return tree; } // 破坏平衡旋转平衡二叉树 public Node rotateTree(Node tree) { Node rootNode = tree; if (rootNode == null) return tree; System.out.println("旋转前------------------------------"); widthSearch(rootNode); Node secondNode = null; if (rootNode.getAf() == BalanceFactory.RightLossBalanceFactory) { // 右边失去平衡 secondNode = rootNode.rightNode; if (secondNode.af == BalanceFactory.RightFactory) { // RR类型 System.out.println("RR类型旋转-------------"); antiClockWiseRoate(tree); } if (secondNode.af == BalanceFactory.LeftFactory) { // RL类型的 System.out.println("RL类型旋转-------------"); clockwiseRotate(secondNode); secondNode = secondNode.parentNode;//注意,第二个点变化了 widthSearch(secondNode); rootNode.rightNode = secondNode; antiClockWiseRoate(rootNode); } } else { // 左边失去平衡 secondNode = rootNode.leftNode; if (secondNode.af == BalanceFactory.LeftFactory) { // LL类型 System.out.println("LL类型旋转-------------"); clockwiseRotate(tree); } if (secondNode.af == BalanceFactory.RightFactory) { // LR类型的 System.out.println("LR类型旋转-------------"); antiClockWiseRoate(secondNode); secondNode = secondNode.parentNode;//注意,第二个点变化了 rootNode.leftNode = secondNode; widthSearch(secondNode); clockwiseRotate(tree); } } System.out.println("旋转后------------------------------"); widthSearch(secondNode); System.out.println("旋转结束------------------------------"); return secondNode; } // LL树 顺时针旋转 public void clockwiseRotate(Node tree) { if (tree == null || tree.leftNode == null) return; Node secondNode = tree.leftNode; secondNode.parentNode = tree.parentNode; tree.parentNode = secondNode; tree.leftNode = secondNode.rightNode; secondNode.rightNode = tree; tree.leftNodeHeight = secondNode.rightNodeHeight; secondNode.rightNodeHeight = tree.getNodeHeight() + 1; } // RR树 逆时针旋转 public void antiClockWiseRoate(Node tree) { if (tree == null || tree.rightNode == null) return; Node secondNode = tree.rightNode; secondNode.parentNode = tree.parentNode; tree.parentNode = secondNode; tree.rightNode = secondNode.leftNode; secondNode.leftNode = tree; tree.rightNodeHeight = secondNode.leftNodeHeight; secondNode.leftNodeHeight = tree.getNodeHeight() + 1; } public static void main(String[] args) { BinaryTreeTest binaryTreeTest = new BinaryTreeTest(); Node node = new Node(8); binaryTreeTest.inserNode(null, node); Node node2 = new Node(10); Node node3 = new Node(16); Node node4 = new Node(6); Node node5 = new Node(3); Node node6 = new Node(78); Node node7 = new Node(9); Node node8 = new Node(24); Node node9 = new Node(15); Node node10 = new Node(19); Node node11 = new Node(2); Node node12 = new Node(45); Node node13 = new Node(65); Node node14 = new Node(78); Node node15 = new Node(102); Node node16 = new Node(1); Node node17 = new Node(32); Node node18 = new Node(33); Node root = binaryTreeTest.inserNode(node, node2); root = binaryTreeTest.inserNode(root, node3); root = binaryTreeTest.inserNode(root, node4); root = binaryTreeTest.inserNode(root, node5); root = binaryTreeTest.inserNode(root, node6); root = binaryTreeTest.inserNode(root, node7); root = binaryTreeTest.inserNode(root, node8); root = binaryTreeTest.inserNode(root, node9); root = binaryTreeTest.inserNode(root, node10); root = binaryTreeTest.inserNode(root, node11); root = binaryTreeTest.inserNode(root, node12); System.out.println("------------------------------"); binaryTreeTest.widthSearch(root); root = binaryTreeTest.inserNode(root, node13); root = binaryTreeTest.inserNode(root, node14); root = binaryTreeTest.inserNode(root, node15); root = binaryTreeTest.inserNode(root, node16); root = binaryTreeTest.inserNode(root, node17); root = binaryTreeTest.inserNode(root, node18); binaryTreeTest.widthSearch(root); } public void widthSearch(Node node) { if (node != null) { System.out.println("node:" + node.key); widthSearch(node.leftNode); widthSearch(node.rightNode); } } }
方法2:不需要左右子树的高度属性,每次计算各自的平衡因子
相关推荐
平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,
文档中是我自己实现的用java语言实现(1)判断给定的二叉树是否平衡;(2)二叉树插入新数据后,如果失衡自我旋转调整的方法。
java下非递归实现平衡二叉树,实现了增删查改的基本功能
NULL 博文链接:https://709002341.iteye.com/blog/2258678
3. 由TXT文本中读入一系列的数据,建立一棵平衡二叉树,并实现查找任何数据的功能,并能打印出结点的访问路径。 (Makefile编译)
分别采用二叉链表和顺序表作存储结构,实现对二叉排序树与平衡二叉树的操作。 重庆理工大学,软件工程系,课程设计。
大三时写的一个程序,平衡二叉树的建立和查找等 用netBeans做的
广工数据结构课程设计大作业-平衡二叉树-Java实现(数据结构期末)
平衡二叉树
使用java语言编程实现了平衡二叉树、二叉树、二叉搜索树、红黑树四种树相关的数据结构,还实现了多种排序算法。并且是在J2EE下实现的。
Java实现的二叉搜索树和平衡二叉树的代码示例
Java中AVL平衡二叉树实现Map_(仿照TreeMap和TreeSet)1
java数据结构与算法之平衡二叉树的设计与实现分析.pdf
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树(递归定义)的二叉排序树。...
java数据结构与算法之平衡二叉树AVL树的设计与实现分析.doc
带平衡条件的二叉树,实现了平衡二叉树,左旋,右旋等等。
java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.docx
java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.pdf
利用java写了两个案例是关于二叉树和平衡树的分别为数组的和链式的。 功能: 1.三种历遍方式的输出。 2.平衡树的重构。 3.节点的添加以及删除。 4.平均查找长度的计算。