java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
本篇文章主要介绍了图解二叉树的三种遍历方式及 java 实现代码,具有一定的参考价值,有兴趣的可以了解一下
二叉树 (binary tree) 是一颗树,其中每个节点都不能有多于两个的儿子。
1. 二叉树节点作为图的特殊形式,二叉树的基本组成单元是节点与边;作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用。
如下,给出了二叉树节点的数据结构图示和相关代码:
2. 递归遍历
- // 定义节点类:
- private static class BinNode {
- private Object element;
- private BinNode lChild; // 定义指向左子树的指针
- private BinNode rChild; // 定义指向右子树的指针
- public BinNode(Object element, BinNode lChild, BinNode rChild) {
- this.element = element;
- this.lChild = lChild;
- this.rChild = rChild;
- }
- }
二叉树本身并不具有天然的全局次序,故为实现遍历,需通过在各节点与其孩子之间约定某种局部次序,间接地定义某种全局次序。
按惯例左兄弟优先于右兄弟,故若将节点及其孩子分别记作 V、L 和 R,则下图所示,局部访问的次序可有 VLR、LVR 和 LRV 三种选择。根据节点 V 在其中的访问次序,三种策略也相应地分别称作先序遍历、中序遍历和后序遍历,下面将分别介绍。
2.1 先序遍历图示:
代码实现:
2.2 中序遍历
- /**
- * 对该二叉树进行前序遍历 结果存储到list中 前序遍历
- */
- public static void preOrder(BinNode node) {
- list.add(node); // 先将根节点存入list
- // 如果左子树不为空继续往左找,在递归调用方法的时候一直会将子树的根存入list,这就做到了先遍历根节点
- if (node.lChild != null) {
- preOrder(node.lChild);
- }
- // 无论走到哪一层,只要当前节点左子树为空,那么就可以在右子树上遍历,保证了根左右的遍历顺序
- if (node.rChild != null) {
- preOrder(node.rChild);
- }
- }
图示:
代码实现:
2.3 后序遍历
- /**
- * 对该二叉树进行中序遍历 结果存储到list中
- */
- public static void inOrder(BinNode node) {
- if (node.lChild != null) {
- inOrder(node.lChild);
- }
- list.add(node);
- if (node.rChild != null) {
- inOrder(node.rChild);
- }
- }
实例图示:
代码实现:
- /**
- * 对该二叉树进行后序遍历 结果存储到list中
- */
- public static void postOrder(BinNode node) {
- if (node.lChild != null) {
- postOrder(node.lChild);
- }
- if (node.rChild != null) {
- postOrder(node.rChild);
- }
- list.add(node);
- }
附:测试相关代码
- private static BinNode root;
- private static List < BinNode > list = new ArrayList < BinNode > ();
- public static void main(String[] args) {
- init();
- // TODO Auto-generated method stub
- //preOrder(root);
- //inOrder(root);
- postOrder(root);
- for (int i = 0; i < list.size(); i++) {
- System.out.print(list.get(i).element + " ");
- }
- }
- // 树的初始化:先从叶节点开始,由叶到根
- public static void init() {
- BinNode b = new BinNode("b", null, null);
- BinNode a = new BinNode("a", null, b);
- BinNode c = new BinNode("c", a, null);
- BinNode e = new BinNode("e", null, null);
- BinNode g = new BinNode("g", null, null);
- BinNode f = new BinNode("f", e, g);
- BinNode h = new BinNode("h", f, null);
- BinNode d = new BinNode("d", c, h);
- BinNode j = new BinNode("j", null, null);
- BinNode k = new BinNode("k", j, null);
- BinNode m = new BinNode("m", null, null);
- BinNode o = new BinNode("o", null, null);
- BinNode p = new BinNode("p", o, null);
- BinNode n = new BinNode("n", m, p);
- BinNode l = new BinNode("l", k, n);
- root = new BinNode("i", d, l);
- }
来源: http://www.phperz.com/article/17/1230/356600.html