import junit.framework.TestCase;
public class TreeWalkerTest extends TestCase {
// 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
// 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
// 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n
public void testSimpleTreeWalk() {
IVisitor preOrderTraverser= new TreePreOrderTraverser();
IVisitor inOrderTraverser= new TreeInOrderTraverser();
IVisitor postOrderTraverser= new TreePostOrderTraverser();
TreeNode a= new TreeNode("a");
TreeNode b= new TreeNode("b");
TreeNode c= new TreeNode("c");
a.setLeftChild(b);
a.setRightChild(c);
TreeNode d= new TreeNode("d");
TreeNode e= new TreeNode("e");
b.setLeftChild(d);
b.setRightChild(e);
a.accept(preOrderTraverser);
assertEquals("abdec",preOrderTraverser.getOutString().toString());
a.accept(inOrderTraverser);
assertEquals("dbeac",inOrderTraverser.getOutString().toString());
a.accept(postOrderTraverser);
assertEquals("debca",postOrderTraverser.getOutString().toString());
}
}
public interface ITreeNode {
public abstract boolean isLeaf();
public abstract TreeNode getRightChild();
public abstract void setRightChild(TreeNode rightChild);
public abstract TreeNode getLeftChild();
public abstract void setLeftChild(TreeNode leftChild);
public abstract String getTreeNodeString();
}
如下是节点的Visitable接口
这个地方有些困惑：为啥要 node.accept(visitor) ？
好像 ： visitor.visit(node)更直接些？ 呵呵 哪位大哥给解释下:-)
public interface IVisitable {
public abstract void accept(IVisitor v);
}
public interface IVisitor {
public abstract void visit(TreeNode node);
public abstract StringBuffer getOutString();
}
public class TreeInOrderTraverser implements IVisitor {
// 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
// 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
// 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n
// 基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？
// 到了后面才明白，这是不同的应用需要的。
// 例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；
// 而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。
// 实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。
// 对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。
// 利用C++的封装和重载特性，这些遍历方法能很清晰的表达。
private StringBuffer outString = new StringBuffer();;
public void visit(TreeNode node) {
visitChild(node.getLeftChild());
getOutString().append(node.getTreeNodeString());//visit root
visitChild(node.getRightChild());
}
private void visitChild(TreeNode childNode) {
if ( childNode!= null) {
childNode.accept(this);
}
}
public StringBuffer getOutString() {
return this.outString;
}
}
public class TreeNode implements IVisitable, ITreeNode {
private TreeNode rightChild;
private TreeNode leftChild;
protected String treeNodeString;
public TreeNode() {
super();
}
public TreeNode(String treeNodeString) {
this.treeNodeString = treeNodeString;
}
public boolean equals(Object anotherTreeNode) {
if (anotherTreeNode instanceof TreeNode) {
return treeNodeString.equals(((TreeNode) anotherTreeNode)
.getTreeNodeString());
} else {
return false;
}
}
public boolean isLeaf() {
return getLeftChild() == null && getRightChild() == null;
}
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;
}
public void accept(IVisitor v) {
v.visit(this);
}
}
public class TreePostOrderTraverser implements IVisitor {
// 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
// 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
// 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n
// 基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？
// 到了后面才明白，这是不同的应用需要的。
// 例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；
// 而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。
// 实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。
// 对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。
// 利用C++的封装和重载特性，这些遍历方法能很清晰的表达。
private StringBuffer outString= new StringBuffer();
public void visit(TreeNode node) {
visitChild(node.getLeftChild());
visitChild(node.getRightChild());
getOutString().append(node.getTreeNodeString());
}
private void visitChild(TreeNode childNode) {
if ( childNode!= null) {
childNode.accept(this);
}
}
public StringBuffer getOutString() {
return outString;
}
}
public class TreePreOrderTraverser implements IVisitor {
// 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
// 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
// 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n
// 基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？
// 到了后面才明白，这是不同的应用需要的。
// 例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；
// 而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。
// 实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。
// 对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。
// 利用C++的封装和重载特性，这些遍历方法能很清晰的表达。
private StringBuffer outString = new StringBuffer();;
public void visit(TreeNode node) {
getOutString().append(node.getTreeNodeString());
visitChild(node.getLeftChild());
visitChild(node.getRightChild());
}
private void visitChild(TreeNode childNode) {
if ( childNode!= null) {
childNode.accept(this);
}
}
public StringBuffer getOutString() {
return outString;
}
}
分享到：
相关推荐
Composite模式将对象组合成树形结构以表示“部分-整体”的层次结构。C++中的Composite模式通常涉及到使用基类和派生类来表示复合对象和叶子对象，通过递归的方式处理树形结构中的每个节点。 #### Flyweight模式 ...
组合模式（Composite Pattern）：将对象组合成树形结构，以便于对对象的管理和操作。 适配器模式（Adapter Pattern）：将一个类的接口转换为另一个类的接口，以便于不同类之间的通信和合作。 外观模式（Facade ...
- 组合模式（Composite）：将对象组合成树形结构以表示“部分-整体”的层次结构，使得用户对单个对象和组合对象的使用具有一致性。 - 装饰器模式（Decorator）：动态地给一个对象添加一些额外的职责，可以独立于...
Composite模式将对象组合成树形结构以表示“部分-整体”的层次结构，使得客户可以一致地使用单个对象和组合对象。 #### Flyweight模式 Flyweight模式用于减少创建大量相似对象所消耗的内存，通过共享尽可能多的数据...
Composite模式允许你将对象组合成树形结构来表示“部分-整体”的层次结构，使得用户可以一致地使用单个对象和组合对象。 #### 2.5 Flyweight模式 Flyweight模式通过共享技术有效地支持大量细粒度对象，减少内存占用...
复合模式是一种结构型设计模式，它允许你将对象组织成树形结构，表现得像单个对象一样。在复合模式中，你可以对单个对象和对象组合进行相同的操作，无需关心你正在处理的是单个对象还是对象组合。这种模式在处理层次...
1. 组合模式（Composite Pattern）：将对象组合成树形结构以表示“部分-整体”的层次结构，使得客户端可以一致地处理单个对象和对象组合。 2. 代理模式（Proxy Pattern）：为其他对象提供一种代理以控制对这个对象...
- **2.4 Composite模式**：组合模式允许你将对象组合成树形结构来表示部分整体的层次结构。 - **2.5 Flyweight模式**：享元模式用于减少大量相似对象的内存消耗。 - **2.6 Facade模式**：外观模式为子系统中的一组...
- **2.4 Composite模式**：将对象组合成树形结构以表示“部分-整体”的层次结构。Composite模式使得用户可以一致地使用单个对象和组合对象。这种模式在处理具有层次结构的问题时非常有效。 - **2.5 Flyweight模式**...
- 组合模式（Composite）：将对象组合成树形结构以表示“部分-整体”的层次结构。 - 装饰模式（Decorator）：动态地给对象添加一些额外的职责，装饰者和被装饰对象拥有相同的接口。 - 外观模式（Facade）：提供一...