JAVA树排序字典

Question

我有一个任务来实现检查两个无向图是否同构。为了实现树，我使用简单的邻接列表示例http://theoryofprogramming.com/adjacency-list-in-java/。我需要做的第二件事是对树“词典”进行排序，在对树的邻接列表进行排序时，词典排序和基数排序之间有区别吗？

Answer 1

你似乎混淆了术语。

基数排序是一种排序算法。

词汇顺序是“字典”顺序的数学概括。

据我所知，不存在“字典排序”这样的东西......除非这是您个人按字典顺序排序的简写。

排序算法和顺序/顺序之间的关系是，您使用排序算法将值的“集合”排序为特定顺序。它们之间的区别...就像“比较粉笔和奶酪”。

---

但是，根据我认为您打算如何使用它们，您可以明智地使用基数排序和词法顺序/排序来对邻接列表进行排序。

Answer 2

从你的问题字典排序和基数排序差异是-

基数排序是一种线性排序算法，通过逐位处理元素来对元素进行排序。

for example to sort array [ 110,22,31 ]  using Redix Sort -  

So first we will arrange based on unit place-
[110,31,22]
Then we arrange based on 10th place-
[110,22,31]
Then we arrange based on 100th place-
[22,31,110]

Finally we have the sorted result [22,31,110].

字典顺序基本上是字典顺序，或者我们可以说字母顺序的概括。

for example if we want to sort the below array-
[10,2,10001,1011,25,20001]

so the lexical sort will look like-
[10,10001,1011,2,20001,25]

您想使用树按字典顺序排序的第二件事

所以在这里我们可以使用二叉搜索树， 我分享了一个代码，希望它有帮助。

public class Node {
    private int value;
   private Node left, right;

    public Node(int value)
    {
        this.value = value;
        left = right = null;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

public class TreeSort {

    // Root of BST
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void insert(int value)
    {
        root = insertRecursion(root, value);
    }

    private Node insertRecursion(Node root, int value)
    {

        /* If the tree is empty, return a new node */
        if (root == null)
        {
            root = new Node(value);
            return root;
        }

        /* Otherwise, recur down the tree */
        if (lexicographicalSort(value ,root.getValue())<0)
            root.setLeft(insertRecursion(root.getLeft(), value));

        else if (lexicographicalSort(value , root.getValue())>0)
            root.setRight( insertRecursion(root.getRight(), value));

        /* return the root */
        return root;
    }

    public void inorderRecursion(Node root)
    {
        if (root != null)
        {
            inorderRecursion(root.getLeft());
            System.out.print(root.getValue() + " ");
            inorderRecursion(root.getRight());
        }
    }

    public void treeInsertions(int[] arr)
    {
        for(int i = 0; i < arr.length; i++)
        {
            insert(arr[i]);
        }

    }

    private static int lexicographicalSort(long input1, long input2){

        // -ve means input1 is smaller
        //  +ve means input1 is larger
        //  0 means input1 and input2 are same
        long inp1 = input1;
        long inp2 = input2;
        int input1Length = 1;
        int input2Length = 1;

        while(inp1/10>0){
            input1Length++;
            inp1 = inp1/10;
        }

        while(inp2/10>0){
            input2Length++;
            inp2 = inp2/10;
        }

        int[] inArr1 = new int[input1Length];
        int[] inArr2 = new int[input2Length];

        inp1 = input1;
        inp2 = input2;

        int min = Math.min(input1Length,input2Length);

        while(inp1/10>0){
            inArr1[--input1Length] = (int)inp1%10;
            inp1 = inp1/10;
        }
        inArr1[--input1Length] = (int)inp1;

        while(inp2/10>0){
            inArr2[--input2Length] = (int)inp2%10;
            inp2 = inp2/10;
        }
        inArr2[--input2Length] = (int)inp2;

        int k = 0;

        while(k<min){
            if( inArr1[k] != inArr2[k]){
                return inArr1[k]-inArr2[k];
            }
            k++;
        }

        return inArr1.length-inArr2.length;
    }
}

测试相同-->

public class SolTest {
    public static void main(String[] args) {

       // int arr[] = {5, 4, 7, 2, 11};
        int arr[] = {101,2,10,1012,8};
        TreeSort tree = new TreeSort();
        tree.treeInsertions(arr);
        tree.inorderRec(tree.getRoot());
}
}

输出->10 101 1012 2 8

注意-> 除了打印结果之外，您还可以将结果存储在列表中

如果您想要对字符串进行自定义词典排序，请使用以下方法

 private static int lexicographicalSort(String input1, String input2){

        // -1 means input1 is smaller
        //  1 means input1 is larger
        //  0 means input1 and input2 are same
        char[] chArr1 = input1.toCharArray();
        char[] chArr2 = input2.toCharArray();
        int min = Math.min(chArr1.length,chArr2.length);
        int k = 0;

        while(k<min){
            if( chArr1[k] != chArr2[k]){
                return chArr1[k]-chArr2[k];
            }
            k++;
        }

        return chArr1.length-chArr2.length;
    }