- 浏览: 736554 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
lengzl:
请问,那个Node 是哪个包里面的类?
JAVA 二叉树的递归和非递归遍历 -
gongchuangsu:
总结的很好,感谢感谢
JAVA 二叉树的递归和非递归遍历 -
Caelebs:
666666666 居然是10年发的,难怪截屏自动保存的名字是 ...
截图工具 -
jijiqw:
是注解不是注释。。。
Spring @Transactional (一) -
letueo:
[b][b][b][b][b][b][b][b][b][b][ ...
Spring @Transactional (一)
着重介绍了非递归算法,特别是非递归后续遍历
package edu.cumt.jnotnull; import java.util.Stack; public class BinaryTree { protected Node root; public BinaryTree(Node root) { this.root = root; } public Node getRoot() { return root; } /** 构造树 */ public static Node init() { Node a = new Node('A'); Node b = new Node('B', null, a); Node c = new Node('C'); Node d = new Node('D', b, c); Node e = new Node('E'); Node f = new Node('F', e, null); Node g = new Node('G', null, f); Node h = new Node('H', d, g); return h;// root } /** 访问节点 */ public static void visit(Node p) { System.out.print(p.getKey() + " "); } /** 递归实现前序遍历 */ protected static void preorder(Node p) { if (p != null) { visit(p); preorder(p.getLeft()); preorder(p.getRight()); } } /** 递归实现中序遍历 */ protected static void inorder(Node p) { if (p != null) { inorder(p.getLeft()); visit(p); inorder(p.getRight()); } } /** 递归实现后序遍历 */ protected static void postorder(Node p) { if (p != null) { postorder(p.getLeft()); postorder(p.getRight()); visit(p); } } /** 非递归实现前序遍历 */ protected static void iterativePreorder(Node p) { Stack<Node> stack = new Stack<Node>(); if (p != null) { stack.push(p); while (!stack.empty()) { p = stack.pop(); visit(p); if (p.getRight() != null) stack.push(p.getRight()); if (p.getLeft() != null) stack.push(p.getLeft()); } } } /** 非递归实现前序遍历2 */ protected static void iterativePreorder2(Node p) { Stack<Node> stack = new Stack<Node>(); Node node = p; while (node != null || stack.size() > 0) { while (node != null) {//压入所有的左节点,压入前访问它 visit(node); stack.push(node); node = node.getLeft(); } if (stack.size() > 0) {// node = stack.pop(); node = node.getRight(); } } } /** 非递归实现后序遍历 */ protected static void iterativePostorder(Node p) { Node q = p; Stack<Node> stack = new Stack<Node>(); while (p != null) { // 左子树入栈 for (; p.getLeft() != null; p = p.getLeft()) stack.push(p); // 当前节点无右子或右子已经输出 while (p != null && (p.getRight() == null || p.getRight() == q)) { visit(p); q = p;// 记录上一个已输出节点 if (stack.empty()) return; p = stack.pop(); } // 处理右子 stack.push(p); p = p.getRight(); } } /** 非递归实现后序遍历 双栈法 */ protected static void iterativePostorder2(Node p) { Stack<Node> lstack = new Stack<Node>(); Stack<Node> rstack = new Stack<Node>(); Node node = p, right; do { while (node != null) { right = node.getRight(); lstack.push(node); rstack.push(right); node = node.getLeft(); } node = lstack.pop(); right = rstack.pop(); if (right == null) { visit(node); } else { lstack.push(node); rstack.push(null); } node = right; } while (lstack.size() > 0 || rstack.size() > 0); } /** 非递归实现后序遍历 单栈法*/ protected static void iterativePostorder3(Node p) { Stack<Node> stack = new Stack<Node>(); Node node = p, prev = p; while (node != null || stack.size() > 0) { while (node != null) { stack.push(node); node = node.getLeft(); } if (stack.size() > 0) { Node temp = stack.peek().getRight(); if (temp == null || temp == prev) { node = stack.pop(); visit(node); prev = node; node = null; } else { node = temp; } } } } /** 非递归实现后序遍历4 双栈法*/ protected static void iterativePostorder4(Node p) { Stack<Node> stack = new Stack<Node>(); Stack<Node> temp = new Stack<Node>(); Node node = p; while (node != null || stack.size() > 0) { while (node != null) { temp.push(node); stack.push(node); node = node.getRight(); } if (stack.size() > 0) { node = stack.pop(); node = node.getLeft(); } } while (temp.size() > 0) { node = temp.pop(); visit(node); } } /** 非递归实现中序遍历 */ protected static void iterativeInorder(Node p) { Stack<Node> stack = new Stack<Node>(); while (p != null) { while (p != null) { if (p.getRight() != null) stack.push(p.getRight());// 当前节点右子入栈 stack.push(p);// 当前节点入栈 p = p.getLeft(); } p = stack.pop(); while (!stack.empty() && p.getRight() == null) { visit(p); p = stack.pop(); } visit(p); if (!stack.empty()) p = stack.pop(); else p = null; } } /** 非递归实现中序遍历2 */ protected static void iterativeInorder2(Node p) { Stack<Node> stack = new Stack<Node>(); Node node = p; while (node != null || stack.size() > 0) { while (node != null) { stack.push(node); node = node.getLeft(); } if (stack.size() > 0) { node = stack.pop(); visit(node); node = node.getRight(); } } } /** * @param args */ public static void main(String[] args) { BinaryTree tree = new BinaryTree(init()); System.out.print(" Pre-Order:"); preorder(tree.getRoot()); System.out.println(); System.out.print(" In-Order:"); inorder(tree.getRoot()); System.out.println(); System.out.print("Post-Order:"); postorder(tree.getRoot()); System.out.println(); System.out.print(" Pre-Order:"); iterativePreorder(tree.getRoot()); System.out.println(); System.out.print("Pre-Order2:"); iterativePreorder2(tree.getRoot()); System.out.println(); System.out.print(" In-Order:"); iterativeInorder(tree.getRoot()); System.out.println(); System.out.print(" In-Order2:"); iterativeInorder2(tree.getRoot()); System.out.println(); System.out.print(" Post-Order:"); iterativePostorder(tree.getRoot()); System.out.println(); System.out.print("Post-Order2:"); iterativePostorder2(tree.getRoot()); System.out.println(); System.out.print("Post-Order3:"); iterativePostorder3(tree.getRoot()); System.out.println(); System.out.print("Post-Order4:"); iterativePostorder4(tree.getRoot()); System.out.println(); } }
发表评论
-
Servlet上传文件
2012-02-07 23:58 1453准备工作:要到http://commons.apache.or ... -
成为Java高手需要达到的25个学习目标--经典
2012-01-29 16:07 1308本文将告诉你学习Java需 ... -
Timer, Quartz 和 Spring 实现作业调度
2011-11-28 15:43 1148一、java.util.Timer ... -
Java 产生不重复的随机数
2011-06-22 23:32 2329int numberCount = 6; ... -
Date类学习总结(Calendar Date 字符串 相互转换 格式化)
2011-06-20 16:12 1632Date类学习总结 1.计算某一月份的最大天数 ... -
jsp中的cookie用法小实例
2011-06-20 00:13 2463这个小实例有三个页面 index.jsp页面内容如下: Y ... -
JS实现简单的增删改查
2011-06-19 23:41 12924<%@ page language="ja ... -
Jsp 动态显示系统时间
2011-06-19 23:24 4864<%@ page language=" ... -
java 动态显示时间
2011-06-19 23:13 4022import java.util.Date; p ... -
js 动态显示时间
2011-06-19 22:53 1798<%@ page language=" ... -
HTML 显示系统时间
2011-06-19 22:13 7842代码1:(显示静态时间) <script type=& ... -
JavaScript 动态显示系统时间
2011-06-19 19:36 2047JavaScript 动态显示系统时间 <html ... -
两例JavaScript 获取当前系统日期和时间
2011-06-19 19:20 1217两例JavaScript 获取当前系统日期和时间 QUOTE ... -
java五种JSP页面跳转方法详解
2011-06-19 17:08 14381. RequestDispatcher.forward() ... -
Java Object方法
2011-06-19 16:47 1272package com.abin.test.connectio ... -
Java 数组,List,Itarator循环
2011-06-19 16:01 2264package com.abin.test.connect ... -
JAVA DBClass操作数据库,这样算不算单列模式
2011-06-19 14:53 1214到底怎样才算单列模式,单列模式事什么概念 package c ... -
Oracle日期函数集锦
2011-06-16 20:55 868Oracle日期函数集锦(一) 一、 常用日期数据格式 1 ... -
java 页面传送数组
2011-06-15 14:56 25521.可以通过嵌入java代码调用session或者reques ... -
java Calendar当前时间
2011-06-14 13:40 1617Calendar c = Calendar.getIn ...
相关推荐
Java版二叉树遍历非递归程序,里面写的一般,希望大家喜欢!
详细介绍了JAVA中二叉树的非递归遍历方式,三种方式都是采用栈来辅助完成,其中前序遍历采用的是先入右子节点再入左子节点的方法,这样弹出栈时左在前,右在后。中序遍历的话则是要先一直到达最左的子节点,然后才弹...
已经经过不断的调试可以跑起来了 有详细的注释
java二叉树的遍历(递归和非递归).pdf
编写先序遍历二叉树的非递归算法程序,要求: (1)以二叉链表建立二叉树。 (2)输出遍历的结点序列。 (3)有实例验算。
java语言实现的二叉树的各种操作(包括递归与非递归遍历二叉树,求二叉树的高度,节点总数,叶子节点等)
java实现二叉树非递归前序中序后序遍历
如果你用C或者C++或者其他高级语言写过二叉树或者阅读过相关方面代码,应该知道二叉树的非递归遍历避不开通过栈或者队列实现。是的,python也一样。但是python自带的list功能很强大,即可以当stack
二叉树的非递归遍历运算 建立二叉树的三叉链式存储结构,在此基础上完成下列算法: 1) 从键盘上输入二叉树的各个结点,建立三叉链表 2) 输出该二叉树 3) 非递归的层次遍历算法 4) 非递归的先序遍历、中序遍历、...
结构清晰地介绍了二叉树的遍历方法 前序 中序 后序 都有,附带详细的注释,希望像能对和我一样入门级的朋友们有所帮助
二叉树的前序遍历、中序遍历、后序遍历的递归和非递归方法的java实现。
非递归中序遍历二叉树
利用java编写的二叉树的遍历,包括前序,中序以及后序,遍历方式包含递归和非递归,值得学习。
结构清晰地介绍了二叉树的遍历方法,希望像能对和我一样入门级的朋友们有所帮助
二叉树的遍历顺序及方法可参考之前写过的二叉树的遍历(JAVA递归和非递归版)这里解决的是如何根据给定的遍历序列构造二叉树的问题。 根据前序与中序遍历序列构造二叉树 该问题中,会给出二叉树的前序与中序的遍历...
给定先序中序序列,递归建立二叉树,并遍历
用Java编写的树的可视化与非递归的遍历
java实现二叉树的遍历,包括前序中序后序遍历,递归和非递归实现。
java实现创建二叉树,并且遍历二叉树(此处使用非递归方式遍历); 用出栈入栈的方式遍历二叉树。
1:构造一个二叉树 2:二叉树前序遍历(递归) 3:二叉树中序遍历(递归) 4:二叉树后续遍历(递归) 5:二叉树前序遍历(非递归) 6:二叉树中序遍历(非递归) 7:二叉树后序遍历(非递归)