您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
平衡二叉树(图文)
第十三双眼睛2023-10-21【数据结构与算法】人已围观
简介平衡二叉树
平衡二叉树
package com.xingchen.day014; public class AVLTreeDemo { public static void main(String[] args) { //int[] arr = {4,3,6,5,7,8}; int[] arr = {10,12,8,9,7,6}; AVLTree avlTree = new AVLTree(); for (int i=0;i<arr.length;i++) { avlTree.add(new Node(arr[i])); } avlTree.infixOrder(); System.out.println(avlTree.root.height()); } } class AVLTree { public Node root; public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } public void infixOrder() { if (root != null) { root.infixOrder(); } else { System.out.println("二叉排序树为空"); } } public Node search(int value) { if (root == null) { return null; } return root.search(value); } public Node searchParent(int value) { if (root == null) { return null; } else { return root.searchParent(value); } } //返回以node为根节点的二叉树中的最小值 public int deleteRightMin(Node node) { Node target = node; //循环查找左节点 while (target.left != null) { target = target.left; } //这时target就指向了最小节点 delNode(target.value); return target.value; } public void delNode(int value) { if (root == null) { return; } else { Node targetNode = search(value); // 如果没有找到,直接返回 if (targetNode == null) { return; } //如果只有一个节点 if (root.left == null && root.right == null) { root = null; return; } // Node parent = searchParent(value); if (targetNode.left == null && targetNode.right == null) { //判断当前节点是父节点的左子节点还是右子节点 if (parent.left != null && parent.left.value == value) { parent.left = null; } else if (parent.right != null && parent.right.value == value) { parent.right = null; } } else if (targetNode.left != null && targetNode.right != null) { int minValue = deleteRightMin(targetNode.right); targetNode.value = minValue; } else { if (targetNode.left != null) { if (parent != null) { if (parent.left.value == value) { parent.left = targetNode.left; } else { parent.right = targetNode.left; } } else { root = targetNode.left; } } else { if (parent != null) { if (parent.left.value == value) { parent.left = targetNode.right; } else { parent.right = targetNode.right; } } else { root = targetNode.right; } } } } } } class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } public void add(Node node) { if (node == null) { return; } if (node.value < this.value) { if (this.left == null) { this.left = node; } else { this.left.add(node); } } else { if (this.right == null) { this.right = node; } else { this.right.add(node); } } //添加完一个节点后,如果右子树的高度比左子树的高度大于1 if(rightHeight() - leftHeight() > 1) { if (right != null && right.leftHeight() > right.rightHeight()) { right.rightRotate(); leftRotate(); } else { leftRotate(); } return; } if (leftHeight() - rightHeight() > 1) { if (left != null && left.rightHeight() > left.leftHeight()) { //先堆当前节点的左子树进行左旋 left.leftRotate(); rightRotate(); } else { rightRotate(); } } } public void infixOrder() { if (this.left != null) { this.left.infixOrder(); } System.out.println(this); if (this.right != null) { this.right.infixOrder(); } } public int height() { return Math.max(left == null?0:left.height(),right == null? 0 :right.height()) + 1; } public int leftHeight() { if (left == null) { return 0; } return left.height(); } public int rightHeight() { if (right == null) { return 0; } return right.height(); } public void leftRotate() { Node newNode = new Node(value); //新的节点的左子树设置成当前节点的左子树 newNode.left = this.left; //新的节点的右子树设置成当前节点的右子树的左子树 newNode.right = this.right.left; //当前节点的值替换成右子节点的值 value = right.value; //把当前节点的右子树设置成右子树的右子树 this.right = this.right.right; //把当前节点的左子树设置成新的节点 this.left = newNode; } public void rightRotate() { Node newNode = new Node(value); newNode.left = left.right; value = left.value; left = left.left; right = newNode; } public Node search(int value) { if (value == this.value) { return this; } else if(value < this.value) { if (this.left != null) { return this.left.search(value); } else { return null; } } else { if (this.right != null) { return this.right.search(value); } else { return null; } } } public Node searchParent(int value) { //如果当前节点就是要删除的节点的父节点 if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) { return this; } else { //向左递归 if (value < this.value && this.left != null) { return this.left.searchParent(value); } else if (value >= this.value && this.right != null) { return this.right.searchParent(value); } else { return null; } } } @Override public String toString() { return "Node{" + "value=" + value + '}'; } } |
Tags:
很赞哦! ()
上一篇:二叉排序树节点的删除(图文)
下一篇:图的创建(图文)
相关文章
随机图文
-
回文数(图文)
回文数 给你一个整数x,如果它是一个回文数,返回true,如果不是,返回false,回文数是指正向和反向都是一样的数 -
栈实现队列(图文)
栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空,返回 true ;否则,返回 false -
颠倒二进制位(图文)
颠倒二进制位 颠倒给定的 32 位无符号整数的二进制位。 -
罗马数字转整数(图文)
罗马数字转整数 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即