前言

今天一天沒有什么狀態(tài)，學(xué)習(xí)效率太低了。今天重新溫習(xí)了一下樹的遍歷，如何尋找中序遍歷的下一個(gè)結(jié)點(diǎn)。接下來的計(jì)劃是學(xué)習(xí)Spring Boot 和 算法與數(shù)據(jù)結(jié)構(gòu)。

思路

算法與數(shù)據(jù)結(jié)構(gòu)是我最薄弱的一環(huán)。每次寫關(guān)于算法的代碼時(shí)，都無法下手，經(jīng)常陷入到邏輯的死胡同里。真心感覺自己的邏輯能力好差，思路混亂。程序員最重要的是思考和邏輯能力，只有把思路理清楚了，代碼才能一氣呵成。

• 中序遍歷：首先按照中序遍歷的方式去訪問根結(jié)點(diǎn)的左子樹，然后訪問根結(jié)點(diǎn)，最后按照中序遍歷的方式去訪問根結(jié)點(diǎn)的右子樹。

首先看圖

image.png

• P表示父結(jié)點(diǎn)，N代表子結(jié)點(diǎn)。L表示N的左子樹，R表示N的右子樹。
• 我們肯定是采用遞歸的方式。當(dāng)結(jié)點(diǎn)是L的時(shí)候，無關(guān)。當(dāng)R != null的時(shí)候，我們返回R結(jié)點(diǎn)下面的第一個(gè)結(jié)點(diǎn)，即下一個(gè)結(jié)點(diǎn)。如果R == null的時(shí)候，我們下一個(gè)結(jié)點(diǎn)肯定是要往上面走，在P ！= null下的情況，如果N是 P的左子樹，那么下一個(gè)結(jié)點(diǎn)就是P。如果N不是P的左子樹的話，我們需要一直往父親結(jié)點(diǎn)走，直到是某一個(gè)結(jié)點(diǎn)的左子樹，下一個(gè)結(jié)點(diǎn)即為所求。

代碼實(shí)現(xiàn)

• 定義一個(gè)MyTreeNode.java。包含以下屬性：結(jié)點(diǎn)的值，左子樹，右子樹，父親結(jié)點(diǎn)。

public class MyTreeNode {

    private final char value;
    private MyTreeNode left;
    private MyTreeNode right;
    private MyTreeNode parent;

    public MyTreeNode(char value) {
        super();
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    public MyTreeNode getLeft() {
        return left;
    }

    public void setLeft(MyTreeNode left) {
        this.left = left;

        if (left != null) {
            this.left.setParent(this);
        }
    }

    public MyTreeNode getRight() {
        return right;
    }

    public void setRight(MyTreeNode right) {
        this.right = right;

        if (right != null) {
            this.right.setParent(this);
        }
    }

    public MyTreeNode getParent() {
        return parent;
    }

    private void setParent(MyTreeNode parent) {
        this.parent = parent;
    }

    public char getValue() {
        return value;
    }
}

• 我們自己手動(dòng)去創(chuàng)建一根這樣的樹。
  

  image.png
  
  顯而易見，前序遍歷是ABDEGCF，中序遍歷是DBGEACF，后序遍歷是DGEBFCA。

• 如何通過前序遍歷和中序遍歷推出樹的結(jié)構(gòu)呢？其實(shí)很簡單，前序遍歷中第一個(gè)元素肯定是根結(jié)點(diǎn)。我們?cè)趶闹行虮闅v中找到該根結(jié)點(diǎn)，那么根結(jié)點(diǎn)左邊的元素就是左子樹，右邊的元素就是右子樹呢。然后遞歸的給每一個(gè)結(jié)點(diǎn)設(shè)置左子樹和右子樹。一根完整的二叉樹就形成了。簡單輕松，貼上代碼。

public class MyTreeNodeCreator {

    public static MyTreeNode sampleTree() {
        MyTreeNode root = new MyTreeNode('A');
        root.setLeft(new MyTreeNode('B'));
        root.setRight(new MyTreeNode('C'));
        root.getLeft().setLeft(new MyTreeNode('D'));
        root.getLeft().setRight(new MyTreeNode('E'));
        root.getLeft().getRight().setLeft(new MyTreeNode('G'));
        root.getRight().setRight(new MyTreeNode('F'));

        return root;
    }

    public static MyTreeNode customTree(String font, String mid) {
        if (StringUtils.isEmpty(font)) {
            return null;
        }

        char rootValue = font.charAt(0);
        int index = mid.indexOf(rootValue);
        MyTreeNode root = new MyTreeNode(rootValue);

        root.setLeft(customTree(font.substring(1, index + 1), mid.substring(0, index)));
        root.setRight(customTree(font.substring(index + 1), mid.substring(index + 1)));

        return root;
    }

    public static void behindOrder(MyTreeNode node) {
        if (node == null) {
            return;
        }

        behindOrder(node.getLeft());
        behindOrder(node.getRight());

        System.out.print(node.getValue() + " ");
    }

    public static String displayBehindOrder(String font, String mid) {
        if (StringUtils.isEmpty(font)) {
            return "";
        }

        char rootValue = font.charAt(0);
        int index = mid.indexOf(rootValue);

        return displayBehindOrder(font.substring(1, index + 1), mid.substring(0, index))
                + displayBehindOrder(font.substring(index + 1), mid.substring(index + 1)) + rootValue;
    }
}

• 接著我們根據(jù)二叉樹，尋找中序遍歷時(shí)的下一個(gè)結(jié)點(diǎn)。先一般后特殊，要進(jìn)行邊界控制，每次必須向前推進(jìn)循環(huán)不變式中涉及的變量值。

public class InOrder {

    public MyTreeNode next(MyTreeNode node) {
        if (node == null) {
            return null;
        }

        if (node.getRight() != null) {
            return first(node.getRight());
        } else {
            while (node.getParent() != null && node.getParent().getLeft() != node) {
                node = node.getParent();
            }

            return node.getParent();
        }
    }

    /**
     * Gets first node
     *
     * @param node
     * @return
     */
    public MyTreeNode first(MyTreeNode node) {
        if (node == null) {
            return null;
        }

        MyTreeNode curNode = node;

        while (curNode.getLeft() != null) {
            curNode = curNode.getLeft();
        }

        return curNode;
    }
}

• 核心代碼完成，我們開始寫測(cè)試demo。我們需要編寫測(cè)試用例，要遵守BCDE原則，以保證被測(cè)試模塊的交付質(zhì)量。
  • B：Border,邊界值測(cè)試，包括循環(huán)邊界，特殊取值，特殊時(shí)間點(diǎn)，數(shù)據(jù)順序等。
  • C：Correct，正確的輸入，并得到預(yù)期的結(jié)果。
  • D： Design，與設(shè)計(jì)文檔相結(jié)合，來編寫單元測(cè)試。
  • E：Error，強(qiáng)制錯(cuò)誤信息的輸入(如：非法數(shù)據(jù)，異常流程，非業(yè)務(wù)允許輸入等)，并得到預(yù)期的結(jié)果。

運(yùn)行Demo，輸出和我們預(yù)期一樣的結(jié)果。

image.png

public class Demo {
    private static InOrder inOrder = new InOrder();

    public static void main(String[] args) {
        printMidOrder();
    }

    public static void printBehindOrder() {
        MyTreeNode root = MyTreeNodeCreator.customTree("ABDEGCF", "DBGEACF");
        MyTreeNodeCreator.behindOrder(root);
        MyTreeNodeCreator.behindOrder(MyTreeNodeCreator.customTree("ABCD", "ABCD"));
    }

    public static void printMidOrder() {
        MyTreeNode sampleTree = MyTreeNodeCreator.sampleTree();
        display(sampleTree);
        display(MyTreeNodeCreator.customTree("", ""));
        display(MyTreeNodeCreator.customTree("A", "A"));
        display(MyTreeNodeCreator.customTree("AB", "BA"));
        display(MyTreeNodeCreator.customTree("ABCD", "DCBA"));
        display(MyTreeNodeCreator.customTree("ABCD", "ABCD"));
    }

    public static void display(MyTreeNode sampleTree) {
        for (MyTreeNode root = inOrder.first(sampleTree); root != null; root = inOrder.next(root)) {

            System.out.print(root.getValue());
        }
        System.out.println(" ");
    }
}

尾言

我感覺數(shù)據(jù)結(jié)構(gòu)和算法，思路是最重要的。只要有思路了，代碼就水到渠成。沒有思路，任何華麗的代碼都是徒勞的。

雖然有些數(shù)據(jù)結(jié)構(gòu)和算法已經(jīng)掌握了，但是想要簡單形象的表達(dá)出來，對(duì)于我來說還是十分困難的。繼續(xù)加油。