`

二叉树的三种遍历

    博客分类:
  • Java
阅读更多
前序遍历(DLR)   前序遍历也叫做先根遍历,可记做根左右。
中序遍历(LDR)   中序遍历也叫做中根遍历,可记做左根右。
后序遍历(LRD)   后序遍历也叫做后根遍历,可记做左右根。


import java.util.LinkedList;
import java.util.List;

/**
 * 功能:把一个数组的值存入二叉树中,然后进行3种方式的遍历
 * 
 * 参考资料0:数据结构(C语言版)严蔚敏
 * 
 * 参考资料1:http://zhidao.baidu.com/question/81938912.html
 * 
 * 参考资料2:http://cslibrary.stanford.edu/110/BinaryTrees.html#java
 * 
 * @author ocaicai@yeah.net @date: 2011-5-17
 * 
 */
public class BinTreeTraverse2 {

	private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	private static List<Node> nodeList = null;

	/**
	 * 内部类:节点
	 * 
	 * @author ocaicai@yeah.net @date: 2011-5-17
	 * 
	 */
	private static class Node {
		Node leftChild;
		Node rightChild;
		int data;

		Node(int newData) {
			leftChild = null;
			rightChild = null;
			data = newData;
		}
	}

	public void createBinTree() {
		nodeList = new LinkedList<Node>();
		// 将一个数组的值依次转换为Node节点
		for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
			nodeList.add(new Node(array[nodeIndex]));
		}
		// 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树
		for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
			// 左孩子
			nodeList.get(parentIndex).leftChild = nodeList
					.get(parentIndex * 2 + 1);
			// 右孩子
			nodeList.get(parentIndex).rightChild = nodeList
					.get(parentIndex * 2 + 2);
		}
		// 最后一个父节点:因为最后一个父节点可能没有右孩子,所以单独拿出来处理
		int lastParentIndex = array.length / 2 - 1;
		// 左孩子
		nodeList.get(lastParentIndex).leftChild = nodeList
				.get(lastParentIndex * 2 + 1);
		// 右孩子,如果数组的长度为奇数才建立右孩子
		if (array.length % 2 == 1) {
			nodeList.get(lastParentIndex).rightChild = nodeList
					.get(lastParentIndex * 2 + 2);
		}
	}

	/**
	 * 先序遍历
	 * 
	 * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已
	 * 
	 * @param node
	 *            遍历的节点
	 */
	public static void preOrderTraverse(Node node) {
		if (node == null)
			return;
		System.out.print(node.data + " ");
		preOrderTraverse(node.leftChild);
		preOrderTraverse(node.rightChild);
	}

	/**
	 * 中序遍历
	 * 
	 * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已
	 * 
	 * @param node
	 *            遍历的节点
	 */
	public static void inOrderTraverse(Node node) {
		if (node == null)
			return;
		inOrderTraverse(node.leftChild);
		System.out.print(node.data + " ");
		inOrderTraverse(node.rightChild);
	}

	/**
	 * 后序遍历
	 * 
	 * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已
	 * 
	 * @param node
	 *            遍历的节点
	 */
	public static void postOrderTraverse(Node node) {
		if (node == null)
			return;
		postOrderTraverse(node.leftChild);
		postOrderTraverse(node.rightChild);
		System.out.print(node.data + " ");
	}

	public static void main(String[] args) {
		BinTreeTraverse2 binTree = new BinTreeTraverse2();
		binTree.createBinTree();
		// nodeList中第0个索引处的值即为根节点
		Node root = nodeList.get(0);

		System.out.println("先序遍历:");
		preOrderTraverse(root);
		System.out.println();

		System.out.println("中序遍历:");
		inOrderTraverse(root);
		System.out.println();

		System.out.println("后序遍历:");
		postOrderTraverse(root);
	}

}
分享到:
评论

相关推荐

    二叉树三种遍历算法的源码背诵版

    二叉树三种遍历算法的源码背诵版 二叉树是一种常用的数据结构,在计算机科学和软件工程中应用非常广泛。二叉树的遍历是指从根节点出发,按照某种顺序访问二叉树中的所有节点。二叉树的遍历有多种方式,本文将详细...

    二叉树三种遍历,先序和中序建立二叉树,后序和中序建立二叉树,二叉搜索树查找,删除,插入

    大连理工大学数据结构上机 二叉树三种遍历,先序和中序建立二叉树,后序和中序建立二叉树,二叉搜索树查找,删除,插入

    二叉树三种遍历动画演示

    本资源“二叉树三种遍历动画演示”提供了对二叉树遍历方法的直观理解,通过动态的动画形式帮助学习者更好地掌握这些概念。 1. 前序遍历(Preorder Traversal): 前序遍历遵循“根-左-右”的访问顺序。首先访问根...

    数据结构 二叉树三种遍历的非递归算法(背诵版).doc

    本资料“数据结构 二叉树三种遍历的非递归算法(背诵版)”着重介绍了二叉树的三种主要遍历方法——前序遍历、中序遍历和后序遍历的非递归实现。 **前序遍历**: 前序遍历的顺序是:根节点 -&gt; 左子树 -&gt; 右子树。非...

    数据结构二叉树三种遍历

    "数据结构二叉树三种遍历" 二叉树是一种基本的数据结构,它广泛应用于计算机科学和信息技术领域。二叉树的遍历是指从二叉树的根结点出发,访问树中所有结点的过程。二叉树的遍历有三种方式:先序遍历、中序遍历和...

    C语言二叉树三种遍历算法及其广义表表示

    C语言二叉树三种遍历算法及其广义表表示 VS2012编写 基于先序遍历的构造算法:输入是二叉树的先序序列,但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用’.’字符表示。 分别利用先序遍历、中序遍历、...

    链式二叉树三种遍历

    【先序遍历】:先访问根节点,然后先序遍历左子树,再先序遍历右子树! 【中序遍历】:中序遍历左子树,然后访问根节点,再中序遍历右子树! 【后序遍历】:后序遍历左子树,然后后序遍历右子树,再访问根节点!

    二叉树三种遍历算法算法实现

    本文将详细介绍二叉树的三种基本遍历算法:前序遍历、中序遍历和后序遍历,并通过给定的代码示例进行深入解析。 ### 1. 二叉树的基本概念 二叉树是一种每个节点最多有两个子节点的树结构,这两个子节点分别被称为...

    二叉树的三种遍历代码

    本主题主要讨论二叉树的三种遍历方法:前序遍历、中序遍历和后序遍历。 1. **前序遍历**(根-左-右): - 首先访问根节点。 - 然后递归地访问左子树。 - 最后递归地访问右子树。 2. **中序遍历**(左-根-右):...

    二叉树的先序遍历

    c语言中关于二叉树的先序遍历,链表的创建

    二叉树先序、中序、后序三种遍历的非递归算法

    常见的二叉树遍历方法有三种:先序遍历、中序遍历和后序遍历。下面我们将讨论这三种遍历方法的非递归算法。 一、先序遍历非递归算法 先序遍历是指先访问根结点,然后访问左子树,最后访问右子树。非递归算法使用栈...

    二叉树建立及遍历算法实现

    建立二叉树,实现二叉树的先序、中序、后序的递归遍历算法,输出遍历结果。 实现二叉树的先序、中序、后序和层次遍历的非递归算法,输出遍历结果。

    完全二叉树的层序遍历-labview

    完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全...

    C言语 二叉树的三种遍历

    本项目以“C语言 二叉树的三种遍历”为主题,涵盖了前序遍历、中序遍历和后序遍历的基本概念、实现方法和实际应用。 1. 前序遍历(Preorder Traversal):前序遍历的顺序是根节点 -&gt; 左子树 -&gt; 右子树。在C语言中,...

    C++ 二叉树的先序遍历、中序遍历和后序遍历非递归算法

    用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。

    二叉树三种遍历算法的源码背诵版_.pdf

    二叉树的遍历是访问树中所有结点的过程,常见的遍历方式有三种:先序遍历、中序遍历和后序遍历。在本篇文档中,我们主要关注这三种遍历的非递归实现,这对于理解和掌握二叉树的操作非常关键,特别是在考研或面试中...

    二叉树三种遍历的非递归算法(背诵版)

    常见的二叉树遍历方法有三种:先序遍历、中序遍历和后序遍历。通常我们使用递归的方式来实现这三种遍历,但递归方法在某些情况下可能会导致栈溢出或者效率较低。因此,非递归算法的实现变得很有必要,特别是在面试或...

Global site tag (gtag.js) - Google Analytics