1 概念
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点 。
二叉树的遍历：
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示
2 数据结构：
3 代码实现
节点类：
/** * @author 17122 * 节点类 */ public class Node<E> { /** * 节点的权(值) */ private E value; /** * 左儿子 */ Node<E> leftNode; /** * 右儿子 */ Node<E> rightNode; public Node(E value) { this.value = value; } /** * 设置左儿子 * * @param leftNode */ public void setLeftNode(Node<E> leftNode) { this.leftNode = leftNode; } /** * 设置右儿子 * * @param rightNode */ public void setRightNode(Node<E> rightNode) { this.rightNode = rightNode; } /** * 前序遍历 */ public void frontShow() { //先遍历当前节点的内容 System.out.print(value + " "); //左节点 if (leftNode != null) { leftNode.frontShow(); } //右节点 if (rightNode != null) { rightNode.frontShow(); } } /** * 中序遍历 */ public void midShow() { //左子节点 if (leftNode != null) { leftNode.midShow(); } //当前节点 System.out.print(value + " "); //右子节点 if (rightNode != null) { rightNode.midShow(); } } /** * 后序遍历 */ public void afterShow() { //左子节点 if (leftNode != null) { leftNode.afterShow(); } //右子节点 if (rightNode != null) { rightNode.afterShow(); } //当前节点 System.out.print(value + " "); } }
二叉树类：
/** * @author 17122 * 二叉树类 */ public class MyBinaryTree<E> { private Node<E> root; public MyBinaryTree() { this.root = null; } public MyBinaryTree(Node<E> root) { this.root = root; } /** * 设置根节点 * * @param root */ public void setRoot(Node<E> root) { this.root = root; } /** * 获取根节点 * * @return */ public Node<E> getRoot() { return root; } /** * 前序遍历 */ public void frontShow() { if (root != null) { root.frontShow(); } } /** * 中序遍历 */ public void midShow() { if (root != null) { root.midShow(); } } /** * 后序遍历 */ public void afterShow() { if (root != null) { root.afterShow(); } } }
测试：
/** * 测试方法 * * @param args */ public static void main(String[] args) { MyBinaryTree tree = new MyBinaryTree(); Node root = new Node(1); root.leftNode = new Node(2); root.rightNode = new Node(3); tree.setRoot(root); tree.frontShow(); System.out.println(); tree.afterShow(); }
输出：
