用递归和非递归的方法遍历二叉树.
先建立一个二叉树:
代码如下:
static class Node { Node left; Node right; String value; public Node(String value, Node left, Node right){ this.value = value; this.left = left; this.right = right; } } public static Node creatTree(){ //左子树 Node k = new Node("k", null, null); Node l = new Node("l", null, null); Node h = new Node("h", k, l); Node i = new Node("i", null, null); Node e = new Node("e", h, i); Node d = new Node("d", null, null); Node b = new Node("b", d, e); //右子树 Node j = new Node("j", null, null); Node g = new Node("g", null, j); Node f = new Node("f", null, null); Node c = new Node("c", f, g); Node a = new Node("a", b, c); return a; } /** * 深度优先,递归遍历(前序,中序,后续) * @param root */ public static void recursionDepthFirst(Node node){ if(node == null){ return; } //前序System.out.println(node.value); recursionDepthFirst(node.left); //中序System.out.println(node.value); recursionDepthFirst(node.right); //后序System.out.println(node.value); } /** * 深度优先,非递归遍历(前序,中序) * @param node */ public static void inOrPreOrderDepthFirst(Node node){ Stack<Node> stack = new Stack<Node>(); while(node != null || !stack.isEmpty()){ while(node != null){ //前序System.out.println(node.value); stack.push(node); node = node.left; } if(!stack.isEmpty()){ node = stack.pop(); //中序System.out.println(node.value); node = node.right; } } } /** * 深度优先,非递归遍历(后序) * @param node */ public static void postOrderDepthFirst(Node node){ Stack<Node> stack = new Stack<Node>(); //待实现 } /** * 宽度优先遍历 */ public static void breadthFirst(Node node){ Queue<Node> queue = new LinkedList<Node>(); queue.add(node); while(!queue.isEmpty()){ Node n = queue.poll(); System.out.println(n.value); if(n.left != null){ queue.add(n.left); } if(n.right != null){ queue.add(n.right); } } }
其中非递归方式遍历有很多写法,可以看 http://robinsoncrusoe.iteye.com/blog/808526
相关推荐
二叉树遍历的特点
数据结构课程设计--二叉树遍历及其应用、对树的先序遍历、后序遍历、中序遍历、层序遍历、二叉树的深度及其叶子树、并打印树形。
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;...ABCDEFG【选做内容】采用非递归算法实现二叉树遍历。
实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...
二叉树遍历的非递归操作二叉树遍历的非递归操作
一个实现二叉树遍历的程序代码,有先序,中序和后序。
易语言二叉树遍历源码,二叉树遍历,二叉树_取下级树,内存_读整数内存,读整数内存_
二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题...
运用C语言编写的二叉树遍历程序 先序遍历·中序遍历·后序遍历
java 写的算24程序。用两种二叉树遍历,并规整输出字符串
二叉树遍历 二叉树遍历
二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法
用堆栈实现二叉树遍历,C语言实现的数据结构
遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
数据结构第七章二叉树遍历的源代码,有用有用~~按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树...
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
利用二叉树遍历算法的框架和思路,假设访问结点的具体操作不仅仅局限于输出结点数据域的值,而把访问延伸到对结点的判别、计数等其他操作。这样可以解决一些关于二叉树的其他实际问题。(1) 统计二叉树中结点总数m...
二叉树遍历操作.cpp
二叉树遍历问题-二叉树遍历问题