二叉树的遍历算法(详细示例分析)
时间:2022-08-04 02:38:35
#include<iostream>
#include<assert.h>
#include<stack>
#include<queue>
using namespace std;
struct Node
{
int v;
Node *leftChild,*rightChild;
Node():leftChild(NULL),rightChild(NULL){}
Node(int vv):leftChild(NULL),rightChild(NULL)
{
v=vv;
}
};
void print(int v)
{
cout<<v<<" ";
}
void PreOrderTraverse(Node *n, void (* visit)(int))
{
assert(n!=NULL&&visit!=NULL);
(*visit)(n->v);
if(n->leftChild!=NULL) PreOrderTraverse(n->leftChild,visit);
if(n->rightChild!=NULL) PreOrderTraverse(n->rightChild,visit);
}
void InOrderTraverse(Node *n, void (* visit)(int))
{
assert(n!=NULL&&visit!=NULL);
if(n->leftChild!=NULL) InOrderTraverse(n->leftChild,visit);
(*visit)(n->v);
if(n->rightChild!=NULL) InOrderTraverse(n->rightChild,visit);
}
void PostOrderTraverse(Node *n, void (* visit)(int))
{
assert(n!=NULL&&visit!=NULL);
if(n->leftChild!=NULL) PostOrderTraverse(n->leftChild,visit);
if(n->rightChild!=NULL) PostOrderTraverse(n->rightChild,visit);
(*visit)(n->v);
}
//非递归版本,将递归改成非递归一般都要利用一个栈
//每次访问一个结点后,在向左子树遍历下去之前,利用这个栈记录该结点的右子女(如果有的话)结点的地址,
//以便在左子树退回时可以直接从栈顶取得右子树的根结点,继续右子树的遍历
void PreOrder(Node *n, void (* visit)(int))
{
stack<Node*> sta;
sta.push(n);
while(!sta.empty())
{
Node * t=sta.top();
sta.pop();
assert(t!=NULL);
(*visit)(t->v);
if(t->rightChild!=NULL) sta.push(t->rightChild);
if(t->leftChild!=NULL) sta.push(t->leftChild);
}
}
//非递归中序遍历
void InOrder(Node * n , void (* visit) (int))
{
stack<Node *> sta;
sta.push(n);
Node * p= n;
while(!sta.empty()&&p!=NULL)
{
p=sta.top();
while(p!=NULL&&!sta.empty())
{
sta.push(p->leftChild);
p=p->leftChild;
}
sta.pop();//弹出空指针
if(!sta.empty())
{
p=sta.top();
sta.pop();
(*visit)(p->v);
sta.push(p->rightChild);
}
}
}
//非递归后续遍历
struct StkNode
{
Node * ptr;
bool tag;//false=left and true=right
StkNode():ptr(NULL),tag(false)
{}
};
void PostOrder(Node * n ,void (*visit) (int))
{
stack<StkNode> sta;
StkNode w;
Node * p = n;
do {
while(p!=NULL)
{
w.ptr=p;
w.tag=false;
sta.push(w);
p=p->leftChild;
}
bool flag=true;
while(flag&&!sta.empty())
{
w=sta.top();
sta.pop();
p=w.ptr;
if(!w.tag)//left,如果从左子树返回,则开始遍历右子树
{
w.tag=true;//标记右子树
sta.push(w);
flag=false;
p=p->rightChild;
}
else
{
(*visit)(p->v);
}
}
} while(!sta.empty());
}
//层序遍历,利用队列
void LevelOrderTraverse(Node * n , void (* visit )(int))
{
assert(n!=NULL&&visit!=NULL);
queue<Node * > que;
que.push(n);
while(!que.empty())
{
Node * t=que.front();
(*visit)(t->v);
que.pop();
if(t->leftChild!=NULL) que.push(t->leftChild);
if(t->rightChild!=NULL) que.push(t->rightChild);
}
}
int main()
{
Node * head= new Node(0);
Node * node1= new Node(1);
Node * node2= new Node(2);
Node * node3= new Node(3);
Node * node4= new Node(4);
Node * node5= new Node(5);
Node * node6= new Node(6);
head->leftChild=node1;
head->rightChild=node2;
node1->leftChild=node3;
node1->rightChild=node4;
node2->rightChild=node5;
node4->leftChild=node6;
/* LevelOrderTraverse(head,print);
cout<<endl;
PreOrderTraverse(head,print);
cout<<endl;*/
InOrder(head,print);
cout<<endl;
InOrderTraverse(head,print);
cout<<endl;
PostOrder(head,print);
cout<<endl;
PostOrderTraverse(head,print);
cout<<endl;
return 0;
}
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java中对List集合的常用操作详解
SpringBoot利用@Retryable注解实现接口重试
一文搞懂并学会使用SpringBoot的Actuator运行状态监控组件的详细教程
![](https://img.aspxhome.com/file/2023/8/67488_0s.png)
C#用NPOI导出导入Excel帮助类
Netty分布式ByteBuf使用命中缓存的分配解析
![](https://img.aspxhome.com/file/2023/1/70561_0s.png)
Java程序员面试中的多线程问题总结
Java Maven settings.xml中私有仓库配置详解
![](https://img.aspxhome.com/file/2023/4/66234_0s.jpg)
Springboot项目快速实现过滤器功能
![](https://img.aspxhome.com/file/2023/9/57729_0s.png)
详解Spring Security如何配置JSON登录
![](https://img.aspxhome.com/file/2023/3/72353_0s.png)
c# WPF中CheckBox样式的使用总结
![](https://img.aspxhome.com/file/2023/1/88421_0s.gif)
mybatis中使用InsertProvider注解报错解决全过程
C#、vb.net及SQL判断指定年份是否为闰年的方法
Spring Bean创建和循环依赖
![](https://img.aspxhome.com/file/2023/9/71179_0s.webp)
关于Scanner对象的输入结束标记问题
![](https://img.aspxhome.com/file/2023/8/77368_0s.png)
详解JAVA类加载机制(推荐)
Spring代理对象导致的获取不到原生对象注解的解决
java 实现通过 post 方式提交json参数操作
SpringBoot使用Redisson实现分布式锁(秒杀系统)
![](https://img.aspxhome.com/file/2023/7/83487_0s.jpg)