二叉树以及对二叉树的三种遍历(先根,中根,后根)的递归遍历算法实现,以及先根遍历的非递归实现。
//Node
public class Node {
private Node left;
private Node right;
private Object value;
public Node(Node left, Node right, Object value) {
super();
this.left = left;
this.right = right;
this.value = value;
}
public Node left() {
return left;
}
public Node right() {
return right;
}
public Object value() {
return value;
}
}
//遍历访问操作接口
public interface Visitor {
public void visit(Node obj);
}
//实现
public class BinaryTreeScan {
public void firstRootScan(Node node, Visitor visitor) {
if (node == null)
return;
visitor.visit(node);
this.firstRootScan(node.left(), visitor);
this.firstRootScan(node.right(), visitor);
}
public void midRootScan(Node node, Visitor visitor) {
if (node == null)
return ;
this.midRootScan(node.left(), visitor);
visitor.visit(node);
this.midRootScan(node.right(), visitor);
}
public void lastRootScan(Node node, Visitor visitor) {
if (node == null)
return ;
this.lastRootScan(node.left(), visitor);
this.lastRootScan(node.right(), visitor);
visitor.visit(node);
}
public void firstRootScanNonRecursion(Node node, Visitor visitor) {
if (node == null)
return ;
Stack stack = new Stack();
stack.push(node);
while(!stack.empty()) {
Node n = (Node) stack.pop();
visitor.visit(n);
if (n.right() != null)
stack.push(n.right());
if (n.left() != null)
stack.push(n.left());
}
}
}
//tester
public class Main {
public static void main(String[] args) {
Node b = new Node(new Node(null,null,"d"),new Node(null,null,"e"),"b");
Node a = new Node(b, new Node(new Node(null,null,"f"),null,"c"),"a");
BinaryTreeScan binaryTreeScan = new BinaryTreeScan();
StringBuilder sb = new StringBuilder();
binaryTreeScan.firstRootScanNonRecursion(a,new VisitorStringBuffer(sb));
System.out.println(sb.toString());
}
}
class VisitorStringBuffer implements Visitor {
private final StringBuilder sb;
VisitorStringBuffer(StringBuilder sb) {
this.sb = sb;
}
public void visit(Node obj) {
sb.append(obj.value());
}
}
分享到:
相关推荐
在二叉树遍历中,我们利用函数调用自身来处理树的不同部分。 1. **前序遍历**(根-左-右): - 递归版本:首先访问根节点,然后递归遍历左子树,最后递归遍历右子树。 - 非递归版本:使用栈来模拟递归过程。首先...
基于C语言编写的递归与非递归方法的二叉树先中后序遍历
二叉树是计算机科学中一种重要的数据结构,它由节点(或称为顶点)组成,每个节点最多有两个子节点,通常分别称为左子节点和右子节点...在编程实践中,熟悉二叉树遍历的递归和非递归实现对于提升问题解决能力至关重要。
对二叉树进行前、中、后、层序遍历。对前、中、后分别用递归和非递归。
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
在实际应用中,除了递归之外,还可以使用栈或队列等数据结构实现非递归的二叉树遍历,例如层次遍历(广度优先搜索)就是使用队列实现的。递归方法虽然直观,但在处理大规模数据时可能会导致栈溢出,此时非递归方法就...
二叉树遍历的递归与非递归实现各有优劣。递归实现代码简洁,易于理解,但当树深度很大时可能导致调用栈溢出。非递归实现通常使用辅助数据结构,如栈或队列,避免了调用栈的问题,但代码相对复杂。 在实际应用中,...
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
二叉树的非递归遍历,使用C++实现二叉树的非递归遍历,对正在学习算法的同学应该挺有帮助的
二种非递归实现 二叉树中序遍历: 递归实现 非递归实现 二叉树后序遍历: 递归实现 非递归实现 二叉树层次遍历 二叉树层次创建,创建方法遵循卡特兰数 http://write.blog.csdn.net/postedit/17380455
C语言二叉树遍历前序非递归算法,简单易懂,正确无误
二叉树遍历是计算机科学中处理二叉树数据结构的一种基本操作,它涉及到访问二叉树中的每个节点。在二叉树中,每个节点最多有两个子节点,通常分为左子节点和右子节点。遍历二叉树的目的是按照某种顺序访问所有节点,...
二叉树遍历的递归和非递归实现都有其优缺点。递归方法代码简洁,但会消耗更多的系统资源,因为每次函数调用都会产生一定的开销。非递归方法虽然代码相对复杂,但能有效地控制内存使用,适合处理大容量的数据。 在...
在IT领域,尤其是在数据结构与算法的学习中,中序遍历二叉树的非递归算法是一个关键且实用的知识点。通常,我们首先通过递归来实现二叉树的遍历,但递归方法可能因深度过大导致栈溢出,因此掌握非递归版本的遍历算法...
在"traverse tree (nonrecuision)"这个压缩包文件中,很可能包含了用C++实现的非递归版本二叉树遍历代码,可以作为学习和参考的实例。通过理解并实践这些代码,可以加深对二叉树遍历的理解,提高编程能力。
二叉树的递归遍历、非递归遍历和层次遍历
}二叉树遍历是计算机科学中对二叉树数据结构进行访问的重要操作,通常包括前序遍历、中序遍历和后序遍历三种方式。在这些遍历方法中,递归是最直观且易于理解的实现方式,但递归可能导致调用栈过深,不适合处理大型...
### 二叉树遍历的非递归算法分析与实现 #### 一、引言 在数据结构领域中,二叉树作为一种基本的数据组织形式,其应用极为广泛。对于二叉树的操作,其中最重要的就是遍历操作。遍历是指按照特定顺序访问二叉树的...
非递归先序遍历二叉树: 非递归中序遍历二叉树: 非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度:...