算法2(递归和非递归俩种方法实现二叉树的前序遍历)

http://blog.csdn.net/yuucyf/article/details/6752480

题目：

递归和非递归俩种方法实现二叉树的前序遍历。

思路一：

对二叉树的递归遍历我相信大家只要学了数据结构后应当都很容易就能写出，这里主要是讨论二叉树的非递归写法。按照二叉树前序遍历的定义，无论是访问整棵树还是其子树，均应该遵循先访问根结点，然后访问根结点的左子树，最后访问根结点的右子树的。在整个二叉树前序遍历的过程中，程序始终要做的工作分成俩个部分：（借用辅助栈来实现）

1. 当前正在处理的树（子树）

2. 保存在栈中等待处理的部分。

当栈中元素位于栈顶即将出栈时，意味着其根结点和左子树已访问完成，出栈后，进入其右子树进行访问。

代码如下：

[cpp] view plaincopyprint?

/*-------------------------------

Copyright by yuucyf. 2011.09.06

--------------------------------*/

#include "stdafx.h"

#include

#include

#include

using namespace std;

typedef struct tagBSTreeNode

{

int nValue;

tagBSTreeNode *psLeft;

tagBSTreeNode *psRight;

tagBSTreeNode()

{

psLeft = psRight = 0;

nValue = 0;

}

}S_BSTreeNode;

void AddBSTreeNode(S_BSTreeNode *&psRoot, int nValue)

{

if (NULL == psRoot)

{

psRoot = new S_BSTreeNode;

assert(psRoot);

psRoot->nValue = nValue;

return;

}

if (psRoot->nValue

AddBSTreeNode(psRoot->psRight, nValue);

else

AddBSTreeNode(psRoot->psLeft, nValue);

}

void PreOrder_Recursion(const S_BSTreeNode *psRoot)

{

if (NULL == psRoot)

return;

cout nValue

PreOrder_Recursion(psRoot->psLeft);

PreOrder_Recursion(psRoot->psRight);

}

void PreOrder_Not_Recursion(S_BSTreeNode *psRoot)

{

stack stackNode;

S_BSTreeNode *psCurNode = psRoot;

while ((!stackNode.empty()) || (psCurNode != NULL))

{

if (psCurNode != NULL)

{

while (psCurNode)

{

cout nValue

stackNode.push(psCurNode);

psCurNode = psCurNode->psLeft;

}

}

else

{

psCurNode = stackNode.top();

stackNode.pop();

psCurNode = psCurNode->psRight;

}

}

}

int _tmain(int argc, _TCHAR* argv[])

{

S_BSTreeNode *psRoot = NULL;

AddBSTreeNode(psRoot, 8);

AddBSTreeNode(psRoot, 6);

AddBSTreeNode(psRoot, 4);

AddBSTreeNode(psRoot, 5);

AddBSTreeNode(psRoot, 12);

AddBSTreeNode(psRoot, 10);

AddBSTreeNode(psRoot, 15);

AddBSTreeNode(psRoot, 13);

AddBSTreeNode(psRoot, 14);

cout

PreOrder_Recursion(psRoot);

cout

cout

PreOrder_Not_Recursion(psRoot);

cout

//Don't forget to free memory.

return 0;

}

扩展：

如果要求是非递归后序遍历呢？非递归后序稍微有点复杂。按照二叉树后序遍历的定义，无论是访问整棵树还是起子树，均应该遵循先访问根结点左子树，然后访问根结点的右子树，最后访问根结点。值得注意的是，当一个元素位于栈顶即将处理的是，其左子树的访问一定完成，如果其右子树不为空，接下来应该进入其右子树访问，但此时该栈顶元素时不能出栈的，因为它作为根结点，其本身的值还未被访问。只有等到其右子树也访问完成后，该栈顶元素才能出栈，并输出它的值。 因此，在二叉树后序遍历的算法中，必须每个节点维护一个类型为int的整数nTag，

其每个元素(节点)的nTag取值为0 或1，用于标识栈中每个元素的状态。

1. 当一个元素刚进栈时，其对应的nTag 值置为0；

2. 当它位于栈顶即将被处理时，其nTag 值为0.意味着应该访问其右子树，于是将右子树作为当前处理的对象，此时该栈顶元素仍应该保留在栈中，并将其对应的nTag 值改为1.

3. 当其右子树访问完成后，该元素又一次位于栈顶，而此时其nTag 值为1，意味着其右子树已访问完成，接下来，应该直接访问的就是它，将其出栈。

代码如下：

[cpp] view plaincopyprint?

void PostOrder_Not_Recursion(S_BSTreeNode *psRoot)

{

stack stackNode;

S_BSTreeNode *psCurNode = psRoot;

while ((!stackNode.empty()) || (psCurNode != NULL))

{

if (psCurNode != NULL)

{

while (psCurNode /*&& psCurNode->nTag != 1*/)

{

stackNode.push(psCurNode);

psCurNode = psCurNode->psLeft;

}

}

psCurNode = stackNode.top();

while ((!stackNode.empty()) && (psCurNode->nTag == 1))

{

cout nValue

stackNode.pop();

if (stackNode.empty())

psCurNode = NULL;

else

psCurNode = stackNode.top();

}

if (!stackNode.empty())

{

psCurNode->nTag = 1;

psCurNode = psCurNode->psRight;

}

else

psCurNode = NULL;

}

}

http://blog.csdn.net/yuucyf/article/details/6752480

题目：

递归和非递归俩种方法实现二叉树的前序遍历。

思路一：

对二叉树的递归遍历我相信大家只要学了数据结构后应当都很容易就能写出，这里主要是讨论二叉树的非递归写法。按照二叉树前序遍历的定义，无论是访问整棵树还是其子树，均应该遵循先访问根结点，然后访问根结点的左子树，最后访问根结点的右子树的。在整个二叉树前序遍历的过程中，程序始终要做的工作分成俩个部分：（借用辅助栈来实现）

1. 当前正在处理的树（子树）

2. 保存在栈中等待处理的部分。

当栈中元素位于栈顶即将出栈时，意味着其根结点和左子树已访问完成，出栈后，进入其右子树进行访问。

代码如下：

[cpp] view plaincopyprint?

/*-------------------------------

Copyright by yuucyf. 2011.09.06

--------------------------------*/

#include "stdafx.h"

#include

#include

#include

using namespace std;

typedef struct tagBSTreeNode

{

int nValue;

tagBSTreeNode *psLeft;

tagBSTreeNode *psRight;

tagBSTreeNode()

{

psLeft = psRight = 0;

nValue = 0;

}

}S_BSTreeNode;

void AddBSTreeNode(S_BSTreeNode *&psRoot, int nValue)

{

if (NULL == psRoot)

{

psRoot = new S_BSTreeNode;

assert(psRoot);

psRoot->nValue = nValue;

return;

}

if (psRoot->nValue

AddBSTreeNode(psRoot->psRight, nValue);

else

AddBSTreeNode(psRoot->psLeft, nValue);

}

void PreOrder_Recursion(const S_BSTreeNode *psRoot)

{

if (NULL == psRoot)

return;

cout nValue

PreOrder_Recursion(psRoot->psLeft);

PreOrder_Recursion(psRoot->psRight);

}

void PreOrder_Not_Recursion(S_BSTreeNode *psRoot)

{

stack stackNode;

S_BSTreeNode *psCurNode = psRoot;

while ((!stackNode.empty()) || (psCurNode != NULL))

{

if (psCurNode != NULL)

{

while (psCurNode)

{

cout nValue

stackNode.push(psCurNode);

psCurNode = psCurNode->psLeft;

}

}

else

{

psCurNode = stackNode.top();

stackNode.pop();

psCurNode = psCurNode->psRight;

}

}

}

int _tmain(int argc, _TCHAR* argv[])

{

S_BSTreeNode *psRoot = NULL;

AddBSTreeNode(psRoot, 8);

AddBSTreeNode(psRoot, 6);

AddBSTreeNode(psRoot, 4);

AddBSTreeNode(psRoot, 5);

AddBSTreeNode(psRoot, 12);

AddBSTreeNode(psRoot, 10);

AddBSTreeNode(psRoot, 15);

AddBSTreeNode(psRoot, 13);

AddBSTreeNode(psRoot, 14);

cout

PreOrder_Recursion(psRoot);

cout

cout

PreOrder_Not_Recursion(psRoot);

cout

//Don't forget to free memory.

return 0;

}

扩展：

如果要求是非递归后序遍历呢？非递归后序稍微有点复杂。按照二叉树后序遍历的定义，无论是访问整棵树还是起子树，均应该遵循先访问根结点左子树，然后访问根结点的右子树，最后访问根结点。值得注意的是，当一个元素位于栈顶即将处理的是，其左子树的访问一定完成，如果其右子树不为空，接下来应该进入其右子树访问，但此时该栈顶元素时不能出栈的，因为它作为根结点，其本身的值还未被访问。只有等到其右子树也访问完成后，该栈顶元素才能出栈，并输出它的值。 因此，在二叉树后序遍历的算法中，必须每个节点维护一个类型为int的整数nTag，

其每个元素(节点)的nTag取值为0 或1，用于标识栈中每个元素的状态。

1. 当一个元素刚进栈时，其对应的nTag 值置为0；

2. 当它位于栈顶即将被处理时，其nTag 值为0.意味着应该访问其右子树，于是将右子树作为当前处理的对象，此时该栈顶元素仍应该保留在栈中，并将其对应的nTag 值改为1.

3. 当其右子树访问完成后，该元素又一次位于栈顶，而此时其nTag 值为1，意味着其右子树已访问完成，接下来，应该直接访问的就是它，将其出栈。

代码如下：

[cpp] view plaincopyprint?

void PostOrder_Not_Recursion(S_BSTreeNode *psRoot)

{

stack stackNode;

S_BSTreeNode *psCurNode = psRoot;

while ((!stackNode.empty()) || (psCurNode != NULL))

{

if (psCurNode != NULL)

{

while (psCurNode /*&& psCurNode->nTag != 1*/)

{

stackNode.push(psCurNode);

psCurNode = psCurNode->psLeft;

}

}

psCurNode = stackNode.top();

while ((!stackNode.empty()) && (psCurNode->nTag == 1))

{

cout nValue

stackNode.pop();

if (stackNode.empty())

psCurNode = NULL;

else

psCurNode = stackNode.top();

}

if (!stackNode.empty())

{

psCurNode->nTag = 1;

psCurNode = psCurNode->psRight;

}

else

psCurNode = NULL;

}

}


相关文章

  • 二叉树的遍历算法

    • 二叉树的前序.后序的递归.非递归遍历算法 摘 要 本课程设计主要解决树的前序.后序的递归.非递归遍历算法,层次序的非递归遍历算法的实现.在课程设计中,系统开发平台为Windows 2000,程序设计设计语言采用Visual C++,程序运行 ...查看


  • 哈工大数据结构与算法2树型结构的建立与遍历

    • 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称:数据结构与算法 科学与技术四班 1110310422 课程类型:必修 实验项目名称:树型结构的建立与遍历 实验题目: 二叉树的运用 班级:计算机 学号: 姓名:胡明 一.实验目的 (1 ...查看


  • 二叉树的遍历

    • 目 录 一.设计思想---------------------.01 二.算法流程图--------------------.01 三.源代码----------------------.04 四.运行结果----------------- ...查看


  • 二叉树深度优先遍历.广度优先遍历

    • 1. 简述树的深度优先遍历和广度优先遍历及其非递归实现的特点. 2011-09-19 10:49:34| 分类: | 标签: |字号大中小 订阅 二叉树的深度优先遍历.广度优先遍历和非递归遍历 二叉树的遍历: D:访问根结点,L:遍历根结点 ...查看


  • 二叉树的遍历 1

    • 课 程 设 计 课程设计名称: 数据结构课程设计 专 业 班 级 : 学 生 姓 名 : 学 号 : 指 导 教 师 : 课程设计时间: 2015.6.29-2015.7.10 1.需求分析 题目:二叉树的前序.中序.后序的递归非递归的遍历 ...查看


  • 二叉树的中序的递归.非递归遍历算法

    • 信息工程学院<数据结构> 课程设计报告 设计题目 二叉树的中序的递归.非递归遍历算法 专 业 班 级 小 组 成 员 一． 题目:二叉树的中序的递归.非递归遍历算法 二． 小组任务分工 马凯:编写二叉树中序递归遍历.非递归遍历 ...查看


  • 二叉树的遍历(先序.中序.后序)

    • 实践三:树的应用 1.实验目的要求 通过本实验使学生深刻理解二叉树的性质和存储结构,熟练掌握二叉树的遍历算法.认识哈夫曼树.哈夫曼编码的作用和意义. 实验要求:建一个二叉树并按照前序.中序.后序三种方法遍历此二叉树, 正确调试本程序. 能够 ...查看


  • 二叉树实验报告

    • <数据结构> 课程设计报告 专 业 计算机科学与技术 班 级 3班 姓 名 学 号 指导教师 起止时间 2012.12~2013.1 课程设计:二叉树 一.任务描述 二叉树的中序.前序.后序的递归.非递归遍历算法,应包含建树的实 ...查看


  • 树和二叉树实验

    • 树和二叉树实验 实验题目:二叉树的实现 一. 实验目的 (1)掌握二叉树的逻辑结构: (2)掌握二叉树的二叉链表存储结构: (3)验证二叉树的二叉链表存储及遍历操作 二. 实验内容: (1)建立一颗含有 n 个节点的二叉树,采用二叉链表存储 ...查看


热门内容