Обход дерева двоичного поиска, объединение InOrder, PreOrder, PostOrder, RevInOrder в одном методе - PullRequest
Новая
       48

Обход дерева двоичного поиска, объединение InOrder, PreOrder, PostOrder, RevInOrder в одном методе

1 голос
/ 26 мая 2020

У меня есть двоичное дерево поиска, и мне нужно написать методы inOrder, preOrder, postOrder и reverseInOrder, вот моя реализация, основанная на this (исключая inOrder): 

public String reverseInOrder() {

            String retString = "";

            // 1. Traverse the right subtree by recursively calling the pre-order function.
            if (this.bigger != null) retString += this.bigger.reverseInOrder() + ", ";

            // 2. Access the data part of the current node.
            retString += this.content;

            // 3. Traverse the left subtree by recursively calling the pre-order function.
            if (this.smaller != null) retString += ", " + this.smaller.reverseInOrder();

            return retString;
        }

        public String postOrder() {

            String retString = "";

            // 1. Traverse the left subtree by recursively calling the pre-order function.
            if (this.smaller != null) retString += this.smaller.preOrder() + ", ";

            // 2. Traverse the right subtree by recursively calling the pre-order function.
            if (this.bigger != null) retString += this.bigger.preOrder() + ", ";

            // 3. Access the data part of the current node.
            retString += this.content;

            return retString;
        }

        public String preOrder() {

            String retString = "";

            // 1. Access the data part of the current node.
            retString += this.content;

            // 2. Traverse the left subtree by recursively calling the pre-order function.
            if (this.smaller != null) retString += ", " + this.smaller.preOrder();

            // 3. Traverse the right subtree by recursively calling the pre-order function.
            if (this.bigger != null) retString += ", " + this.bigger.preOrder();

            return retString;
        }

Как видите, я всегда делаю одни и те же три вещи:

  • доступ к меньшему поддереву
  • доступ к текущему контенту
  • доступ к большему поддереву

Меняется только порядок, в котором я их делаю (игнорируя вставку запятых для удобства чтения).
Поэтому я хотел бы свести все типы этого метода к одному, где вы можете выбирать порядок, вот мой реализация: 

    /**
     * ops:
     * 0 := smaller/left
     * 1 := this content
     * 2 := smaller/right
     */
    public String someOrder(int firstOp, int secondOp) {
        List<String> retParts = new ArrayList<String>();

        int thirdOp = 3 - firstOp - secondOp;
        for (int el : new int[]{firstOp, secondOp, thirdOp}) {
            switch (el) {
                case 0:
                    if (this.smaller != null) retParts.add(this.smaller.someOrder(firstOp, secondOp));
                    break;

                case 1:
                    retParts.add(this.content.toString());
                    break;

                case 2:
                    if (this.bigger != null) retParts.add(this.bigger.someOrder(firstOp, secondOp));
                    break;

                default:
                    // shouldn't happen
                    break;
            }
        }

        return String.join(", ", retParts);
    }

Короткая попытка объяснения:

Вы сообщаете методу порядок операций, передавая ему первую и вторую операции (например, fistOp = 0, если вы сначала хотите go в меньшее поддерево), метод выводит последнюю операцию. В порядке операций я делаю то, что представляет собой операция. В конце концов, я возвращаю результаты операций в виде объединенной строки

Это не кажется мне элегантным решением, поэтому я открыт для предложений о том, как решить эту проблему (также в В общем, как объединить несколько методов, которые отличаются порядком операций в Java)

...