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

发布时间：2020-12-13 20:36:18 所属栏目：百科来源：网络整理

导读：Tree Node的定义。普通的POJO类： public class TreeNode {private TreeNode rightChild;private TreeNode leftChild;protected String treeNodeString;public TreeNode(String treeNodeString) {this.treeNodeString = treeNodeString;}public TreeNode getR

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);
		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(),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 += 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));
	}

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!