- 浏览: 2962784 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (2529)
- finance (1459)
- technology (218)
- life (343)
- play (150)
- technology-component (0)
- idea (6)
- house (74)
- health (75)
- work (32)
- joke (23)
- blog (1)
- amazing (13)
- important (22)
- study (13)
- Alternative (0)
- funny (8)
- stock_technology (12)
- business (16)
- car (21)
- decorate (4)
- basketball (2)
- English (16)
- banker (1)
- TheBest (1)
- sample (2)
- love (13)
- management (4)
最新评论
-
zhongmin2012:
BSM确实需要实践,标准ITIL服务流程支持,要做好,需要花费 ...
BSM实施之前做什么 -
shw340518:
提示楼主,有时间逻辑bug:是你妈二十那年写的 那会儿连你爹都 ...
80后辣妈给未来儿子的信~我的儿,你也给我记住了~~~ -
guoapeng:
有相关的文档吗?
it项目管理表格(包含146个DOC文档模板) -
solomon:
看到的都是 这种 CTRL+C 和 CTRL+V 的文章, ...
Designing a website with InfoGlue components -
wendal:
恩, 不错. 有参考价值
Designing a website with InfoGlue components
后序遍历还没有明白,继续学习^_^,过几天写个huffman编码的例子来玩玩,不多说了,看代码吧,注意:程序申请的空间并没有释放^_^
/**//********************************************************************
created: 2005/12/30
created: 30:12:2005 10:39
filename: bintree.h
author: Liu Qi
purpose:
二叉树的3种遍历方式(包括非递归实现),前序,后序和中序,先访问根节点就是
前序(部分书籍称为先根遍历,个人觉得该说法更好^_^),类似的,最后访问根节点就是后序
*********************************************************************/
#ifndef TREE_H
#define TREE_H
#include <stdio.h>
#include <malloc.h>
#include
<stack>
#include <queue>
#include <assert.h>
using namespace std;
typedef int ElemType;
typedef struct treeT
{
ElemType key;
struct treeT*
left;
struct treeT* right;
}treeT, *pTreeT;
/**//*===========================================================================
*
Function name: visit
* Parameter: root:树根节点指针
*
Precondition:
* Description:
* Return value:
*
Author: Liu Qi,
//-
===========================================================================*/
static
void visit(pTreeT root)
{
if (NULL != root)
{
printf(" %d\n", root->key);
}
}
/**//*===========================================================================
*
Function name: BT_MakeNode
* Parameter: target:元素值
*
Precondition: None
* Postcondition: NULL != pTreeT
*
Description: 构造一个tree节点,置左右指针为空,并且返回指向新节点的指针
* Return value:
指向新节点的指针
* Author: Liu Qi,
[12/30/2005]
===========================================================================*/
static
pTreeT BT_MakeNode(ElemType target)
{
pTreeT pNode = (pTreeT)
malloc(sizeof(treeT));
assert( NULL != pNode );
pNode->key = target;
pNode->left = NULL;
pNode->right = NULL;
return pNode;
}
/**//*===========================================================================
*
Function name: BT_Insert
* Parameter: target:要插入的元素值,
pNode:指向某一个节点的指针
* Precondition: NULL != ppTree
*
Description: 插入target到pNode的后面
* Return value: 指向新节点的指针
*
Author: Liu Qi,
[12/29/2005]
===========================================================================*/
pTreeT
BT_Insert(ElemType target, pTreeT* ppTree)
{
pTreeT Node;
assert( NULL != ppTree );
Node = *ppTree;
if (NULL == Node)
{
return
*ppTree = BT_MakeNode(target);
}
if (Node->key == target) //不允许出现相同的元素
{
return
NULL;
}
else if (Node->key > target) //向左
{
return BT_Insert(target, &Node->left);
}
else
{
return BT_Insert(target, &Node->right);
}
}
/**//*===========================================================================
*
Function name: BT_PreOrder
* Parameter: root:树根节点指针
*
Precondition: None
* Description: 前序遍历
* Return
value: void
* Author: Liu Qi,
[12/29/2005]
===========================================================================*/
void
BT_PreOrder(pTreeT root)
{
if (NULL != root)
{
visit(root);
BT_PreOrder(root->left);
BT_PreOrder(root->right);
}
}
/**//*===========================================================================
*
Function name: BT_PreOrderNoRec
* Parameter: root:树根节点指针
*
Precondition: Node
* Description: 前序(先根)遍历非递归算法
* Return
value: void
* Author: Liu Qi,
[1/1/2006]
===========================================================================*/
void
BT_PreOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL !=
root)
{
visit(root);
s.push(root);
root = root->left;
}
else
{
root = s.top();
s.pop();
root = root->right;
}
}
}
void BT_PreOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root))
{
while (NULL !=
root)
{
visit(root);
s.push(root);
root = root->left;
}
while (NULL == root && !s.empty())
{
root = s.top();
s.pop();
root =
root->right;
}
}
}
/**//*===========================================================================
*
Function name: BT_InOrder
* Parameter: root:树根节点指针
*
Precondition: None
* Description: 中序遍历
* Return
value: void
* Author: Liu Qi,
[12/30/2005]
===========================================================================*/
void
BT_InOrder(pTreeT root)
{
if (NULL != root)
{
BT_InOrder(root->left);
visit(root);
BT_InOrder(root->right);
}
}
/**//*===========================================================================
*
Function name: BT_InOrderNoRec
* Parameter: root:树根节点指针
*
Precondition: None
* Description: 中序遍历,非递归算法
* Return
value: void
* Author: Liu Qi,
[1/1/2006]
===========================================================================*/
void
BT_InOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while
((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
visit(root);
s.pop();
root =
root->right;
}
}
}
/**//*===========================================================================
*
Function name: BT_PostOrder
* Parameter: root:树根节点指针
*
Precondition: None
* Description: 后序遍历
* Return
value: void
* Author: Liu Qi,
[12/30/2005]
===========================================================================*/
void
BT_PostOrder(pTreeT root)
{
if (NULL != root)
{
BT_PostOrder(root->left);
BT_PostOrder(root->right);
visit(root);
}
}
/**//*===========================================================================
*
Function name: BT_PostOrderNoRec
* Parameter: root:树根节点指针
*
Precondition: None
* Description: 后序遍历,非递归算法
* Return
value: void
* Author: Liu Qi, //
[1/1/2006]
===========================================================================*/
void
BT_PostOrderNoRec(pTreeT root)
{
//学习中,尚未明白
}
/**//*===========================================================================
*
Function name: BT_LevelOrder
* Parameter: root:树根节点指针
*
Precondition: NULL != root
* Description: 层序遍历
* Return
value: void
* Author: Liu Qi,
[1/1/2006]
===========================================================================*/
void
BT_LevelOrder(pTreeT root)
{
queue<treeT *> q;
treeT
*treePtr;
assert( NULL != root );
q.push(root);
while (!q.empty())
{
treePtr = q.front();
q.pop();
visit(treePtr);
if (NULL != treePtr->left)
{
q.push(treePtr->left);
}
if (NULL !=
treePtr->right)
{
q.push(treePtr->right);
}
}
}
#endif
测试代码
#include <stdio.h>
#include <stdlib.h>
#include
<time.h>
#include "tree.h"
#define MAX_CNT 5
#define BASE 100
int main(int argc, char *argv[])
{
int i;
pTreeT root =
NULL;
srand( (unsigned)time( NULL ) );
for (i=0;
i<MAX_CNT; i++)
{
BT_Insert(rand() % BASE,
&root);
}
//前序
printf("PreOrder:\n");
BT_PreOrder(root);
printf("\n");
printf("PreOrder no recursion:\n");
BT_PreOrderNoRec(root);
printf("\n");
//中序
printf("InOrder:\n");
BT_InOrder(root);
printf("\n");
printf("InOrder no recursion:\n");
BT_InOrderNoRec(root);
printf("\n");
//后序
printf("PostOrder:\n");
BT_PostOrder(root);
printf("\n");
//层序
printf("LevelOrder:\n");
BT_LevelOrder(root);
printf("\n");
return
0;
}如果有兴趣不妨运行一下,看看效果^_^
另外请教怎样让二叉树漂亮的输出,即按照树的形状输出
posted on 2006-01-01
20:20 ngaut 阅读(17249) 评论(8) 编辑 收藏 引用 所属分类: c/c++/ds
评论
# re: 二叉树的遍历:前序,中序,后序,层序--包括递归和非递归实现 2006-01-03 23:09 PIGWORLD
给你写了个后序遍历的非递归实现,直接写的,没有验证过,估计没有什么大的问题,看看吧
思想是:
先找到最左边的叶子并把路上遇到的节点依次压栈,然后弹出栈顶的元素(该元素为最左边的叶子),并判断(1)它有没有右节点;(2)右节点是否被访问过。如果(1)为有右节点同时(2)为没有访问过,则先压入刚才弹出的元素,然后再压入它的右子树。否则,就访问该节点,并设置pre为改节点。
void BT_PostOrderNoRec(pTreeT root)
{
stack<pTreeT> s;
s.push(root);
while(root != 0 || !s.isEmpty()) {
//找到最左边的叶子
while((root =
root->left) != 0) {
s.push(root);
}
pTree pre; //记录前一个访问的节点
root = s.pop(); //弹出栈顶元素
//如果右子树非空,并且右子树未访问过,
//则(在内层while循环中)把右子树压栈
if(root->right != 0
&& pre != root->right) {
//要把上一句中弹出的元素重新压栈
s.push(root);
root = root->right;
s.push(root);
}
//否则
else {
弹出栈顶节点,访问它并设置pre为该节点
root = pre = s.pop();
visit(root);
//使root为0以免进入内层循环
root = 0;
}
} 回复 更多评论
# re: 二叉树的遍历:前序,中序,后序,层序--包括递归和非递归实现 2006-09-08 17:22 247
*
* *
*
#
# # 回复 更多评论
# re: 二叉树的遍历:前序,中序,后序,层序--包括递归和非递归实现 2006-09-12 14:54 路人甲
void
BT_PostOrderNoRec(pTreeT root)
{
stack<treeT *> s;
pTreeT
pre=NULL;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root =
s.top();
if (root->right!=NULL && pre!=root->right){
root=root->right;
}
else{
root=pre=s.top();
visit(root);
s.pop();
root=NULL;
}
}
}
} 回复 更多评论
# re: 二叉树的遍历:前序,中序,后序,层序--包括递归和非递归实现 2006-09-12 14:57 路人甲
根据lz和前面那个人的代码,经过调试成功,
现如下:
void BT_PostOrderNoRec(pTreeT root)
{
stack<treeT *> s;
pTreeT pre=NULL;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root =
s.top();
if (root->right!=NULL && pre!=root->right){
root=root->right;
}
else{
root=pre=s.top();
visit(root);
s.pop();
root=NULL;
}
}
}
}
发表评论
-
GTD
2010-10-29 09:14 1300GTD流程图 Getting Things Done的缩写。来 ... -
面试题收集
2010-06-09 11:28 0说在前面: 1、以下题目,除了编程任务外其他都需要写在给 ... -
美国参数技术公司PTC
2010-04-13 16:43 12614 美国参数技术公司 PTC公司 美国参数技术 ... -
China Offer Letter From HP
2010-04-12 08:58 0Hi, huangzhen, ... -
埃森哲咨询公司
2010-03-19 18:47 1556埃森哲咨询公司 出自 MBA智库百科(http://wiki ... -
2010 工作学习 plan 及 target
2010-03-12 15:15 0Hi HuangZhen , 我公司地址 ... -
算法基础
2010-01-04 08:47 0第一章 基础知识C++程序设计 (4课时)★ 参数类 ... -
集合与图论模拟考卷及解答
2010-01-04 08:44 0第一章 集合的基本概念 ★★★★★ (4学时) 掌握: ... -
Career Compass: Define Your Own Growth Map
2009-01-08 11:09 2130This article give us a tools to ... -
Best Careers 2009: Computer Systems Analyst/Archit
2009-01-05 14:56 1011By Marty Nemko Posted Decemb ... -
The 30 Best Careers for 2009
2009-01-05 14:51 902U.S. News 's annual list of 30 ... -
我司招募 有意向简历发我邮箱 合适 我给你推荐4
2008-12-04 07:35 276人力资源部 HR Supervisor 电子邮箱: ... -
我司招募 有意向简历发我邮箱 合适 我给你推荐3
2008-12-04 07:32 398Cognos Administrator 电子邮箱: fam ... -
work recommendation sample for your reference
2008-12-02 13:16 1624November 10, 1999 To Whom It M ... -
华东理工大学网络学院(高通过率)
2008-11-11 17:19 0东理工大学网络教育2008年秋季招生简章华东理工大学是全国重点 ... -
Siebel
2008-11-07 17:28 1471目录 简介 历史 收购 Ora ... -
Cognizant Q3 Tops Ests; Maintains Full Year Guidan
2008-11-06 15:32 948Congizant (CTSH) this morning p ... -
my first blog on Cognization internal blog system
2008-11-03 10:40 1333I write my first blog on Cogniz ... -
my cognizant contact information
2008-10-31 10:53 0Here is my mailbox in Cognizati ... -
我司招募 有意向简历发我邮箱 合适 我给你推荐2
2008-10-31 07:36 241I forgot to mention salary ,sor ...
相关推荐
本文将深入探讨四种常见的二叉树遍历方法:前序遍历、中序遍历、后序遍历以及层次遍历,并以C++编程语言为例,阐述如何实现这些遍历算法。 1. **前序遍历**(Preorder Traversal) 前序遍历的顺序是根节点 -> 左...
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
二叉树三种遍历非递归算法 二叉树是一种常用的数据结构,它广泛应用于计算机科学和软件工程中。二叉树的遍历是指对二叉树中的每个结点进行访问的过程。常见的二叉树遍历方法有三种:先序遍历、中序遍历和后序遍历。...
常见的遍历方法包括:前序遍历、中序遍历和后序遍历。 #### 4.1 前序遍历 前序遍历的顺序是先访问根节点,然后递归地进行左子树的前序遍历,最后递归地进行右子树的前序遍历。实现代码如下: ```c void Preoder...
本主题主要探讨的是在MFC(Microsoft Foundation Classes)环境中如何实现二叉树的前序、中序和后序遍历。 首先,让我们了解一下二叉树的三种遍历方法: 1. 前序遍历:前序遍历的顺序是“根-左-右”。即首先访问根...
本节将详细介绍二叉树的前序、中序和后序遍历,以及如何求解二叉树的深度和叶节点数量。 **前序遍历(Preorder Traversal)** 前序遍历的顺序是:根节点 -> 左子树 -> 右子树。在代码实现中,通常采用递归的方式...
类似地,如果给定后序和中序遍历的结果,也可以重构二叉树。在后序遍历中,最后一个元素是根节点,因为它是所有子节点之后访问的。中序遍历仍然可以帮助我们区分左右子树,但是这次我们需要找到根节点右侧的子序列来...
### 二叉树先序、中序、后序遍历非递归算法 #### 前言 在计算机科学中,二叉树是一种常见的数据结构,它被广泛应用于各种算法和程序设计中。二叉树的遍历是理解并操作二叉树的基础,通常有三种主要的遍历方式:...
标题"关于二叉树前序和后序的非递归遍历算法"指的是不使用递归函数来实现二叉树的前序和后序遍历。递归方法虽然直观,但在处理大型二叉树时可能会导致栈溢出,因此非递归方法是一个更优的选择。 **前序遍历**是...
非递归中序遍历二叉树: 非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度: 交换二叉树的左右子树:...
本项目聚焦于使用C++语言实现二叉树的各种操作,包括构建、前序遍历、中序遍历、后序遍历以及层序遍历。下面将详细解释这些概念及其C++实现的关键点。 首先,二叉树是由节点构成的数据结构,每个节点最多有两个子...
二叉树的遍历主要有三种方式:前序遍历、中序遍历和后序遍历。 1. **前序遍历**: - 访问根节点; - 遍历左子树; - 遍历右子树。 这种遍历方式通常用于复制二叉树或构建一个新的与原二叉树结构相同的二叉树...
本程序实现了三种主要的二叉树遍历方法:先序遍历、中序遍历和后序遍历。以下是关于这些遍历方法的详细解释: 1. 先序遍历(Preorder Traversal): - 访问根节点。 - 对左子树进行先序遍历。 - 对右子树进行...
本节将详细介绍如何使用C语言实现一个简单的二叉树,包括节点的创建与销毁、以及三种遍历方式:前序遍历、中序遍历和后序遍历。 ##### 1. 定义二叉树节点 首先定义一个结构体 `TreeNode`,用于表示二叉树中的每个...
二叉树前序,中序,后序,求深度的递归和非递归方法
在处理二叉树时,有三种经典的遍历方法:前序遍历、中序遍历和后序遍历。 1. **前序遍历**:前序遍历的顺序是“根-左-右”。在给定的代码中,`PreOrder`函数实现了这个过程。首先访问根节点,然后递归地对左子树...
二叉树的遍历方法主要包括三种:前序遍历、中序遍历以及后序遍历。每种遍历方式都有其独特的应用场景,而在实际编程中,有时候我们需要通过已知的两种遍历来构建或恢复二叉树,并得到第三种遍历顺序。本文将详细介绍...
本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**: - **递归算法**:首先访问根节点,然后递归地对左子树进行前序遍历,最后对右子树进行前序遍历。伪代码如下: ``` function...
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。