Java 有一棵树结构 取得所有的叶子节点
时间: 2024-02-24 17:55:19 浏览: 32
是的,Java提供了一些内置的数据结构来表示树,例如TreeNode和TreeMap。要获取树中所有叶子节点,可以使用以下代码:
```java
public List<TreeNode> getLeafNodes(TreeNode root) {
List<TreeNode> leafNodes = new ArrayList<>();
if (root == null) {
return leafNodes;
}
if (root.left == null && root.right == null) {
leafNodes.add(root);
} else {
leafNodes.addAll(getLeafNodes(root.left));
leafNodes.addAll(getLeafNodes(root.right));
}
return leafNodes;
}
```
这个方法会递归地遍历树的所有节点,找到所有的叶子节点并将它们添加到一个List中返回。在代码中,假设TreeNode类有left和right属性,表示左右子节点。
相关问题
用Java写一棵红黑树
红黑树是一种自平衡的二叉查找树,其中每个节点都有一个颜色属性,可以为红色或黑色。为了满足红黑树的性质,必须满足以下五个规则:
1. 每个节点都是红色或黑色。
2. 根节点是黑色的。
3. 每个叶子节点(NIL节点,空节点)是黑色的。
4. 如果一个节点是红色的,则它的两个子节点必须都是黑色的。
5. 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
下面是用Java实现红黑树的代码:
```java
public class RedBlackTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node<K, V> root;
private static class Node<K, V> {
private K key;
private V value;
private Node<K, V> left;
private Node<K, V> right;
private boolean color;
public Node(K key, V value, boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
}
public void put(K key, V value) {
root = put(root, key, value);
root.color = BLACK;
}
private Node<K, V> put(Node<K, V> node, K key, V value) {
if (node == null) {
return new Node<>(key, value, RED);
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = put(node.left, key, value);
} else if (cmp > 0) {
node.right = put(node.right, key, value);
} else {
node.value = value;
}
if (isRed(node.right) && !isRed(node.left)) {
node = rotateLeft(node);
}
if (isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
private boolean isRed(Node<K, V> node) {
if (node == null) {
return false;
}
return node.color == RED;
}
private Node<K, V> rotateLeft(Node<K, V> node) {
Node<K, V> x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
private Node<K, V> rotateRight(Node<K, V> node) {
Node<K, V> x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
private void flipColors(Node<K, V> node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
public V get(K key) {
Node<K, V> node = root;
while (node != null) {
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else {
return node.value;
}
}
return null;
}
public boolean contains(K key) {
return get(key) != null;
}
public void delete(K key) {
if (!contains(key)) {
return;
}
if (!isRed(root.left) && !isRed(root.right)) {
root.color = RED;
}
root = delete(root, key);
if (root != null) {
root.color = BLACK;
}
}
private Node<K, V> delete(Node<K, V> node, K key) {
if (key.compareTo(node.key) < 0) {
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveRedLeft(node);
}
node.left = delete(node.left, key);
} else {
if (isRed(node.left)) {
node = rotateRight(node);
}
if (key.compareTo(node.key) == 0 && node.right == null) {
return null;
}
if (!isRed(node.right) && !isRed(node.right.left)) {
node = moveRedRight(node);
}
if (key.compareTo(node.key) == 0) {
Node<K, V> min = min(node.right);
node.key = min.key;
node.value = min.value;
node.right = deleteMin(node.right);
} else {
node.right = delete(node.right, key);
}
}
return balance(node);
}
private Node<K, V> moveRedLeft(Node<K, V> node) {
flipColors(node);
if (isRed(node.right.left)) {
node.right = rotateRight(node.right);
node = rotateLeft(node);
flipColors(node);
}
return node;
}
private Node<K, V> moveRedRight(Node<K, V> node) {
flipColors(node);
if (isRed(node.left.left)) {
node = rotateRight(node);
flipColors(node);
}
return node;
}
private Node<K, V> deleteMin(Node<K, V> node) {
if (node.left == null) {
return null;
}
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveRedLeft(node);
}
node.left = deleteMin(node.left);
return balance(node);
}
private Node<K, V> min(Node<K, V> node) {
while (node.left != null) {
node = node.left;
}
return node;
}
private Node<K, V> balance(Node<K, V> node) {
if (isRed(node.right)) {
node = rotateLeft(node);
}
if (isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
public int size() {
return size(root);
}
private int size(Node<K, V> node) {
if (node == null) {
return 0;
}
return 1 + size(node.left) + size(node.right);
}
}
```
该实现中,红黑树的节点为内部类`Node`,其中包括键、值、左子节点、右子节点和颜色属性。`put`方法用于向红黑树中添加元素,`get`方法用于查找元素,`contains`方法用于判断元素是否存在,`delete`方法用于删除元素,`size`方法用于获取元素个数。在`put`和`delete`方法中,使用了旋转和颜色翻转等操作来保持红黑树的平衡和性质。
Java设计一棵红黑树,方法包括插入节点,删除节点和查找节点
红黑树是一种自平衡二叉查找树,它保证了插入、删除和查找操作的最坏情况时间复杂度为 O(log n)。红黑树的节点有两种颜色,红色和黑色,同时满足以下性质:
1. 根节点为黑色;
2. 所有叶子节点都是黑色;
3. 如果一个节点是红色的,则它的两个子节点都是黑色的;
4. 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点;
5. 每个节点的左子树和右子树都是红黑树。
下面是 Java 实现红黑树的代码:
```
public class RedBlackTree<T extends Comparable<T>> {
private Node<T> root;
private static final boolean RED = true;
private static final boolean BLACK = false;
private static class Node<T> {
T value;
Node<T> left, right;
boolean color;
Node(T value, boolean color) {
this.value = value;
this.color = color;
}
}
// 插入节点
public void insert(T value) {
root = insert(root, value);
root.color = BLACK;
}
private Node<T> insert(Node<T> node, T value) {
if (node == null) {
return new Node<>(value, RED);
}
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node.left = insert(node.left, value);
} else if (cmp > 0) {
node.right = insert(node.right, value);
} else {
node.value = value;
}
if (isRed(node.right) && !isRed(node.left)) {
node = rotateLeft(node);
}
if (isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
// 删除节点
public void delete(T value) {
if (root == null) {
return;
}
if (!isRed(root.left) && !isRed(root.right)) {
root.color = RED;
}
root = delete(root, value);
if (root != null && !isRed(root.left) && !isRed(root.right)) {
root.color = BLACK;
}
}
private Node<T> delete(Node<T> node, T value) {
if (value.compareTo(node.value) < 0) {
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveRedLeft(node);
}
node.left = delete(node.left, value);
} else {
if (isRed(node.left)) {
node = rotateRight(node);
}
if (value.compareTo(node.value) == 0 && node.right == null) {
return null;
}
if (!isRed(node.right) && !isRed(node.right.left)) {
node = moveRedRight(node);
}
if (value.compareTo(node.value) == 0) {
Node<T> min = findMin(node.right);
node.value = min.value;
node.right = deleteMin(node.right);
} else {
node.right = delete(node.right, value);
}
}
return balance(node);
}
// 查找节点
public Node<T> find(T value) {
Node<T> node = root;
while (node != null) {
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else {
return node;
}
}
return null;
}
private boolean isRed(Node<T> node) {
return node != null && node.color == RED;
}
private Node<T> rotateLeft(Node<T> node) {
Node<T> x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
private Node<T> rotateRight(Node<T> node) {
Node<T> x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
private void flipColors(Node<T> node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
private Node<T> moveRedLeft(Node<T> node) {
flipColors(node);
if (isRed(node.right.left)) {
node.right = rotateRight(node.right);
node = rotateLeft(node);
flipColors(node);
}
return node;
}
private Node<T> moveRedRight(Node<T> node) {
flipColors(node);
if (isRed(node.left.left)) {
node = rotateRight(node);
flipColors(node);
}
return node;
}
private Node<T> findMin(Node<T> node) {
while (node.left != null) {
node = node.left;
}
return node;
}
private Node<T> deleteMin(Node<T> node) {
if (node.left == null) {
return null;
}
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveRedLeft(node);
}
node.left = deleteMin(node.left);
return balance(node);
}
private Node<T> balance(Node<T> node) {
if (isRed(node.right)) {
node = rotateLeft(node);
}
if (isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
}
```
其中,插入节点和删除节点都需要进行旋转和颜色翻转等操作来保证红黑树的性质。查找节点则是一个简单的二叉查找。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)