在Java中,你可以使用TreeMap
或TreeSet
來實現對樹節點的排序。這兩種數據結構都是基于紅黑樹實現的,它們可以保證元素的自然順序或者根據自定義的比較器進行排序。
以下是一個使用TreeMap
實現節點排序的示例:
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class SortedTreeNode {
public static void main(String[] args) {
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(12);
root.right.right = new TreeNode(18);
// 使用TreeMap對樹節點進行排序
Map<Integer, TreeNode> sortedNodes = new TreeMap<>(Comparator.comparingInt(TreeNode::getVal));
sortedNodes.putAll(buildNodeMap(root));
// 輸出排序后的節點
for (Map.Entry<Integer, TreeNode> entry : sortedNodes.entrySet()) {
System.out.println("Value: " + entry.getKey() + ", Node: " + entry.getValue());
}
}
private static Map<Integer, TreeNode> buildNodeMap(TreeNode node) {
if (node == null) {
return new TreeMap<>();
}
Map<Integer, TreeNode> nodeMap = buildNodeMap(node.left);
nodeMap.put(node.val, node);
nodeMap.putAll(buildNodeMap(node.right));
return nodeMap;
}
}
在這個示例中,我們首先創建了一個TreeNode
類,然后使用TreeMap
對樹節點進行排序。buildNodeMap
方法是一個遞歸方法,它將樹節點轉換為一個以節點值為鍵,節點為值的TreeMap
。最后,我們遍歷排序后的TreeMap
并輸出節點的值和節點對象。
如果你想要根據自定義的比較器對樹節點進行排序,可以在創建TreeMap
時傳入一個Comparator
實例。例如,以下示例將根據節點的值降序排序:
Map<Integer, TreeNode> sortedNodes = new TreeMap<>(Comparator.reverseOrder());