树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。树结构在客观世界中广泛存在,树在计算机领域中也有广泛的应用,如在编译程序中,可用树来表示源程序的语法结构。
树作为非常基础的数据结构,有必要了解它的基本原理和使用场合,复习二叉树的数据结构,要分几个部分循序渐进地进行,这篇博客只涉及二叉树的构造和遍历。
首先类用于表示树的一个节点:
package algorithm.binarytree;
/**
* <p>Description: Test</p>
* <p>Copyright (c) 2010</p>
* <p>Department: </p>
* <p>Company: </p>
* <p>Project:Test</p>
*
* @author Tomy Zhou
* @since 1.0
* @version algorithm.binarytree; BinaryTreeNode.java
* 2010-4-26
**/
public class BinaryTreeNode
<T> {
public T data;
public BinaryTreeNode leftChild, rightChild;
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BinaryTreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTreeNode leftChild) {
this.leftChild = leftChild;
}
public BinaryTreeNode getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTreeNode rightChild) {
this.rightChild = rightChild;
}
}
package algorithm.binarytree;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* <p>Description: Test</p>
* <p>Copyright (c) 2010</p>
* <p>Department: </p>
* <p>Company: </p>
* <p>Project:Test</p>
*
* @author Tomy Zhou
* @since 1.0
* @version algorithm.binarytree; BinaryTree.java
* 2010-4-26
**/
public class BinaryTree<T> {
BinaryTreeNode<T> root;
public BinaryTree(){
}
/**
* 二叉树的创建
* @param list
*/
public void createBiTree(List<T> list){
Iterator<T> iterator = list.iterator();
while(iterator.hasNext()){
BinaryTreeNode<T> node = new BinaryTreeNode<T>();
node.setData(iterator.next());
insertTree(node);
}
}
/**
* 插入时,从根节点开始判断它是否有Child,如果没有,则将节点的孩子
* 指向为传入参数的引用
*
* @param node
*/
public void insertTree(BinaryTreeNode<T> node) {
if (root == null) {
root = node;
} else {
BinaryTreeNode<T> current = root;
while (true) {
if (current.leftChild == null) {
current.leftChild = node;
return;
} else if (root.rightChild == null) {
current.rightChild = node;
return;
} else {
current = current.leftChild;
}
}
}
}
/**
* 先序递归遍历-按照root,left子树和right子树顺序遍历
*
*/
public void preOrderTraverse(BinaryTreeNode node){
System.out.println(node.getData());
if(node.getLeftChild()!=null){
preOrderTraverse(node.getLeftChild());
}
if(node.getRightChild()!=null){
preOrderTraverse(node.getRightChild());
}
}
/**
* 先序循环遍历-按照root,left子树和right子树顺序遍历
*
*/
public void preOrderTraverseLoop(BinaryTreeNode node){
//System.out.println(node.getData());
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.push(node);
while(!stack.isEmpty()){
BinaryTreeNode biNode = stack.pop();
System.out.println(biNode.getData());
BinaryTreeNode left = biNode.leftChild;
if(left!=null){
stack.push(left);
}
BinaryTreeNode right = biNode.rightChild;
if(right!=null){
stack.push(right);
}
}
}
public static void main(String[] args) {
Integer[] ints = new Integer[]{1,3,9,8,7,6,2,98,76};
List list = new ArrayList<Integer>(ints.length);
for (int i = 0; i < ints.length; i++) {
list.add(ints[i]);
}
BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
binaryTree.createBiTree(list);
binaryTree.preOrderTraverse(binaryTree.root);
}
}
分享到:
相关推荐
通过对二叉树构造与遍历的深入学习与实践,学生不仅能够掌握二叉树的基本概念和操作,还能在算法设计、数据处理等方面获得实质性的提升。这种理论与实践相结合的学习方式,是提升计算机科学与技术专业学生专业技能的...
这些遍历方法在实际应用中有着广泛用途,例如在编译器设计中构造语法树、文件系统的遍历以及数据的序列化和反序列化等。源程序通常会使用递归或栈来实现这些遍历策略,递归方法直观且易于理解,而栈方法则避免了函数...
### 构造二叉树与遍历二叉树 ...总之,通过上述分析我们可以了解到,二叉树不仅是一种重要的数据结构,也是许多高级数据结构的基础,掌握好二叉树的构造与遍历方法对于进一步学习更复杂的算法和数据结构至关重要。
给出二叉树的中序遍历序列和后序遍历序列,编程还原该二叉树。 输入: 第1行为二叉树的中序遍历序列 第2行为二叉树的后序遍历序列 输出: 二叉树的按层遍历序列
这个是数据结构中关于二叉树的构造及遍历。
- **中序遍历**:在二叉树中,中序遍历的顺序为左-根-右,通常用于构造二叉搜索树的有序序列。 - **后序遍历**:二叉树的后序遍历为左-右-根,对于非空二叉树,后序遍历可以用来计算表达式的值(Lisp中的读-eval-...
实验中提供了`Creat_Bt`函数来创建二叉树,通过输入数据(整数和字符)来构造树的结构。在`main`函数中,先调用`Creat_Bt`创建二叉树,然后分别调用三个遍历函数,输出先序、中序和后序遍历的结果。 在实际实验过程...
本实验主要关注二叉树的构造和遍历,通过Visual C++ 6.0环境进行实现。实验的目的在于加深对二叉树逻辑结构和物理结构的理解,掌握二叉链表的使用,以及如何进行二叉树的各种遍历方法。 首先,二叉树的存储结构通常...
* 遍历-中序遍历-非递归 * 遍历-前序遍历-非递归 * 遍历-后序遍历-非递归 * 二叉查找树-两数之和 * 二叉查找树-中第K小的元素 * 二叉查找树-从有序数组中构造二叉查找树 * 二叉查找树-从有序链表构造平衡的二叉查找...
其中,二叉树的遍历是理解二叉树的基础之一,常见的遍历方法有先序遍历、中序遍历和后序遍历。 - **先序遍历**:访问顺序为“根—左—右”。 - **中序遍历**:访问顺序为“左—根—右”。 - **后序遍历**:访问顺序...
首先,我们要了解二叉树的三种基本遍历方式:前序遍历、中序遍历和后序遍历。这些遍历方法主要通过递归和非递归两种方式实现。 1. **前序遍历**(根-左-右):首先访问根节点,然后递归地遍历左子树,最后遍历右子...
例如,给定先序遍历序列`A B D H I E J C F G`和中序遍历序列`H D I B J E A F C G`,可以按照上述步骤构造出对应的二叉树,并验证其先序、中序、后序遍历序列是否匹配。 总之,理解二叉树的存储结构和遍历方法是...
二叉树是一种特殊的树结构,每个节点最多只有两个子节点,分为左子节点和右子节点。本问题涉及的核心知识点是二叉树的遍历及其构造。根据前序和中序遍历序列,我们可以唯一地恢复一棵二叉树。下面我们将详细探讨这个...
这可以通过已知的先序和中序遍历来构造二叉树,然后再进行后序遍历。 1. 首先,从先序遍历序列中找到根节点,它是序列中的第一个元素。 2. 接着,在中序遍历序列中找到根节点,将序列分为左右两部分,左侧是左子树...
二叉树的构造与前序遍历等基本操,简单的C++程序
- **构建表达式树**:前序遍历可以用来构造表达式树,方便进行表达式的求值。 - **压缩编码**:后序遍历在某些树形编码算法中起到关键作用,如霍夫曼编码。 - **数据序列化与反序列化**:将二叉树转换为线性序列(如...
文档可能包含以下内容:无根树的表示方法、树的遍历算法、树的性质、二叉树的特性、有根树的构造方法、以及转换过程中的注意事项。此外,可能还会涵盖相关的编程实现,如使用递归或栈队列进行树的遍历和构造。 理解...
二叉树的简单构造及二叉树的前中后不同方法的遍历
例如,前序遍历适合构造和复制二叉树,中序遍历通常用于构造二叉搜索树,后序遍历可用于计算表达式树的结果。层次遍历则常用于显示树的层次结构,如在图形界面中绘制树形视图。 对于二叉树的操作,除了遍历外,还...