`
xitongyunwei
  • 浏览: 916113 次
文章分类
社区版块
存档分类
最新评论

二叉树(2)——遍历的非递归实现

 
阅读更多


算法概述

递归算法简洁明了、可读性好,但与非递归算法相比要消耗更多的时间和存储空间。为提高效率,我们可采用一种非递归的二叉树遍历算法。非递归的实现要借助栈来实现,因为堆栈的先进后出的结构和递归很相似。

对于中序遍历来说,非递归的算法比递归算法的效率要高的多。其中序遍历算法的实现的过程如下:

(1).初始化栈,根结点进栈;

(2).若栈非空,则栈顶结点的左孩子结点相继进栈,直到null(到叶子结点时)退栈;访问栈顶结点(执行visit操作)并使栈顶结点的右孩子结点进栈成为栈顶结点。

(3).重复执行(2),直至栈为空。

算法实现

package datastructure.tree;

import datastructure.stack.ArrayStack;
import datastructure.stack.Stack;

public class UnrecOrderBTree implements Visit{
	private Stack stack = new ArrayStack();
	private BTree bt;
	@Override
	public void visit(BTree btree) {
		System.out.print("\t" + btree.getRootData());
	}
	
	public void inOrder(BTree boot) {
		stack.clear();
		stack.push(boot);
		while(!stack.isEmpty()) {
			//左孩子结点进栈
			while((bt = ((BTree)(stack.peek())).getLeftChild()) != null) {
				stack.push(bt);
			}
			//如果该结点没有右孩子,则逐级往上出栈
			while(!stack.isEmpty() &&!( (BTree)stack.peek() ).hasRightTree()) {
				bt = (BTree)stack.pop();
				visit(bt);
			}
			//如果该结点有右孩子,则右孩子进栈
			if(!stack.isEmpty() && ( (BTree)stack.peek() ).hasRightTree()){
				bt = (BTree)stack.pop();
				visit(bt);
				stack.push(bt.getRightChild());
			}
		}
	}

}


测试:



要构建的树

package datastructure.tree;
/**
 * 测试二叉树
 * @author Administrator
 *
 */
public class BTreeTest {
	public static void main(String args[]) {
		BTree btree = new LinkBTree('A');
		BTree bt1, bt2, bt3, bt4;
		bt1 = new LinkBTree('B');
		btree.addLeftTree(bt1);
		bt2 = new LinkBTree('D');
		bt1.addLeftTree(bt2);
		
		bt3 =  new LinkBTree('C');
		btree.addRightTree(bt3);
		bt4 =  new LinkBTree('E');
		bt3.addLeftTree(bt4);
		bt4 =  new LinkBTree('F');
		bt3.addRightTree(bt4);
		
		RecursionOrderBTree order = new RecursionOrderBTree();
		System.out.println("\n中序遍历:");
		order.inOrder(btree);
		
	}
}

结果如下:


中序遍历:
D B AE C F

分享到:
评论

相关推荐

    二叉树的遍历——递归以及非递归实现

    vs2010下运行编写,使用了STL栈,实现了基本的插入、删除、计算深度、查找,主要是遍历,包括递归遍历,以及非递归的前序中序后序遍历,每个函数都有测试用例,如果存在错误,请在给我留言。

    数据结构实验——二叉树的建立和遍历.zip

    2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问结点的操作修改为叶结点计数,统计度为0的;度为1...

    c++实现二叉树的4种遍历(递归和非递归)(csdn)————程序.pdf

    c++实现二叉树的4种遍历(递归和非递归)(csdn)————程序

    栈的应用——二叉树的前序、中序、后序非递归遍历算法

    栈的应用——二叉树的前序、中序、后序非递归遍历算法

    c++编写二叉树遍历(前中后序——递归与非递归)

    数据结构中二叉树遍历,两种方法,递归与非递归,vs2008测试通过。

    二叉树的形成和三种非递归遍历

    二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态: (1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)右子树为空的二叉树——(c); (4)左子树为空的二叉树——(d); (5)完全...

    实用《数据结构》编程——二叉树的建立、中序遍历非递归C程序.pdf

    #资源达人分享计划#

    数据结构实验——二叉树的存储与遍历

    实验要求: (1)采用链式存储结构建立...(2)二叉树的建立采用递归方式实现,先序遍历、中序遍历、后序遍历均采用非递归方式实现。 (3)在主函数中分别调用以上四个算法函数(建立二叉树,先序、中序、后序遍历二叉树)。

    数据结构的二叉树的应用——MFC

    数据结构的二叉树的应用——MFC 【问题描述】设计出二叉链表...(4)要求实现二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法。 (5)二叉树中存储的结点可以是数值可以是字符或者记录等等。

    C语言数据结构-用递归、非递归两种方法遍历二叉树

    三种遍历方法的非递归实现方法。 先序:对于任一节点P, (1)输出节点P,然后将其入栈,再看P的左孩子是否为空; (2)若P的左孩子不为空,则置P的左孩子为当前节点,重复(1)的操作; (3)若P的左孩子为空,则将...

    北京邮电大学_信通院_数据结构_二叉树 C++

    使用非递归方式编写新的二叉 树的构造函数,建立二叉树。提示:可以使用 STL 中的 stack 来辅助实现。 2、若二叉树的每一个结点具有数值,如何搜索二叉树,找到指定值的叶子结点? 3、若已知叶子结点的指针,如何...

    第五章 树与二叉树

    5.5.1 前序遍历非递归算法 关键:在前序遍历过某个左子树后,如何找到该结点的右子树的根指针。 一般的前序遍历执行过程中,设要遍历二叉树的根指针为bt,可能出现两种情况: (1)若bt!=NULL,则表明当前二叉树不...

    C语言——二叉树的基本操作

    建立一颗二叉树,并用递归或非递归的算法选用先序、中序和后序遍历

    数据结构——二叉树 线索化二叉树 C语言

    中序线索二叉树,反方向进行中序遍历(要求非递归,顺前驱进行)。 (1)建立二叉树; (2) 按先序、中序、后序输出二叉树; (3)复制二叉树; (4)在字符模式下画出无缺陷的二叉树

    数据结构实验——二叉树相关操作

    本人本科期间数据结构二叉树的实验 ...2、先序、中序、后序遍历二叉树(要求任选某一种用非递归算法完成) 3、查询二叉树中某个结点 4、统计二叉树中叶子结点的个数 5、求二叉树的深度 6、要求有菜单

    C语言:二叉树的各种操作(内附具体代码和思路).docx

    数据结构的重要部分——二叉树,这里主要是完成二叉树的建立、前中后序遍历(其中中序和后序遍历以非递归的形式完成)、交换子树、计算树的高度等操作,学习二叉树的小伙伴可以来看看噢

    华南 数据结构上机实验代码 完整代码

    归并排序(非递归算法) 基数排序 实现图的存储结构 图的深度遍历 图的广度遍历 二叉排序树的复制 计算二叉树的结点个数 删除单链性表中值相同的多余结点 删除线性表中所有值为x的元素 Josephus问题 利用...

    严蔚敏 数据结构(C语言版) 代码 23490 书中算法

    3.3.4 将递归转换为非递归的方法 60 3.4 队列 61 3.4.1 队列的类型定义 61 3.4.2 循环队列——队列的顺序表示和实现 62 3.4.3 链队——队列的链式表示和实现 65 3.5 队列的应用 67 3.6 小结 69 习题 ...

    〈数据结构〉课程设计报告

    建立排序二叉树就是,就是将各结点...为实现二叉树的非递归算法,需要设置一个栈来保存指向结点的指针,以便在遍历某结点的左子树后,由这个指针能找到该结点的右子树。栈中的地址是随着结点的遍历次序而动态变化的。

    数据结构与算法综合资料库.CHM

    汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有...

Global site tag (gtag.js) - Google Analytics