二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。
Java实现二叉树遍历算法相关代码如下:
package cn.xj.bitree; public class BiTreeNode { private char data; private BiTreeNode leftNode; private BiTreeNode rightNode; public BiTreeNode(char data, BiTreeNode leftNode, BiTreeNode rightNode) { this.data = data; this.leftNode = leftNode; this.rightNode = rightNode; } public char getData() { return data; } public void setData(char data) { this.data = data; } public BiTreeNode getLeftNode() { return leftNode; } public void setLeftNode(BiTreeNode leftNode) { this.leftNode = leftNode; } public BiTreeNode getRightNode() { return rightNode; } public void setRightNode(BiTreeNode rightNode) { this.rightNode = rightNode; } }
package cn.xj.bitree; import java.util.Stack; public class BiTree { private BiTreeNode rootNode; public BiTree(BiTreeNode rootNode) { this.rootNode = rootNode; } public BiTreeNode getRootNode() { return rootNode; } //构造树 public static BiTreeNode init(){ BiTreeNode a = new BiTreeNode('A',null,null); BiTreeNode b = new BiTreeNode('B', null, a); BiTreeNode c = new BiTreeNode('C',null,null); BiTreeNode d = new BiTreeNode('D', b, c); BiTreeNode e = new BiTreeNode('E',null,null); BiTreeNode f = new BiTreeNode('F', e, null); BiTreeNode g = new BiTreeNode('G', null, f); BiTreeNode h = new BiTreeNode('H', d, g); return h;// root } //打印节点 public void visit(BiTreeNode node){ System.out.print(node.getData()+""); } //递归 /**递归实现前序遍历:根首先访问*/ public void preOrder(BiTreeNode node){ if(node!=null){ visit(node); preOrder(node.getLeftNode()); preOrder(node.getRightNode()); } } /**递归实现中序遍历:根中间访问*/ public void midOrder(BiTreeNode node){ if(node!=null){ midOrder(node.getLeftNode()); visit(node); midOrder(node.getRightNode()); } } /**递归实现后序遍历:根最后访问*/ public void poster(BiTreeNode node){ if(node!=null){ poster(node.getLeftNode()); poster(node.getRightNode()); visit(node); } } //非递归 /**非递归前序遍历*/ public void iterativePre(BiTreeNode node){ Stack<BiTreeNode> stack = new Stack<BiTreeNode>(); if(node!=null){ stack.push(node); while(!stack.isEmpty()){ node = stack.pop(); visit(node); //先访问根节点,栈底节点 if(node.getRightNode()!=null) stack.push(node.getRightNode());//右节点进栈,等同于stack.add(node.getRightNode()); if(node.getLeftNode()!=null) stack.push(node.getLeftNode()); //左节点进栈stack.add(node.getLeftNode()); } } } /**非递归实现中序遍历*/ public void iterativeMid(BiTreeNode p){ Stack<BiTreeNode> stack = new Stack<BiTreeNode>(); while (p != null) { //先按右中左的顺序把所有节点放入栈; while(p!=null){ if(p.getRightNode()!=null) stack.push(p.getRightNode());// 当前节点右子入栈 stack.push(p);// 当前节点入栈 p = p.getLeftNode(); } p = stack.pop(); while(!stack.empty()&&p.getRightNode()==null){ visit(p); p = stack.pop(); } visit(p); if(!stack.empty()) p = stack.pop(); else p = null; } } /**非递归实现后序遍历*/ public void iterativePost(BiTreeNode p){ BiTreeNode q = p; Stack<BiTreeNode> stack = new Stack<BiTreeNode>(); while(p!=null){ //左子树入栈 for(;p.getLeftNode()!=null;p=p.getLeftNode()) stack.push(p); //当前节点无右子或右子已经输出 while(p!=null&&(p.getRightNode()==null||p.getRightNode()==q)){ visit(p); q=p;//记录上一个已输出节点 if(stack.empty()) return; p = stack.pop(); } //处理右子节点 stack.push(p); p=p.getRightNode(); } } public static void main(String[] args){ BiTree tree = new BiTree(init()); /**递归*/ System.out.print("Pre-Order:"); tree.preOrder(tree.getRootNode()); System.out.println(); System.out.print("Mid-Order:"); tree.midOrder(tree.getRootNode()); System.out.println(); System.out.print("Post-Order:"); tree.poster(tree.getRootNode()); System.out.println("\r\n------------"); /**非递归*/ System.out.print("非递归Pre-Order:"); tree.iterativePre(tree.getRootNode()); System.out.println(); System.out.print("非递归Mid-Order:"); tree.iterativeMid(tree.getRootNode()); System.out.println(); System.out.print("非递归Post-Order:"); tree.iterativePost(tree.getRootNode()); } }
相关推荐
二叉树遍历的特点
数据结构课程设计--二叉树遍历及其应用、对树的先序遍历、后序遍历、中序遍历、层序遍历、二叉树的深度及其叶子树、并打印树形。
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;...ABCDEFG【选做内容】采用非递归算法实现二叉树遍历。
实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...
二叉树遍历的非递归操作二叉树遍历的非递归操作
一个实现二叉树遍历的程序代码,有先序,中序和后序。
易语言二叉树遍历源码,二叉树遍历,二叉树_取下级树,内存_读整数内存,读整数内存_
二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题...
运用C语言编写的二叉树遍历程序 先序遍历·中序遍历·后序遍历
java 写的算24程序。用两种二叉树遍历,并规整输出字符串
二叉树遍历 二叉树遍历
二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法
用堆栈实现二叉树遍历,C语言实现的数据结构
遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
数据结构第七章二叉树遍历的源代码,有用有用~~按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树...
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
利用二叉树遍历算法的框架和思路,假设访问结点的具体操作不仅仅局限于输出结点数据域的值,而把访问延伸到对结点的判别、计数等其他操作。这样可以解决一些关于二叉树的其他实际问题。(1) 统计二叉树中结点总数m...
二叉树遍历操作.cpp
二叉树遍历问题-二叉树遍历问题