前言
今天一天沒有什么狀態(tài)，學(xué)習(xí)效率太低了腕唧。今天重新溫習(xí)了一下樹的遍歷或辖，如何尋找中序遍歷的下一個結(jié)點。接下來的計劃是學(xué)習(xí)
Spring Boot和 算法與數(shù)據(jù)結(jié)構(gòu)枣接。
思路
算法與數(shù)據(jù)結(jié)構(gòu)是我最薄弱的一環(huán)颂暇。每次寫關(guān)于算法的代碼時，都無法下手但惶，經(jīng)常陷入到邏輯的死胡同里耳鸯。真心感覺自己的邏輯能力好差，思路混亂膀曾。程序員最重要的是思考和邏輯能力县爬，只有把思路理清楚了，代碼才能一氣呵成添谊。
- 中序遍歷：首先按照中序遍歷的方式去訪問根結(jié)點的左子樹捌省，然后訪問根結(jié)點，最后按照中序遍歷的方式去訪問根結(jié)點的右子樹碉钠。
首先看圖
image.png
-
P表示父結(jié)點纲缓，N代表子結(jié)點。L表示N的左子樹喊废，R表示N的右子樹祝高。 - 我們肯定是采用遞歸的方式。當結(jié)點是
L的時候污筷，無關(guān)工闺。當R != null的時候，我們返回R結(jié)點下面的第一個結(jié)點瓣蛀，即下一個結(jié)點陆蟆。如果R == null的時候，我們下一個結(jié)點肯定是要往上面走惋增，在P 叠殷！= null下的情況，如果N是P的左子樹诈皿，那么下一個結(jié)點就是P林束。如果N不是P的左子樹的話像棘，我們需要一直往父親結(jié)點走，直到是某一個結(jié)點的左子樹壶冒，下一個結(jié)點即為所求缕题。
代碼實現(xiàn)
- 定義一個
MyTreeNode.java。包含以下屬性：結(jié)點的值胖腾，左子樹烟零，右子樹，父親結(jié)點咸作。
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;
}
}
-
我們自己手動去創(chuàng)建一根這樣的樹瓶摆。
image.png
顯而易見，前序遍歷是ABDEGCF性宏，中序遍歷是DBGEACF群井，后序遍歷是DGEBFCA。 如何通過前序遍歷和中序遍歷推出樹的結(jié)構(gòu)呢毫胜？其實很簡單书斜，前序遍歷中第一個元素肯定是根結(jié)點。我們在從中序遍歷中找到該根結(jié)點酵使，那么根結(jié)點左邊的元素就是左子樹，右邊的元素就是右子樹呢口渔。然后遞歸的給每一個結(jié)點設(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ù)二叉樹知举，尋找中序遍歷時的下一個結(jié)點。先一般后特殊太伊，要進行邊界控制雇锡，每次必須向前推進循環(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;
}
}
- 核心代碼完成僚焦，我們開始寫測試
demo锰提。我們需要編寫測試用例，要遵守BCDE原則，以保證被測試模塊的交付質(zhì)量欲账。-
B：Border,邊界值測試，包括循環(huán)邊界芭概，特殊取值赛不，特殊時間點，數(shù)據(jù)順序等罢洲。 -
C：Correct踢故，正確的輸入，并得到預(yù)期的結(jié)果惹苗。 -
D：Design殿较，與設(shè)計文檔相結(jié)合，來編寫單元測試桩蓉。 -
E：Error淋纲，強制錯誤信息的輸入(如：非法數(shù)據(jù)，異常流程院究，非業(yè)務(wù)允許輸入等)洽瞬，并得到預(yù)期的結(jié)果。
-
運行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)掌握了，但是想要簡單形象的表達出來跪妥，對于我來說還是十分困難的京景。繼續(xù)加油。
