`

Step By Step TDD树的遍历算法：）

算法TDDJavaCC++ 
阅读更多
Tree Node的定义。普通的POJO类： 
public class TreeNode {

	private TreeNode rightChild;
	private TreeNode leftChild;
	protected String treeNodeString;

	public TreeNode(String treeNodeString) {
		this.treeNodeString = treeNodeString;
	}
		
	public TreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(TreeNode rightChild) {
		this.rightChild = rightChild;
	}

	public TreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(TreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public String getTreeNodeString() {
		return this.treeNodeString;
	}

}


第一个Test： 
public class TreeTest extends TestCase {
	public void testTreePreTraverse() {
		TreeNode a= new TreeNode("a");
		assertEquals("a", preOrderTraverse(a));
	}

	private String preOrderTraverse(TreeNode root) {
		return null;//为了看得清楚直接写在test里了，应该提出成单独类
	}
}



...
	private String preOrderTraverse(TreeNode root) {
		return root.getTreeNodeString();//绿
	}

增加test，进一步描述需求 
...
	public void testABCPreOrderTraverse(){
		TreeNode a= new TreeNode("a");
		TreeNode b= new TreeNode("b");
		TreeNode c= new TreeNode("c");
		a.setLeftChild(b);
		a.setRightChild(c);
		assertEquals("abc", preOrderTraverse(a));//红expected:abc actual:a
	}



	private String preOrderTraverse(TreeNode root) {
		if (root.getLeftChild() == null && root.getRightChild() == null) {
			return root.getTreeNodeString();
		}else{
			return "abc";
		}
	}


else里面的演化 
return root.getTreeNodeString()+"bc";

return root.getTreeNodeString()+"b"+"c";


"b" == root.getLeftChild().getTreeNodeString()
"c" == root.getRightChild().getTreeNodeString() 
	private String preOrderTraverse(TreeNode root) {
		if (root.getLeftChild() == null && root.getRightChild() == null) {
			return root.getTreeNodeString();
		} else {
			TreeNode leftChild = root.getLeftChild();
			TreeNode rightChild = root.getRightChild();

			String result = root.getTreeNodeString();
			result += leftChild.getTreeNodeString();
			result += rightChild.getTreeNodeString();

			return result;
		}
	}

进一步添加test 
	public void testABCDEPreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		assertEquals("abdec", preOrderTraverse(a));//红
	}

红expected:abdec actual:abc 

最快使其通过，然后refactor消除重复 
			String result = root.getTreeNodeString();
			result += leftChild.getTreeNodeString();
			result += "d";
			result += "e";
			result += rightChild.getTreeNodeString();

testABCDEPreOrderTraverse()通过了:-)
但testABCPreOrderTraverse()会红，暂时先不管这个，我们refactor完这步再来看这个= = 
			String result = root.getTreeNodeString();
			result += leftChild.getTreeNodeString();
			result += leftChild.getLeftChild().getTreeNodeString();//"d"
			result += "e";
			result += rightChild.getTreeNodeString();



private String preOrderTraverse(TreeNode root) {
		if (root.getLeftChild() == null && root.getRightChild() == null) {
			return root.getTreeNodeString();
		} else {
			TreeNode leftChild = root.getLeftChild();
			TreeNode rightChild = root.getRightChild();

			String result = root.getTreeNodeString();
			result += leftChild.getTreeNodeString();
			result += leftChild.getLeftChild().getTreeNodeString();
			result += leftChild.getRightChild().getTreeNodeString();
			result += rightChild.getTreeNodeString();

			return result;
		}
	}


result += leftChild.getTreeNodeString();//visit leftChild
result += leftChild.getLeftChild().getTreeNodeString();//visit leftChild's leftChild
result += leftChild.getRightChild().getTreeNodeString();//visit leftChild's rightChild
root，left，right 恩恩 这不就是在preOrderTraverse么？
等同于 preOrderTraverse(leftChild)可以试一下。 （有test在咱不怕，不行就退回去= =） 
private String preOrderTraverse(TreeNode root) {
		if (root.getLeftChild() == null && root.getRightChild() == null) {
			return root.getTreeNodeString();
		} else {
			TreeNode leftChild = root.getLeftChild();
			TreeNode rightChild = root.getRightChild();

			String result = root.getTreeNodeString();
			result += preOrderTraverse(leftChild);
			result += rightChild.getTreeNodeString();

			return result;
		}
	}


是个绿，通过 yeah~而且连testABCPreOrderTraverse()也通过了。
访问右孩子也没区别吧？ 那咱试试.(有test在，咱就可以随便试，方便= =~) 
	private String preOrderTraverse(TreeNode root) {
		if (root.getLeftChild() == null && root.getRightChild() == null) {
			return root.getTreeNodeString();
		} else {
			TreeNode leftChild = root.getLeftChild();
			TreeNode rightChild = root.getRightChild();

			String result = root.getTreeNodeString();
			result += preOrderTraverse(leftChild);
			result += preOrderTraverse(rightChild);

			return result;
		}
	}


目前为止都是完全树，那瘸腿的呢？写个test看下 
public void testABCDEFPreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		e.setLeftChild(f);
		assertEquals("abdefc", preOrderTraverse(a));//完了 nullPointer了,惨
	}

因为e只有左孩子f，e的右孩子==null,走到e的右孩子时（执行preOrderTraverse(e的右孩子)）
if (root.getLeftChild() == null && root.getRightChild() == null)
时会错（其实在调用null.getLeftChild()，所以错了）

太技术化了= =
事实是：你要访问人家的右孩子，你不得问问人家有没有啊（if（e的右孩子有否？））
我改= = 
			String result = root.getTreeNodeString();
			result += preOrderTraverse(leftChild);
			if (rightChild != null)
				result += preOrderTraverse(rightChild);

这次通过了，同理 我把f放e右边呢？ 也得check吧？先写个test 
	public void testABCDEF2PreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		e.setRightChild(f);
		assertEquals("abdefc", preOrderTraverse(a));//红 还没check左孩子
	}



	private String preOrderTraverse(TreeNode root) {
		if (root.getLeftChild() == null && root.getRightChild() == null) {
			return root.getTreeNodeString();
		} else {
			TreeNode leftChild = root.getLeftChild();
			TreeNode rightChild = root.getRightChild();

			String result = root.getTreeNodeString();
			if (leftChild != null)
				result += preOrderTraverse(leftChild);
			if (rightChild != null)
				result += preOrderTraverse(rightChild);

			return result;
		}
	}

这下可以了：） 仔细看看怎么有点别扭啊  那么多check null啊？
嘿嘿 其实这里面有重复情况。第一个if 其实已经被else中包含了。去了试试 执行test，给我走= = 
	private String preOrderTraverse(TreeNode root) {

		TreeNode leftChild = root.getLeftChild();
		TreeNode rightChild = root.getRightChild();

		String result = root.getTreeNodeString();
		if (leftChild != null)
			result += preOrderTraverse(leftChild);
		if (rightChild != null)
			result += preOrderTraverse(rightChild);

		return result;

	}

通过:-) 继续refactor，消除重复 extract method 
	private String preOrderTraverse(TreeNode root) {

		TreeNode leftChild = root.getLeftChild();
		TreeNode rightChild = root.getRightChild();

		String result = root.getTreeNodeString();//root
		result = visitChild(leftChild, result);//left
		result = visitChild(rightChild, result);//right 真清爽:-)

		return result;

	}

	private String visitChild(TreeNode child, String result) {
		if (child != null)
			result += preOrderTraverse(child);
		return result;
	}

差不多了 下面是结果:-) 最后的extract class没有做= = 不过不难:-) 

import junit.framework.TestCase;

public class TreeTest extends TestCase {
	public void testTreePreTraverse() {
		TreeNode a = new TreeNode("a");
		assertEquals("a", preOrderTraverse(a));
	}

	public void testABCPreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		a.setLeftChild(b);
		a.setRightChild(c);
		assertEquals("abc", preOrderTraverse(a));
	}

	public void testABCDEPreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		assertEquals("abdec", preOrderTraverse(a));
	}

	public void testABCDEFPreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		e.setLeftChild(f);
		assertEquals("abdefc", preOrderTraverse(a));
	}

	public void testABCDEF2PreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		e.setRightChild(f);
		assertEquals("abdefc", preOrderTraverse(a));
	}

	private String preOrderTraverse(TreeNode root) {
		
		String result = root.getTreeNodeString();
		result = visitChild(root.getLeftChild(), result);
		result = visitChild(root.getRightChild(), result);
		return result;

	}

	private String visitChild(TreeNode child, String result) {
		if (child != null)
			result += preOrderTraverse(child);
		return result;
	}
}


extract class
先序: 
public class PreOrderTraverserOld implements ITraverser {
	private String result = new String();

	public String doTraverse(TreeNode root) {
		result += root.getTreeNodeString();
		result = visitChild(root.getLeftChild(), result);
		result = visitChild(root.getRightChild(), result);
		return result;
	}

	public String visitChild(TreeNode child, String result) {
		if (child != null)
			result = doTraverse(child);
		return result;
	}

}


中序，后序步骤没啥差别= =



中序 
public class InOrderTraverserOld implements ITraverser {
	private String result = new String();

	public String doTraverse(TreeNode root) {
		result = visitChild(root.getLeftChild(), result);
		result += root.getTreeNodeString();
		result = visitChild(root.getRightChild(), result);
		return result;
	}

	public String visitChild(TreeNode child, String result) {
		if (child != null)
			result = doTraverse(child);
		return result;
	}

}

后序 
public class PostOrderTraverserOld implements ITraverser {
	private String result = new String();

	public String doTraverse(TreeNode root) {
		result = visitChild(root.getLeftChild(), result);
		result = visitChild(root.getRightChild(), result);
		result += root.getTreeNodeString();
		return result;
	}

	public String visitChild(TreeNode child, String result) {
		if (child != null)
			result = doTraverse(child);
		return result;
	}

}

Test 
import junit.framework.TestCase;

public class TreeTest extends TestCase {
	ITraverser preOrderTraverserOld = new PreOrderTraverserOld();
	ITraverser inOrderTraverserOld = new InOrderTraverserOld();
	ITraverser postOrderTraverserOld = new PostOrderTraverserOld();

	public void testTreePreTraverse() {
		TreeNode a = new TreeNode("a");
		assertEquals("a", preOrderTraverserOld.doTraverse(a));
	}

	public void testABCPreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		a.setLeftChild(b);
		a.setRightChild(c);
		assertEquals("abc", preOrderTraverserOld.doTraverse(a));
	}

	public void testABCDEPreOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		assertEquals("abdec", preOrderTraverserOld.doTraverse(a));
	}

	public void testABCDEFInOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		e.setLeftChild(f);

		assertEquals("dbfeac", inOrderTraverserOld.doTraverse(a));
	}

	public void testABCDEF2InOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		e.setRightChild(f);
		assertEquals("dbefac", inOrderTraverserOld.doTraverse(a));
	}

	public void testABCDEFPostOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		e.setLeftChild(f);
		assertEquals("dfebca", postOrderTraverserOld.doTraverse(a));
	}

	public void testABCDEF2PostOrderTraverse() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		a.setLeftChild(b);
		a.setRightChild(c);
		b.setLeftChild(d);
		b.setRightChild(e);
		e.setRightChild(f);
		assertEquals("dfebca", postOrderTraverserOld.doTraverse(a));
	}

}
1
顶
1
踩
分享到：
| Composite+Visitor模式的树形结构实现
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Test Driven: Practical TDD and Acceptance TDD for Java Developers (PDF英文版)

    《Test Driven: Practical TDD and Acceptance TDD for Java Developers》是一本专注于Java开发者进行测试驱动开发（TDD）和验收测试驱动开发（Acceptance TDD）的专业书籍。这本书以PDF英文版的形式提供，旨在帮助...

    tdd_by_example.pdf

    **《TDD by Example》** 是由 Kent Beck 所著的一本关于测试驱动开发的经典著作，该书通过具体的例子详细介绍了 TDD 的思想和实践方法。以下是对书中部分章节的解读： - **Chapter 1: Story Time** - 引导读者进入 ...

    Visal C# 2010 step by step (英文)

    《Visual C# 2010 Step by Step》是一本由John Sharp编写的书籍，旨在帮助读者逐步掌握Visual C# 2010编程语言及其相关技术。本书适合初学者和有一定编程基础的学习者使用，通过实践案例深入浅出地介绍了C#的基本...

    tdd:在 JAVA 中学习 TDD @odd-e

    标题 "TDD:在JAVA中学习TDD @odd-e" 提到的是Test-Driven Development（测试驱动开发，简称TDD）在Java编程语言中的实践。TDD是一种软件开发方法论，强调先编写测试用例，然后编写刚好足够通过测试的生产代码。这种...

    test.driven.tdd.and.acceptance.tdd.for.java.developers

    在《Test-Driven and Acceptance TDD for Java Developers》这本书中，作者Lasse Koskela可能介绍了如何将模型驱动的方法与测试驱动开发（TDD）相结合，以便于Java开发者能够更有效地构建高质量的应用程序。...

    TDD测试驱动开发

    测试驱动开发（Test-Driven Development，简称TDD）是一种软件开发方法，强调在编写实际功能代码之前，先编写测试用例。这种方法的核心理念是“先写测试，再写代码”。TDD通过引入测试来引导软件设计，使得开发过程...

    TDD-CDMA技术及在4G中的应用.ppt

    2. 自适应资源分配：TDD-CDMA 技术可以在上行和下行链路中运用各种自适应资源分配算法，提高系统容量和灵活性。 3. 智能天线技术：TDD-CDMA 技术可以与智能天线技术结合，提高系统容量和抗干扰能力。 4. 多用户检测...

    tdd-tutorial:TDD教程

    3. 在Java中使用TDD： - **JUnit**：JUnit是Java最常用的单元测试框架，用于编写和运行测试用例。了解断言、测试注解（如@Test、@Before、@After）以及如何组织测试类是关键。 - **Mockito**：Mockito允许我们创建...

    Microsoft ASP.NET_3.5Step by Step

    《Microsoft ASP.NET 3.5 Step by Step》是微软出版的一本关于ASP.NET 3.5技术的详细教程，旨在帮助读者深入理解并掌握这一强大的Web应用程序开发框架。ASP.NET 3.5是.NET Framework 3.5的一部分，它极大地扩展了...

    TDD：通过大量测试寻找最优解决方案.docx

    标题中的"TDD"指的是Test-Driven Development，即测试驱动开发，是一种软件开发方法论，强调在编写实际代码之前先编写测试用例。这种方法的核心理念是通过编写测试来定义需求，确保代码的质量和功能完整性。TDD的...

    RIP TDD原文搬运

    测试驱动开发（Test-Driven Development，简称TDD）是一种软件开发方法，由Kent Beck提出并在其著作中倡导。然而，DHH（David Heinemeier Hansson）在其文章《TDD已死，长久测试》中表达了对TDD的质疑，认为TDD已经...

    FizzBuzz-TDD:研究TDD的项目

    FizzBu​​zz TDD 关于 研究测试驱动开发（TDD）的项目。 锻炼： 编写一个程序，打印从1到100的数字。但是，对于三个打印数字“ Fizz”（而不是数字）的倍数，以及五个打印“嗡嗡声”的倍数。 对于三和五的倍数的...

    tdd by example

    tdd by example (kent beck)

    tdd:简单的TDD实现

    测试驱动开发（Test-Driven Development，简称TDD）是一种软件开发方法，强调在编写实际功能代码之前先编写测试用例。TDD的核心理念是“先写测试，再写代码”。这个过程可以分为三个主要步骤：红、绿、重构。 1. **...

    TDD读书报告

    ### TDD读书报告知识点梳理 #### 一、了解和认识TDD - **定义**: 测试驱动开发（Test-Driven Development, TDD）是一种软件开发方法论，它要求开发人员在编写功能代码前先编写测试代码，以确保功能代码的质量。 - ...

    tdd-by-example:TDD示例

    通过示例进行测试驱动的开发存储库中的所有源代码示例均适用于我的所提供的示例灵感来自肯特·贝克（Kent Beck）在他的《示例一书中的 在此存储库中，我将使用Beck的经典TDD Money示例-更新到Java 11和JUnit 5。...

    try-tdd:引入 tdd 的练习

    **TDD（Test-Driven Development，测试驱动开发）**是一种软件开发方法，它提倡先编写测试用例，然后根据测试失败的情况来编写实现代码，确保代码功能的正确性。在这个名为"try-tdd"的练习中，我们专注于通过单元...

    spring-boot-tdd-example：tdd学习spring入门demo

    《Spring Boot TDD入门实践详解》 在编程领域，Test-Driven Development（TDD，测试驱动开发）是一种软件开发方法，它强调先编写测试用例，再编写满足这些测试用例的代码。在这个名为"spring-boot-tdd-example"的...

Magicbox
Global site tag (gtag.js) - Google Analytics