#include<iostream>
using namespace std;
/**
二叉树的遍历:前序,后序,中序
二叉树的非递归遍历:前序,后序,中序
参考文献:http://topic.csdn.net/t/20060802/17/4922659.html
***/
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &T)
{
char ch;
cin.get(ch);
if(ch == ' ')
T = NULL;
else
{
if(!(T = (BiTNode*)malloc(sizeof(BiTNode))))
exit(0);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return 1;
}
int PreOrderVisit(BiTree &T)
{
if(T)
{
cout<<T->data<<endl;
PreOrderVisit(T->lchild);
PreOrderVisit(T->rchild);
return 1;
}else
return 1;
}
int MidOrderVisit(BiTree &T)
{
if(T)
{
MidOrderVisit(T->lchild);
cout<<T->data;
MidOrderVisit(T->rchild);
return 1;
}
else
return 1;
}
int LastOrderVisit(BiTree &T)
{
if(T)
{
LastOrderVisit(T->lchild);
LastOrderVisit(T->rchild);
cout<<T->data;
}
else
return 1;
}
//先序遍历二叉树:非递归
int PreOrderVisit2(BiTree &T)
{
BiTree temp = T;
cout<<"非递归前序遍历树:"<<endl;
BiTree stack[100] ;
int top = -1;
while(T||top>-1)
{
while(T)
{
cout<<T->data<<" ";
stack[++top] = T;
T = T->lchild;
}
if(top>-1)
{
T = stack[top--];
T = T->rchild;
}
}
T = temp;
cout<<endl;
return 1;
}
//中序遍历二叉树:非递归
int MidOrderVisit2(BiTree &T)
{
BiTree temp = T;
cout<<"非递归中序遍历树:"<<endl;
BiTree stack[100] ;
int top = -1;
while(T||top>-1)
{
while(T)
{
stack[++top] = T;
T = T->lchild;
}
if(top>-1)
{
T = stack[top--];
cout<<T->data<<" ";
T = T->rchild;
}
}
cout<<endl;
T = temp;
return 1;
}
//后序遍历二叉树:非递归
int LastOrderVisit2(BiTree &T)
{
BiTree temp = T;
cout<<"非递归后序遍历树:"<<endl;
BiTree stack[100] ;
int tag[100];
int top = -1;
while(T||top>-1)
{
while(T)
{
int pointer = ++top;
stack[pointer] = T;
tag[pointer] = 0;
T = T->lchild;
}
while(top>-1&&tag[top]==1)
{
T = stack[top--];
cout<<T->data<<" ";
}
if(top>-1)
{
tag[top] = 1;
T = stack[top];
T = T->rchild;
}else
break;
}
cout<<endl;
T = temp;
return 1;
}
int main()
{
BiTree T;
//例如:
// abc空格空格de空格g空格空格f空格空格空格
cout<<"创建树:输入数据,Enter键结束:"<<endl;
CreateBiTree(T);
/* cout<<"前序遍历树:"<<endl;
PreOrderVisit(T);
cout<<"中序遍历树:"<<endl;
MidOrderVisit(T);
cout<<"后序遍历树:"<<endl;
LastOrderVisit(T);*/
PreOrderVisit2(T);
MidOrderVisit2(T);
LastOrderVisit2(T);
}
分享到:
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
二叉树的遍历有多种方式,本文将介绍二叉树的递归遍历,中序遍历,先序遍历和后序遍历。 递归遍历是指使用递归函数来遍历二叉树的每个结点。递归遍历的优点是代码简洁易懂,但缺点是可能会导致堆栈溢出。在本文的...
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
**前序遍历**是二叉树遍历的一种,其顺序为:根节点 -> 左子树 -> 右子树。在非递归实现中,我们可以使用栈来辅助完成。首先将根节点压入栈中,然后进入一个循环。在循环中,如果栈不为空,就弹出栈顶元素并访问,...
二叉树的遍历,全部用递归实现,很有规律! 二叉树的遍历,全部用递归实现,很有规律
C语言二叉树遍历前序非递归算法,简单易懂,正确无误
java实现 二叉树的遍历 前序遍历用到递归, 中序和后序遍历用到栈, 其实还是有一定难度的
以上就是使用C语言进行二叉树遍历的基本方法,无论是前序、中序还是后序,核心都是递归的思想或者借助栈来模拟递归。掌握这三种遍历方式对于理解二叉树的性质和操作至关重要,它们在数据结构和算法的许多实际应用...
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
本文将深入探讨四种常见的二叉树遍历方法:前序遍历、中序遍历、后序遍历以及层次遍历,并以C++编程语言为例,阐述如何实现这些遍历算法。 1. **前序遍历**(Preorder Traversal) 前序遍历的顺序是根节点 -> 左...
以上算法展示了如何利用栈进行二叉树的前序、中序和后序非递归遍历。这些非递归方法不仅避免了递归可能带来的栈溢出问题,而且在处理大规模数据时更有效率。理解并掌握这些算法,对于深入学习数据结构和算法优化具有...
二叉树遍历是计算机科学中一种重要的数据结构操作,主要应用于树形数据结构的处理。在软考中,理解并能熟练应用二叉树的遍历方法是必不可少的技能。这里我们详细讨论前序遍历、中序遍历、后序遍历以及层次遍历这四种...
### 二叉树先序、中序、后序遍历非递归算法 #### 前言 在计算机科学中,二叉树是一种常见的数据结构,它被广泛应用于各种算法和程序设计中。二叉树的遍历是理解并操作二叉树的基础,通常有三种主要的遍历方式:...
在二叉树中,遍历是访问每个节点的过程,有三种主要的遍历方式:前序遍历、中序遍历和后序遍历。本主题聚焦于后序遍历,它对于理解和操作二叉树至关重要。 后序遍历(Postorder Traversal)的顺序是:先访问左子树...
本程序实现了三种主要的二叉树遍历方法:先序遍历、中序遍历和后序遍历。以下是关于这些遍历方法的详细解释: 1. 先序遍历(Preorder Traversal): - 访问根节点。 - 对左子树进行先序遍历。 - 对右子树进行...
本文将深入探讨二叉树的三种主要遍历方法:前序遍历、中序遍历和后序遍历。 **前序遍历(Preorder Traversal)** 前序遍历的顺序是:根节点 -> 左子树 -> 右子树。这意味着我们首先访问根节点,然后递归地遍历左...
二叉树的遍历通常分为三种:前序遍历(根左右)、中序遍历(左根右)和后序遍历(左右根)。通常情况下,我们都是通过递归的方式来实现这些遍历方法,但是递归方式可能会导致大量的函数调用开销,甚至可能导致栈溢出...
本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**: - **递归算法**:首先访问根节点,然后递归地对左子树进行前序遍历,最后对右子树进行前序遍历。伪代码如下: ``` function...
二叉树遍历是计算机科学中处理二叉树数据结构的一种基本操作,它涉及到三种主要的遍历方式:前序遍历、中序遍历和后序遍历。这些遍历方法在理解和操作二叉树时起着至关重要的作用。 **前序遍历**(Preorder ...
本主题将详细介绍如何非递归地进行二叉树的前序、中序和后序遍历,以及如何使用C语言实现通用栈结构来辅助遍历。 首先,我们来看递归遍历的方法。递归遍历是基于函数调用自身来完成的,对于二叉树,有以下三种遍历...