1、二叉树:文章来源:https://www.toymoban.com/news/detail-854199.html
package com.datastructure.tree;
//一个常用的第三方库是Apache Commons Collections,它提供了一个名为BinaryTree的类,用于表示二叉树。
//可以使用org.apache.commons.collections4.BinaryTree类创建二叉树和进行操作。
//可以在Maven中添加以下依赖项:
//<dependency>
//<groupId>org.apache.commons</groupId>
//<artifactId>commons-collections4</artifactId>
//<version>4.4</version>
//</dependency>
public class BinaryTree {
private Node root;
private class Node {
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// 插入节点
public void insert(int data) {
root = insert(root, data);
}
private Node insert(Node node, int data) {
if (node == null) {
node = new Node(data);
} else {
if (data <= node.data) {
node.left = insert(node.left, data);
} else {
node.right = insert(node.right, data);
}
}
return node;
}
// 前序遍历
public void preOrderTraversal() {
preOrderTraversal(root);
}
private void preOrderTraversal(Node node) {
if (node != null) {
System.out.println(node.data);
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
// 中序遍历
public void inOrderTraversal() {
inOrderTraversal(root);
}
private void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.println(node.data);
inOrderTraversal(node.right);
}
}
// 后序遍历
public void postOrderTraversal() {
postOrderTraversal(root);
}
private void postOrderTraversal(Node node) {
if (node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.println(node.data);
}
}
}
package com.datastructure.tree;
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);
System.out.println("前序遍历:");
tree.preOrderTraversal();
System.out.println("中序遍历:");
tree.inOrderTraversal();
System.out.println("后序遍历:");
tree.postOrderTraversal();
}
}
2、平衡二叉树:文章来源地址https://www.toymoban.com/news/detail-854199.html
package com.datastructure.tree;
//平衡树
//AVLTree是一个泛型类,可以存储任意实现了Comparable接口的类型。
//在AVLTree类中,使用Node类来表示树节点,并在节点中保存了节点值、左子节点、右子节点和节点高度。
//在插入操作中,使用递归的方式在树中查找合适的位置插入新节点,并在返回时重新平衡树。
//在插入节点之后,检查当前节点的平衡因子,如果超出范围,则通过旋转操作来恢复平衡。
//除了插入操作之外,还可以实现其他操作,例如删除节点、查找节点、遍历等。
public class AVLTreeDemo<T extends Comparable<T>> {
private class Node {
T value;
Node left;
Node right;
int height;
Node(T value) {
this.value = value;
this.height = 1;
}
}
private Node root;
private int height(Node node) {
if (node == null) {
return 0;
}
return node.height;
}
private int balanceFactor(Node node) {
if (node == null) {
return 0;
}
return height(node.left) - height(node.right);
}
private Node rotateLeft(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
private Node rotateRight(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
public void insert(T value) {
root = insert(root, value);
}
private Node insert(Node node, T value) {
if (node == null) {
return new Node(value);
}
if (value.compareTo(node.value) < 0) {
node.left = insert(node.left, value);
} else if (value.compareTo(node.value) > 0) {
node.right = insert(node.right, value);
} else {
return node; // 不允许插入重复的值
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = balanceFactor(node);
if (balance > 1 && value.compareTo(node.left.value) < 0) {
return rotateRight(node);
}
if (balance < -1 && value.compareTo(node.right.value) > 0) {
return rotateLeft(node);
}
if (balance > 1 && value.compareTo(node.left.value) > 0) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (balance < -1 && value.compareTo(node.right.value) < 0) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
public void delete(T value) {
root = delete(root, value);
}
private Node delete(Node node, T value) {
if (node == null) {
return null;
}
if (value.compareTo(node.value) < 0) {
node.left = delete(node.left, value);
} else if (value.compareTo(node.value) > 0) {
node.right = delete(node.right, value);
} else {
if (node.left == null || node.right == null) {
Node temp = null;
if (node.left != null) {
temp = node.left;
} else {
temp = node.right;
}
if (temp == null) {
temp = node;
node = null;
} else {
node = temp;
}
} else {
Node temp = minValueNode(node.right);
node.value = temp.value;
node.right = delete(node.right, temp.value);
}
}
if (node == null) {
return node;
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = balanceFactor(node);
if (balance > 1 && balanceFactor(node.left) >= 0) {
return rotateRight(node);
}
if (balance > 1 && balanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (balance < -1 && balanceFactor(node.right) <= 0) {
return rotateLeft(node);
}
if (balance < -1 && balanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
private Node minValueNode(Node node) {
Node current = node;
while (current.left != null) {
current = current.left;
}
return current;
}
// 其他操作方法...
// 中序遍历
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node node) {
if (node != null) {
inorderTraversal(node.left);
System.out.print(node.value + " ");
inorderTraversal(node.right);
}
}
}
package com.datastructure.tree;
//可以在项目中添加Apache Commons Collections库的依赖。
//可以在Maven项目中的pom.xml文件中添加以下代码片段:
//<dependency>
//<groupId>org.apache.commons</groupId>
//<artifactId>commons-collections4</artifactId>
//<version>4.4</version>
//</dependency>
//import org.apache.commons.collections4.map.AVLTree;
public class AVLTreeDemoMain {
public static void main(String[] args) {
AVLTreeDemo<Integer> tree = new AVLTreeDemo<>();
tree.insert(5);
tree.insert(10);
tree.insert(3);
tree.insert(7);
tree.insert(8);
tree.insert(1);
System.out.println("Inorder Traversal:");
tree.inorderTraversal();
tree.delete(5);
System.out.println("nAfter deleting 5:");
tree.inorderTraversal();
}
}
到了这里,关于数据结构之二叉树和平衡二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!