二叉树的遍历算法(详细示例分析)
发布时间: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;
}
猜你喜欢
- 配置两个parent的方法在向pom.xml 文件中添加依赖之前需要先添加spring-boot-starter-parent。spring
- 机器跑了一晚上,发现有崩溃现象,由于页面内有动态绘图功能,我怀疑是绘图原因,但是今天上午有人提醒我才想到,是不是间隔调用时DWR产生了内存泄
- 现工作中有需求要进行批量新增和修改实现了以下几种方式代码中foreach insert/update多线程foreach insert/up
- 目录int和Integer的区别及自动装箱和自动拆箱Integer和int的对比,如下所示:自动装箱和自动拆箱:Integer的自动拆装箱的
- HttpClient使用post方法提交数据 源代码:package post;import Java.io.IOException;imp
- 释放公平锁(基于JDK1.7.0_40)1. unlock()unlock()在ReentrantLock.java中实现的,源码如下:pu
- wait(), notify(), notifyAll()等方法介绍在Object.java中,定义了wait(), notify()和no
- 笔者语录: 我发现我喜欢捣鼓一些小玩意儿,虽然官网(见文末)写得很明白了,但是咱们对感兴趣的部分来敲一遍代码好吧。过滤器简介:简介logba
- 每种编程语言都有自己操作内存中元素的方式,例如在 C 和 C++ 里是通过指针,而在 Java 中则是通过“引用”。在 JDK.1.2 之后
- C# 和 java 比较:java 中使用的是接口。C# 使用委托机制,可以用时 + 运算符进行注册,直接多播。而 java 中是一般是使用
- 1. 概述官方JavaDocsApi: javax.swing.JList JList,列表框。JList 以列表的形式展示多个选项,允许用
- 线程间通信我们看下面的图我们来看线程间通信的原理:线程(Thread B)和线程(Thread A)通信, 首先线程A 必须实现同步上下文对
- 模式介绍命令模式(Command Pattern) :在软件设计中,我们经常需要向某些对象发送请求,但是并不知道请求的接收者是谁,也不知道被
- 1. 人机对战要增添一个人机对战的模块, 最大的难点就是如何让人机知道下在什么位置是最好的, 不仅要具备进攻的能力, 还需要具备防守的能力.
- 标准c++中string类函数介绍注意不是CString之所以抛弃char*的字符串而选用C++标准程序库中的string类,是因为他和前者
- 界面开发中,经常使用观察者设计模式来实现文档/视图模式,当文档内容改变时,作为观察者的用户视图必须相应作出调整以向用户呈现文档的状态。由于语
- 起源 [1946: John von Neumann, Stan Ulam, and Nick Metropolis, all a
- Java定义Long数据类型Long lg=10L;只需要在定义的的整型后面加个L;就和定义float数据类型一样Float ft=5.20
- 本文实例讲述了winform绑定快捷键的方法。分享给大家供大家参考。具体分析如下:第一种:Alt + *(按钮快捷键)在大家给button、
- -vmargs -Xms128M -Xmx512M -XX:PermSize=64M -XX:MaxPermSize=128M 这里有几个问