当前位置:  首页>> 技术小册>> Java面试指南

二叉树排序算法是一种常见的排序算法,它的时间复杂度为O(nlogn)。下面是一个用Java实现的二叉树排序算法:

  1. class TreeNode {
  2. int val;
  3. TreeNode left;
  4. TreeNode right;
  5. public TreeNode(int val) {
  6. this.val = val;
  7. }
  8. }
  9. public class BinaryTreeSort {
  10. public TreeNode root;
  11. public void insert(int val) {
  12. root = insert(root, val);
  13. }
  14. public TreeNode insert(TreeNode root, int val) {
  15. if (root == null) {
  16. return new TreeNode(val);
  17. }
  18. if (val < root.val) {
  19. root.left = insert(root.left, val);
  20. } else {
  21. root.right = insert(root.right, val);
  22. }
  23. return root;
  24. }
  25. public void inorderTraversal(TreeNode root) {
  26. if (root != null) {
  27. inorderTraversal(root.left);
  28. System.out.print(root.val + " ");
  29. inorderTraversal(root.right);
  30. }
  31. }
  32. public static void main(String[] args) {
  33. int[] nums = {4, 2, 7, 1, 3, 6, 9, 5};
  34. BinaryTreeSort tree = new BinaryTreeSort();
  35. for (int num : nums) {
  36. tree.insert(num);
  37. }
  38. tree.inorderTraversal(tree.root);
  39. }
  40. }

这个算法中,我们定义了一个TreeNode类,表示二叉树的节点。每个节点包含一个val值,以及左右子节点的指针。我们还定义了一个BinaryTreeSort类,用于执行排序操作。它包含一个root节点,表示树的根节点。我们使用insert方法将值插入到二叉树中,inorderTraversal方法遍历二叉树并输出排序后的结果。

在main方法中,我们定义一个数组nums,并将其插入到二叉树中。然后调用inorderTraversal方法输出排序后的结果。

以上就是一个用Java实现的二叉树排序算法。