Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4795900
  • 博文数量: 890
  • 博客积分: 17977
  • 博客等级: 上将
  • 技术积分: 8621
  • 用 户 组: 普通用户
  • 注册时间: 2005-08-26 09:59
个人简介

一个好老好老的老程序员了。

文章分类

全部博文(890)

文章存档

2020年(7)

2019年(40)

2018年(88)

2017年(130)

2015年(5)

2014年(12)

2013年(41)

2012年(36)

2011年(272)

2010年(1)

2009年(53)

2008年(65)

2007年(47)

2006年(81)

2005年(12)

分类: IT职场

2012-09-01 23:12:49

今天去面试,遇到二叉树给定前序和中序,求后续。算法都还给大学老师了,也不会啊。晚上回来补习一下。
二叉树的前序遍历、中序遍历和后序遍历及其算法 本文由 arthinking 发表于472 天前 ⁄ 数据结构与算法暂无评论 ⁄ 被围观 2,136 views+

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

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

二叉树的前序遍历

前序遍历:- + a * b – c d / e f
中序遍历:a + b * c – d – e / f
后序遍历:a b c d – * + e f / -
前序遍历算法:
template void BinaryTree::PreOrder(BinTreeNode *subTree, void (*visit)(BinTreeNode *P)) { //递归函数:此算法按照前序遍历以subTree为根的二叉树。 if(subTree!=NULL){ //递归结束条件 visit(subTree); //访问根节点 PreOrder(subTree->leftChild,visit); //前序遍历根的左子树 PreOrder(subTree->rightChild,visit); //前序遍历根的右子树 } };
中序遍历算法:
template void BinaryTree::InOrder(BinTreeNode *subTree, void(*visit)(BinTreeNode *p)){ //递归函数:此算法按照中序次序遍历以subTree为根的子数 if(subTree!=NULL) { //如果subTree为NULL,则结束递归 InOrder(subTree->leftChild,visit); //中序遍历根的左子树 visit(subTree); //访问根节点 InOrder(subTree->rightChild,visit); //中序遍历根的右子数 } };
后序遍历算法:
template void BinaryTree::PostOrder(BinTreeNode *subTree, void (*visit)(BinTreeNode *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

阅读(2262) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~