Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1531763
  • 博文数量: 113
  • 博客积分: 3526
  • 博客等级: 中校
  • 技术积分: 1815
  • 用 户 组: 普通用户
  • 注册时间: 2009-09-08 09:46
个人简介

记录总结自己的工作

文章分类

全部博文(113)

文章存档

2015年(19)

2014年(10)

2013年(6)

2012年(16)

2011年(24)

2010年(21)

2009年(17)

分类: Java

2012-08-07 16:30:47

         首先创建节点类,并在里面添加了一个创建树的方法,调用后就可以返回一个包含7个节点的二叉树。

点击(此处)折叠或打开

  1. public class Node {
  2.     // 节点值
  3.     public int value;

  4.     // 左子节点
  5.     public Node left;

  6.     // 右子节点
  7.     public Node right;

  8.     Node(int va) {
  9.         value = va;
  10.     }

  11.     Node(int va, Node le, Node ri) {
  12.         value = va;
  13.         left = le;
  14.         ri = right;
  15.     }

  16.     /**
  17.      * 创建一颗二叉树
  18.      *
  19.      * @return 根节点
  20.      */
  21.     public static Node createTree() {
  22.         Node root = new Node(0);
  23.         Node node1 = new Node(1);
  24.         Node node2 = new Node(2);
  25.         Node node3 = new Node(3);
  26.         Node node4 = new Node(4);
  27.         Node node5 = new Node(5);
  28.         Node node6 = new Node(6);
  29.         Node node7 = new Node(7);

  30.         root.left = node1;
  31.         root.right = node2;
  32.         node1.left = node3;
  33.         node1.right = node4;
  34.         node2.left = node5;
  35.         node2.right = node6;
  36.         node3.left = node7;
  37.         return root;
  38.     }
  39. }

            创建遍历类,在该类里实现各种遍历方法。

点击(此处)折叠或打开

  1. import java.util.ArrayList;

  2. public class Traverse {

  3.     /**
  4.      * 递归前序遍历
  5.      *
  6.      * @param root
  7.      */
  8.     public void recursiveProOrder(Node root) {
  9.         // 遍历根节点
  10.         if (root != null) {
  11.             System.out.print(root.value);
  12.         }
  13.         // 遍历左子树
  14.         if (root.left != null) {
  15.             recursiveProOrder(root.left);
  16.         }
  17.         // 遍历右子树
  18.         if (root.right != null) {
  19.             recursiveProOrder(root.right);
  20.         }
  21.     }

  22.     /**
  23.      * 前序遍历
  24.      *
  25.      * @param root
  26.      */
  27.     public void proOrder(Node root) {
  28.         // 使用ArrayList作为堆栈
  29.         ArrayList<Node> stack = new ArrayList<Node>();
  30.         // 栈指针
  31.         int top = -1;
  32.         Node current = root;
  33.         while (true) {
  34.             if (current != null) {
  35.                 System.out.print(current.value);
  36.             }
  37.             // 右子节点进栈
  38.             if (current.right != null) {
  39.                 stack.add(current.right);
  40.                 top++;
  41.             }
  42.             // 左子节点进栈
  43.             if (current.left != null) {
  44.                 stack.add(current.left);
  45.                 top++;
  46.             }
  47.             // 如果栈内还有节点,栈顶节点出栈
  48.             if (top > -1) {
  49.                 current = stack.get(top);
  50.                 stack.remove(top--);
  51.             } else {
  52.                 break;
  53.             }
  54.         }
  55.     }

  56.     /**
  57.      * 递归中序遍历
  58.      *
  59.      * @param root
  60.      */
  61.     public void recursiveInOrder(Node root) {
  62.         if (root != null) {
  63.             if (root.left != null) {
  64.                 recursiveInOrder(root.left);
  65.             }
  66.             System.out.print(root.value);
  67.             if (root.right != null) {
  68.                 recursiveInOrder(root.right);
  69.             }
  70.         }
  71.     }

  72.     /**
  73.      * 中序遍历
  74.      *
  75.      * @param root
  76.      */
  77.     public void inOrder(Node root) {
  78.         if (root != null) {
  79.             ArrayList<Node> stack = new ArrayList<Node>();
  80.             int top = -1;
  81.             Node current = root;
  82.             while (current != null || top > -1) {
  83.                 if (current != null) {
  84.                     // 一直深入地寻找左子节点,并将路上的节点都进栈
  85.                     stack.add(current);
  86.                     top++;
  87.                     current = current.left;
  88.                 } else {
  89.                     // 取出栈顶节点,并继续遍历右子树
  90.                     current = stack.get(top);
  91.                     stack.remove(top--);
  92.                     System.out.print(current.value);
  93.                     current = current.right;
  94.                 }
  95.             }
  96.         }
  97.     }

  98.     /**
  99.      * 递归后续遍历
  100.      *
  101.      * @param root
  102.      */
  103.     public void recursivePostOrder(Node root) {
  104.         if (root != null) {
  105.             if (root.left != null) {
  106.                 recursivePostOrder(root.left);
  107.             }
  108.             if (root.right != null) {
  109.                 recursivePostOrder(root.right);
  110.             }
  111.             System.out.print(root.value);
  112.         }
  113.     }

  114.     /**
  115.      * 后序遍历:可以被遍历的节点都要进栈出栈两次,所以添加第二个栈用来标示进栈次数
  116.      *
  117.      * @param root
  118.      */
  119.     public void postOrder(Node root) {
  120.         if (root != null) {
  121.             // 用来保存节点的栈
  122.             ArrayList<Node> stack = new ArrayList<Node>();
  123.             // 用来保存标志位的栈
  124.             ArrayList<Integer> stack2 = new ArrayList<Integer>();
  125.             // 两个栈共用的栈指针
  126.             int top = -1;
  127.             int tag;
  128.             Node current = root;
  129.             do {
  130.                 //将所有左子节点进栈
  131.                 while (current != null) {
  132.                     stack.add(current);
  133.                     stack2.add(0);
  134.                     top++;
  135.                     current = current.left;
  136.                 }
  137.                 //取出栈顶节点,并判断其标志位
  138.                 current = stack.get(top);
  139.                 tag = stack2.get(top);
  140.                 stack2.remove(top);
  141.                 if (tag == 0) {
  142.                     // tag为0,表明该节点第一次进栈,还需要进栈一次,同时修改标志位
  143.                     current = current.right;
  144.                     stack2.add(1);
  145.                 } else {
  146.                     // tag不位0,表明非首次进栈,可以遍历了。
  147.                     stack.remove(top);
  148.                     top--;
  149.                     System.out.print(current.value);
  150.                     current = null;
  151.                 }
  152.             } while (current != null || top != -1);
  153.         }
  154.     }
  155. }
             实例化遍历类并调用各个遍历方法。
         点击(此处)折叠或打开
  1. public class Algorithm {

  2.     public static void main(String[] args) {

  3.          Node root=Node.createTree();
  4.          System.out.print("前序遍历: ");
  5.          new Traverse().proOrder(root);
  6.          System.out.println();
  7.          System.out.print("前序递归遍历: ");
  8.          new Traverse().recursiveProOrder(root);
  9.          System.out.println();
  10.          System.out.print("中序遍历: ");
  11.          new Traverse().inOrder(root);
  12.          System.out.println();
  13.          System.out.print("中序递归遍历: ");
  14.          new Traverse().recursiveInOrder(root);
  15.          System.out.println();
  16.          System.out.print("后序遍历: ");
  17.          new Traverse().postOrder(root);
  18.          System.out.println();
  19.          System.out.print("后序递归遍历: ");
  20.          new Traverse().recursivePostOrder(root);
  21.     }

输出结果:
前序遍历:        01374256
前序递归遍历: 01374256
中序遍历:        73140526
中序递归遍历: 73140526
后序遍历:        73415620
后序递归遍历: 73415620


阅读(7106) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~