[数据结构与算法]Java实现二叉排序树

实际上Java，c++和c算法的写法上大致是相同的，本题使用Java实现。

堆排序是不想写了，红黑树也实现不了，只能写个二叉树排个序找找自信

本题建立了一颗二叉排序树然后给他中序遍历，实现了排序的效果。

本来是想写堆排序的，最后用堆排序的类名写了个这个，感觉效果差不多，都是二叉树，时间复杂度也都是O(nlogn)的

import java.util.Scanner;

public class HeapSort2 {
    public static void main(String[] args) {
        HeapSort2 heap = new HeapSort2();
        int n;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        Root head = new Root();
        TreeNode p = new TreeNode();
        head.root = p;
        p.val = scanner.nextInt();
        for (int i = 0; i < n - 1; i++) {
            TreeNode q = new TreeNode();
            q.val = scanner.nextInt();
            heap.insert(q, head.root);
        }
        heap.inOrderRecur(head.root);
    }

    public void insert(TreeNode q, TreeNode node) {
        if (q.val < node.val) {
            if (node.l == null) {
                node.l = q;
                return;
            } else
                insert(q, node.l);
        } else {
            if (node.r == null) {
                node.r = q;
                return;
            } else
                insert(q, node.r);
        }
    }

    public void inOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.l);
        System.out.print(root.val + " ");
        inOrderRecur(root.r);
    }


}

class Root {
    TreeNode root;
}

class TreeNode {
    int val;
    TreeNode l, r;

    TreeNode() {
    }

    TreeNode(int x) {
        this.val = x;
    }
}

?下面是本体用到的类，Root类用来记录根节点的位置，TreeNode实现了二叉树的结构。

class Root {
    TreeNode root;
}

class TreeNode {
    int val;
    TreeNode l, r;

    TreeNode() {
    }

    TreeNode(int x) {
        this.val = x;
    }
}

main方法?

    public static void main(String[] args) {
        HeapSort2 heap = new HeapSort2();//初始化类
        int n;//输入的数字个数
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        Root head = new Root();
        TreeNode p = new TreeNode();//建立根节点
        head.root = p;//记录根节点
        p.val = scanner.nextInt();
        for (int i = 0; i < n - 1; i++) {//插入剩下的n-1个节点
            TreeNode q = new TreeNode();
            q.val = scanner.nextInt();
            heap.insert(q, head.root);
        }
        heap.inOrderRecur(head.root);//中序遍历
    }

?insert方法，递归找位置插入二叉树

    public void insert(TreeNode q, TreeNode node) {//插入节点用到的方法
        if (q.val < node.val) {//比较要插入的节点与当前节点val
            if (node.l == null) {//左子树为空直接插入
                node.l = q;
                return;
            } else
                insert(q, node.l);//左子树不为空递归到左子树位置
        } else {
            if (node.r == null) {//同上
                node.r = q;
                return;
            } else
                insert(q, node.r);
        }
    }

常见的中序遍历

    public void inOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.l);
        System.out.print(root.val + " ");
        inOrderRecur(root.r);
    }