今天一天没有什么状态,学习效率太低了。今天重新温习了一下树的遍历,如何寻找中序遍历的下一个结点。接下来的计划是学习
Spring Boot
和 算法与数据结构。
算法与数据结构是我最薄弱的一环。每次写关于算法的代码时,都无法下手,经常陷入到逻辑的死胡同里。真心感觉自己的逻辑能力好差,思路混乱。程序员最重要的是思考和逻辑能力,只有把思路理清楚了,代码才能一气呵成。
首先看图
image.png
P
表示父结点,N
代表子结点。L
表示N
的左子树,R
表示N
的右子树。L
的时候,无关。当R != null
的时候,我们返回R
结点下面的第一个结点,即下一个结点。如果R == null
的时候,我们下一个结点肯定是要往上面走,在P != null
下的情况,如果N
是 P
的左子树,那么下一个结点就是P
。如果N
不是P
的左子树的话,我们需要一直往父亲结点走,直到是某一个结点的左子树,下一个结点即为所求。MyTreeNode.java
。包含以下属性:结点的值,左子树,右子树,父亲结点。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;
}
}
image.png
显而易见,前序遍历是ABDEGCF
,中序遍历是DBGEACF
,后序遍历是DGEBFCA
。
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;
}
}
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
原则,以保证被测试模块的交付质量。 B
:Border
,边界值测试,包括循环边界,特殊取值,特殊时间点,数据顺序等。C
:Correct
,正确的输入,并得到预期的结果。D
: Design
,与设计文档相结合,来编写单元测试。E
:Error
,强制错误信息的输入(如:非法数据,异常流程,非业务允许输入等),并得到预期的结果。运行Demo
,输出和我们预期一样的结果。
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(" ");
}
}
我感觉数据结构和算法,思路是最重要的。只要有思路了,代码就水到渠成。没有思路,任何华丽的代码都是徒劳的。
虽然有些数据结构和算法已经掌握了,但是想要简单形象的表达出来,对于我来说还是十分困难的。继续加油。