二叉树的前序遍历、中序遍历和后序遍历及其算法
本文由发表于7年前 | 数据结构与算法 | 评论数 1 |  被围观 29,746 views+

二叉树的基本的遍历规则有三种:前序遍历,中序遍历和后序遍历。对于每一种遍历,树中每个结点都要经过3次。前序遍历在第一次遇到结点时立即访问,中序遍历第二次遇到结点时访问,后序遍历则到第三次遇到结点时才访问。

以一棵二叉树说明其三种遍历顺序:
二叉树的前序遍历

二叉树的前序遍历

前序遍历:- + a * b – c d / e f
中序遍历:a + b * c – d – e / f
后序遍历:a b c d – * + e f / -
前序遍历算法:
template<class T>
void BinaryTree<T>::PreOrder(BinTreeNode<T> *subTree,
		       void (*visit)(BinTreeNode<T> *P)) {
	//递归函数:此算法按照前序遍历以subTree为根的二叉树。
	if(subTree!=NULL){		//递归结束条件
		visit(subTree);		//访问根节点
		PreOrder(subTree->leftChild,visit);	//前序遍历根的左子树
		PreOrder(subTree->rightChild,visit);	//前序遍历根的右子树
	}
};
中序遍历算法:
template<class T>
void BinaryTree<T>::InOrder(BinTreeNode<T> *subTree,
		       void(*visit)(BinTreeNode<T> *p)){
	//递归函数:此算法按照中序次序遍历以subTree为根的子数
	if(subTree!=NULL) {		//如果subTree为NULL,则结束递归
		InOrder(subTree->leftChild,visit);	//中序遍历根的左子树
		visit(subTree);	//访问根节点
		InOrder(subTree->rightChild,visit);	//中序遍历根的右子数
	}
};
后序遍历算法:
template<class T>
void BinaryTree<T>::PostOrder(BinTreeNode<T> *subTree,
			void (*visit)(BinTreeNode<T> *P)) {
	//递归函数,此算法按照后序遍历以subTree为根的二叉树
	if(subTree!=NULL) {		//递归结束条件
		PostOrder(subTree->leftChild,visit);	//后序遍历根的左子树
		PostOrder(subTree->rightChild,visit);	//后序遍历根的右子树
		visit(subTree);		//访问根节点
	}
};
除了文章中有特别说明,均为IT宅原创文章,转载请以链接形式注明出处。
本文链接:http://www.itzhai.com/preorder-binary-tree-traversal-inorder-traversal-and-postorder-traversal-of-algorithm-2.html
arthinking Java技术交流群:280755654,入门群:428693174 more
分享到:
 
如果您有更好的原创技术博文或者观点,欢迎投稿:admin@itzhai.com,或者关注订阅左侧浮动面板的微信号订阅IT宅itread)发送消息。
数据结构与算法推荐专题
文章评论
    一条评论
  1. 瞬间 2013年11月08日17:24:43  #-49楼 回复 回复

    中序遍历 c-d 应该加括号

给我留言

有人回复时邮件通知我
数据结构与算法的相关文章
随机文章 本月热门 热评
1 JavaScript设计模式笔记 – 适配器模式 装饰者模式 2012/11/19
2 Fedora与Redhat系统忘记密码的快速解决办法 2011/4/30
3 Javascript笔记 – Javascript中的闭包 2012/5/31
4 虚拟机装不了系统,镜像文件用不了?很可能是分区工具的问题 2011/5/2
5 Eclipse的Javascript校验卡住的问题 2014/7/15
6 Java对象内存计算的几种方法 2014/6/8
友情推荐 更多
破博客 文官洗碗安天下,武将打怪定乾坤。多么美好的年代,思之令人泪落。
Mr.5's Life 白天是一名程序员,晚上就是个有抱负的探索者
行知-追寻技术之美 关注大数据,分布式系统
我爱编程 编程成长轨迹
Cynthia's Blog 学习笔记 知识总结 思考感悟
 
欢迎关注我的公众号 IT宅
关于IT宅 文章归档

IT宅中的文章除了标题注明转载或有特别说明的文章,均为IT宅的技术知识总结,学习笔记或随笔。如果喜欢,请使用文章下面提供的分享组件。转载请注明出处并加入文章的原链接。 感谢大家的支持。

联系我们:admin@itzhai.com

Theme by arthinking. Copyright © 2011-2015 IT宅.com 保留所有权利.