public class BTNode {
private char key;
private BTNode left, right;
public BTNode(char key) {
this(key, null, null);
}
public BTNode(char key, BTNode left, BTNode right) {
this.key = key;
this.left = left;
this.right = right;
}
public char getKey() {
return key;
}
public void setKey(char key) {
this.key = key;
}
public BTNode getLeft() {
return left;
}
public void setLeft(BTNode left) {
this.left = left;
}
public BTNode getRight() {
return right;
}
public void setRight(BTNode right) {
this.right = right;
}
}
public class BinTree {
protected BTNode root;
public BinTree(BTNode root) {
this.root = root;
}
public BTNode getRoot() {
return root;
}
/** 构造树 */
public static BTNode init() {
BTNode a = new BTNode('A');
BTNode b = new BTNode('B', null, a);
BTNode c = new BTNode('C');
BTNode d = new BTNode('D', b, c);
BTNode e = new BTNode('E');
BTNode f = new BTNode('F', e, null);
BTNode g = new BTNode('G', null, f);
BTNode h = new BTNode('H', d, g);
return h;// root
}
/** 访问节点 */
public static void visit(BTNode p) {
System.out.print(p.getKey() + " ");
}
/** 递归实现前序遍历 */
protected static void preorder(BTNode p) {
if (p != null) {
visit(p);
preorder(p.getLeft());
preorder(p.getRight());
}
}
/** 递归实现中序遍历 */
protected static void inorder(BTNode p) {
if (p != null) {
inorder(p.getLeft());
visit(p);
inorder(p.getRight());
}
}
/** 递归实现后序遍历 */
protected static void postorder(BTNode p) {
if (p != null) {
postorder(p.getLeft());
postorder(p.getRight());
visit(p);
}
}
/** 非递归实现前序遍历 */
protected static void iterativePreorder(BTNode p) {
Stack<BTNode> stack = new Stack<BTNode>();
if (p != null) {
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
visit(p);
if (p.getRight() != null)
stack.push(p.getRight());
if (p.getLeft() != null)
stack.push(p.getLeft());
}
}
}
/** 非递归实现后序遍历 */
protected static void iterativePostorder(BTNode p) {
BTNode q = p;
Stack<BTNode> stack = new Stack<BTNode>();
while (p != null) {
// 左子树入栈
for (; p.getLeft() != null; p = p.getLeft())
stack.push(p);
// 当前节点无右子或右子已经输出
while (p != null && (p.getRight() == null || p.getRight() == q)) {
visit(p);
q = p;// 记录上一个已输出节点
if (stack.empty())
return;
p = stack.pop();
}
// 处理右子
stack.push(p);
p = p.getRight();
}
}
/** 非递归实现中序遍历 */
protected static void iterativeInorder(BTNode p) {
Stack<BTNode> stack = new Stack<BTNode>();
while (p != null) {
while (p != null) {
if (p.getRight() != null)
stack.push(p.getRight());// 当前节点右子入栈
stack.push(p);// 当前节点入栈
p = p.getLeft();
}
p = stack.pop();
while (!stack.empty() && p.getRight() == null) {
visit(p);
p = stack.pop();
}
visit(p);
if (!stack.empty())
p = stack.pop();
else
p = null;
}
}
public static void main(String[] args) {
BinTree tree = new BinTree(init());
System.out.print(" Pre-Order:");
preorder(tree.getRoot());
System.out.println();
System.out.print(" In-Order:");
inorder(tree.getRoot());
System.out.println();
System.out.print("Post-Order:");
postorder(tree.getRoot());
System.out.println();
System.out.print(" Pre-Order:");
iterativePreorder(tree.getRoot());
System.out.println();
System.out.print(" In-Order:");
iterativeInorder(tree.getRoot());
System.out.println();
System.out.print("Post-Order:");
iterativePostorder(tree.getRoot());
System.out.println();
}
}
分享到:
相关推荐
### 二叉树遍历的特点(数据结构) 在计算机科学领域,数据结构是研究的核心之一。其中,二叉树作为一种重要的非线性数据结构,在实际应用中极为广泛,包括搜索算法、排序算法等方面都有其身影。本文将详细介绍...
二叉树的遍历C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历...
二叉树遍历是理解数据结构和算法的基础,它包括前序遍历、中序遍历和后序遍历三种主要方法。 1. **二叉树的基本概念**: - 二叉树是一种特殊的树结构,每个节点最多有两个子节点,通常称为左子节点和右子节点。 -...
二叉树遍历是理解二叉树操作的关键部分,主要包括先序遍历、中序遍历和后序遍历三种方式。 1. 先序遍历(Preorder Traversal): 先序遍历的顺序是根节点 -> 左子树 -> 右子树。在C语言实现中,一般采用递归的方法...
二叉树遍历算法在IT领域中是一种基础且重要的数据结构操作技术,广泛应用于各种问题的解决。在本文中,我们将深入探讨二叉树遍历的原理及其在统计二叉树节点数量、叶子节点计数以及计算树深等方面的应用。 二叉树...
从给定的文件信息来看,该文件主要围绕“堆栈实现二叉树遍历数据结构”的主题,通过C语言编程来实现。以下是基于标题、描述、标签和部分内容的知识点总结和详细说明: ### 1. 数据结构基础 数据结构是计算机科学的...
二叉树遍历是针对这种数据结构的一种基本操作,用于按照特定顺序访问树中的所有节点。本程序实现了三种主要的二叉树遍历方法:先序遍历、中序遍历和后序遍历。以下是关于这些遍历方法的详细解释: 1. 先序遍历...
"数据结构树和二叉树遍历二叉树和线索二叉树PPT学习教案.pptx" 本资源主要讲述了数据结构树和二叉树遍历的相关知识点,包括二叉树的基本概念、二叉树遍历的六种方案、先序、中序、后序遍历算法的实现、线索二叉树的...
实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...
#### 1.2 二叉树遍历 遍历是指按照某种顺序访问二叉树中的所有节点,且每个节点只被访问一次的过程。二叉树常见的遍历方式包括:先序遍历、中序遍历和后序遍历。 ### 二、二叉树遍历方法 #### 2.1 先序遍历(前序...
### MATLAB 实现二叉树遍历算法的知识点详解 #### 一、二叉树节点结构体定义 在MATLAB中实现二叉树的第一步是定义一个表示二叉树节点的结构体。在这个例子中,作者定义了一个名为`TreeNode`的类来表示节点,该类...
java 写的算24程序。用两种二叉树遍历,并规整输出字符串
二叉树遍历 二叉树遍历
二叉树遍历是计算机科学中处理树结构数据时常用的一种技术,主要分为四种类型:先序遍历、中序遍历、后序遍历和宽度优先遍历。这些遍历方法各有特点,适用于不同的场景。 1. **先序遍历**: - **递归实现**:先...
二叉树遍历是计算机科学中数据结构领域的一个重要概念,尤其在算法设计与分析中占有举足轻重的地位。二叉树是一种特殊的图结构,每个节点最多有两个子节点,通常分为左子节点和右子节点。二叉树遍历是指按照特定顺序...
二叉树遍历是计算机科学中的一个重要概念,主要应用于数据结构和算法领域。二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,通常称为左子节点和右子节点。二叉树遍历是指按照特定顺序访问二叉树的所有...
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
二叉树遍历操作.cpp