当前位置：网站首页>树结构---二叉树2非递归遍历
树结构---二叉树2非递归遍历
2022-07-01 09:05:00 【遨游的laugh哥】
目录
完整代码（binTree.h）
#include"seqQueue.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class T>
class binTree{
friend void printTree(const binTree<T>& t,T flag){
//由于要输出值，所以队列存值
//为了检验函数功能，直接调用已实现函数
if(t.root==NULL) return;
seqQueue<T> s;
s.enQueue(t.root->data);//值
T tmp,lc,rc;
while(!s.is_empty()){
tmp=s.deQueue();
//调用左右孩子
lc=t.lchild(tmp,flag);
rc=t.rchild(tmp,flag);
cout<<"("<<tmp<<" "<<lc<<" "<<rc<<")"<<endl;
if(lc!=flag) s.enQueue(lc);
if(rc!=flag) s.enQueue(rc);}
}
private:
struct node{
T data;
node *lchild,*rchild;
node():lchild(NULL),rchild(NULL){}
node(const T& x,node* p=NULL,node* q=NULL):data(x),lchild(p),rchild(q){}
~node(){}
};
node* root;
//为公有无参函数传参
void preTraverse(node* t) const;
void midTraverse(node* t) const;
void postTraverse(node* t) const;
int nodeSize(node* t) const;
int treeHigh(node* t) const;
void clear(node* &t);
//辅助函数---找给定结点值的结点指针
node* find(T x,node* t) const{//传值x和要返回的指针t
node* tmp;
if(t==NULL) return NULL;
//根左右
if(t->data==x) return t;
tmp=find(x,t->lchild);
if(tmp) return tmp;
else return find(x,t->rchild);
}
public:
/*构造函数*/
binTree(){ root=NULL;}
/*层次遍历创建树+层次遍历已有树*/
void createTree(T flag);//用flag表示空结点
void levelTraverse() const;//层次遍历
/*递归实现前中后序遍历*/
void preTraverse() const;
void midTraverse() const;
void postTraverse() const;
/*求树的高度+叶子结点个数*/
int nodeSize() const;
int treeHigh() const;
/*求左右孩子结点值---传参x和表示空的flag*/
T lchild(T x,T flag) const;
T rchild(T x,T flag) const;
//清空+剪枝
void clear();
void defLeft(T x);
void defRight(T x);
};
//创建树+层次遍历
template<class T>
void binTree<T>::createTree(T flag){
seqQueue<node*> s;//创建装有结点指针的队列
//输入根节点并入队
T x;
cout<<"输入根节点:";
cin>>x;
s.enQueue(root=new node(x));
//访问结点，并将非空左右孩子入队
node* tmp;
T ldata,rdata;
while(!s.is_empty()){
tmp=s.deQueue();
cout<<"输入结点"<<tmp->data<<"的左右孩子:";
cin>>ldata>>rdata;
if(ldata!=flag) s.enQueue(tmp->lchild=new node(ldata));
if(rdata!=flag) s.enQueue(tmp->rchild=new node(rdata));
}
cout<<"create successful!\n";
}
template<class T>
void binTree<T>::levelTraverse() const{
cout<<"\n层次遍历:";
if(root==NULL) return;
seqQueue<node*> s;
s.enQueue(root);
while(!s.is_empty()){
node* tmp=s.deQueue();
cout<<tmp->data<<" ";//输出
if(tmp->lchild) s.enQueue(tmp->lchild);
if(tmp->rchild) s.enQueue(tmp->rchild);
}
}
//递归实现前中后序遍历
template<class T>
void binTree<T>::preTraverse(node* t) const{
if(t==NULL) return;
cout<<t->data<<" ";
preTraverse(t->lchild);
preTraverse(t->rchild);
}
template<class T>
void binTree<T>::preTraverse() const{
cout<<"\n前序遍历:";
preTraverse(root);
}
template<class T>
void binTree<T>::midTraverse(node* t) const{
if(t==NULL) return;
midTraverse(t->lchild);
cout<<t->data<<" ";
midTraverse(t->rchild);
}
template<class T>
void binTree<T>::midTraverse() const{
cout<<"\n中序遍历:";
midTraverse(root);
}
template<class T>
void binTree<T>::postTraverse(node* t) const{
if(t==NULL) return;
postTraverse(t->lchild);
postTraverse(t->rchild);
cout<<t->data<<" ";
}
template<class T>
void binTree<T>::postTraverse() const{
cout<<"\n后序遍历:";
postTraverse(root);
}
//求结点数+树高
template<class T>
int binTree<T>::nodeSize(node* t) const{
if(t==NULL) return 0;
//结点数=根+左子树+右子树
else return nodeSize(t->lchild)+nodeSize(t->rchild)+1;
}
template<class T>
int binTree<T>::nodeSize() const{
return nodeSize(root);
}
template<class T>
int binTree<T>::treeHigh(node* t) const{
if(t==NULL) return 0;
int L,R;
L=treeHigh(t->lchild);
R=treeHigh(t->rchild);
return 1+(L>R?L:R);//根+max(左子树高度，右子树高度)
}
template<class T>
int binTree<T>::treeHigh() const{
return treeHigh(root);
}
//求左右孩子
template<class T>
T binTree<T>::lchild(T x,T flag) const{
node* tmp=find(x,root);
if(tmp==NULL||tmp->lchild==NULL) return flag;
else return tmp->lchild->data;
}
template<class T>
T binTree<T>::rchild(T x,T flag) const{
node* tmp=find(x,root);
if(tmp==NULL||tmp->rchild==NULL) return flag;
else return tmp->rchild->data;
}
//清空+剪枝
template<class T>
void binTree<T>::clear(node* &t){
if(t==NULL) return;
clear(t->lchild);
clear(t->rchild);
delete t;
t=NULL;//把根节点置空
}
template<class T>
void binTree<T>::clear(){
clear(root);
}
template<class T>
void binTree<T>::defLeft(T x){
node* tmp=find(x,root);
if(tmp==NULL) return;
clear(tmp->lchild);
}
template<class T>
void binTree<T>::defRight(T x){
node* tmp=find(x,root);
if(tmp==NULL) return;
clear(tmp->rchild);
}主函数测试
#include"binTree.h"
#include<stdlib.h>
#include<iostream>
using namespace std;
int main(){
binTree<char> bt;
bt.createTree('#');
printTree(bt,'#');
cout<<bt.nodeSize()<<" "<<bt.treeHigh()<<endl;
bt.defLeft('D');
printTree(bt,'#');
cout<<endl;
cout<<bt.nodeSize()<<" "<<bt.treeHigh()<<endl;
bt.defRight('B');
printTree(bt,'#');
cout<<endl;
cout<<bt.nodeSize()<<" "<<bt.treeHigh()<<endl;
return 0;
}
非递归的前中后遍历
引入栈文件----stack.h
template<class elemType>
class seqStack{
private:
elemType* data;
int maxsize;
int top_s;
void doublespace();//扩容
public:
//构造+析构
seqStack(int initszie=10){
data=new elemType[initszie];
maxsize=initszie;
top_s=-1;
}
~seqStack(){ delete[] data;}
//函数操作
bool is_empty() const{ return top_s==-1;}
elemType top() const{ return data[top_s];}
elemType pop(){
return data[top_s--];
}
void push(const elemType& x){
data[++top_s]=x;
}
};
//扩容
template<class elemType>
void seqStack<elemType>::doublespace(){
elemType* tmp;
maxsize*=2;
data=new elemType[maxsize];
for(int i=0;i<=top_s;i++){
data[i]=tmp[i];
}
delete[] tmp;
}前序实现：
void preTraverse() const{ seqStack<node*> s; if(root==NULL) return; cout<<"前序遍历："; s.push(root); node* tmp; while(!s.is_empty()){ tmp=s.pop(); cout<<tmp->data<<" "; //由于栈后进先出，一定要先右后左 if(tmp->rchild) s.push(tmp->rchild); if(tmp->lchild) s.push(tmp->lchild); } }比较简单，类似层次遍历，只是一定要先右孩子进栈，然后左孩子进栈
中序
void midTraverse() const{//非递归中序 /*由于要记录出栈次数，所以引入结构elem*/ if(root==NULL) return; struct elem{ node* cur; int time; elem(node* p=NULL):cur(p),time(0){ }//构造函数 }; cout<<"非递归中序遍历："; //初始化---装有elem的栈和elem变量 seqStack<elem> s; elem bt(root); s.push(bt); elem tmp;//记录出栈 while(!s.is_empty()){ tmp=s.pop(); if(tmp.time==1){ //表明已经出栈过一次了，也就是左结点访问结束 cout<<tmp.cur->data<<" "; //接下来访问右孩子节点 if(tmp.cur->rchild) s.push(tmp.cur->rchild); } else{ tmp.time+=1; s.push(tmp);//自己是第一次访问，入栈，time+1 //左孩子进栈 if(tmp.cur->lchild) s.push(tmp.cur->lchild); } } cout<<endl; }注意：elem(tmp.cur->lchild)-----是elem类型，没有指定变量名，类似临时变量
注意：如果出栈过一次，那么time+1，而且在访问左结点，一定要：再进栈push一次
后序
void postTraverse() const{//非递归后序 /*由于要记录出栈次数，所以引入结构elem*/ if(root==NULL) return; struct elem{ node* cur; int time; elem(node* p=NULL):cur(p),time(0){ }//构造函数 }; cout<<"非递归后序遍历："; //初始化---装有elem的栈和elem变量 seqStack<elem> s; elem bt(root); s.push(bt); elem tmp;//记录出栈 //以上和中序遍历代码一致 while(!s.is_empty()){ tmp=s.pop(); if(tmp.time==2){ //已访问两次，也就是左右孩子都遍历了，输出结果 cout<<tmp.cur->data<<" "; } else{ if(tmp.time==1){ //左孩子已访问，右孩子进栈 tmp.time+=1; s.push(tmp);//一定别忘了，右孩子进栈时，自己再进一次栈 if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//注意类型 } else{ tmp.time+=1; s.push(tmp);//自己进栈，然后遍历左孩子 if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild)); } } } }与中序区别只在：
while(!s.is_empty()){
//区别
}
if(tmp.time==2){ //已访问两次，也就是左右孩子都遍历了，输出结果 cout<<tmp.cur->data<<" "; } else{ if(tmp.time==1){ //左孩子已访问，右孩子进栈 tmp.time+=1; s.push(tmp);//一定别忘了，右孩子进栈时，自己再进一次栈 if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//注意类型 } else{ tmp.time+=1; s.push(tmp);//自己进栈，然后遍历左孩子 if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild)); } }注意这个根左右过程：
if 访问根
else if 第一次---左孩子
else 第二次---右孩子
完整程序
#include<stdlib.h>
#include"seqStack.h"
#include<iostream>
using namespace std;
template<class T>
class binTree{
private:
struct node{
T data;
node *lchild,*rchild;
node():lchild(NULL),rchild(NULL){}
node(const T& x,node* p=NULL,node* q=NULL):data(x),lchild(p),rchild(q){}
~node(){}
};
node* root;
public:
binTree(){ root=NULL;}
void createTree();//静态初始化树
void preTraverse() const{//非递归前序
if(root==NULL) return;
cout<<"非递归前序遍历：";
//将根节点入栈
seqStack<node*> s;//栈的元素类型是--node*
s.push(root);
node* tmp;//记录出栈元素
while(!s.is_empty()){
tmp=s.pop();//栈顶元素出栈
cout<<tmp->data<<" ";//前序遍历--先访问根
//由于栈的后进先出，右孩子先于左孩子进栈
if(tmp->rchild) s.push(tmp->rchild);
if(tmp->lchild) s.push(tmp->lchild);
}
cout<<endl;
}
void midTraverse() const{//非递归中序
/*由于要记录出栈次数，所以引入结构elem*/
if(root==NULL) return;
struct elem{
node* cur;
int time;
elem(node* p=NULL):cur(p),time(0){ }//构造函数
};
cout<<"非递归中序遍历：";
//初始化---装有elem的栈和elem变量
seqStack<elem> s;
elem bt(root);
s.push(bt);
elem tmp;//记录出栈
while(!s.is_empty()){
tmp=s.pop();
if(tmp.time==1){
//表明已经出栈过一次了，也就是左结点访问结束
cout<<tmp.cur->data<<" ";
//接下来访问右孩子节点
if(tmp.cur->rchild) s.push(tmp.cur->rchild);
}
else{
tmp.time+=1;
s.push(tmp);//自己是第一次访问，入栈，time+1
//左孩子进栈
if(tmp.cur->lchild) s.push(tmp.cur->lchild);
}
}
cout<<endl;
}
void postTraverse() const{//非递归后序
/*由于要记录出栈次数，所以引入结构elem*/
if(root==NULL) return;
struct elem{
node* cur;
int time;
elem(node* p=NULL):cur(p),time(0){ }//构造函数
};
cout<<"非递归后序遍历：";
//初始化---装有elem的栈和elem变量
seqStack<elem> s;
elem bt(root);
s.push(bt);
elem tmp;//记录出栈
//以上和中序遍历代码一致
while(!s.is_empty()){
tmp=s.pop();
if(tmp.time==2){
//已访问两次，也就是左右孩子都遍历了，输出结果
cout<<tmp.cur->data<<" ";
}
else{
if(tmp.time==1){
//左孩子已访问，右孩子进栈
tmp.time+=1;
s.push(tmp);//一定别忘了，右孩子进栈时，自己再进一次栈
if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//注意类型
}
else{
tmp.time+=1;
s.push(tmp);//自己进栈，然后遍历左孩子
if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild));
}
}
}
}
};
template<class T>
void binTree<T>::createTree(){
node* f=new node('f');
node* g=new node('g');
node* k=new node('k');
node* h=new node('h');
node* e=new node('e',f,g);
node* j=new node('j',NULL,k);
node* d=new node('d',NULL,e);
node* i=new node('i',j,NULL);
node* b=new node('b',d,NULL);
node* c=new node('c',h,i);
root=new node('a',b,c);
}测试主函数
int main(){
binTree<char> bt;
bt.createTree();
bt.preTraverse();
bt.midTraverse();
bt.postTraverse();
return 0;
}
边栏推荐
- Mysql8.0 learning record 17 -create table
- 中小企业固定资产管理办法哪种好？
- FreeRTOS学习简易笔记
- Glitch free clock switching technology
- C language student information management system
- 【pytorch学习】torch.device
- VSYNC+三重缓存机制+Choreographer
- 类加载
- Shell script -if else statement
- FAQ | FAQ for building applications for large screen devices
猜你喜欢
随机推荐
Naoqi robot summary 28
Shell script echo command escape character
【pytorch】nn.AdaptiveMaxPool2d
Can diffusion models be regarded as an autoencoder?
Redis source code learning (29), compressed list learning, ziplist C (II)
ARM v7的体系结构A、R、M区别，分别应用在什么领域？
C语言学生信息管理系统
中考体育项目满分标准（深圳、安徽、湖北）
Personal decoration notes
Installing Oracle EE
【ESP 保姆级教程 预告】疯狂Node.js服务器篇 ——案例：ESP8266 + MQ系列 + NodeJs本地服务 + MySql存储
【pytorch】transforms.Normalize((0.5, 0.5, 0.5), (0.5, 0.5, 0.5))
FAQ | FAQ for building applications for large screen devices
Full mark standard for sports items in the high school entrance examination (Shenzhen, Anhui and Hubei)
Nacos - service discovery
[ESP nanny level tutorial] crazy completion chapter - Case: ws2812 light control system based on Alibaba cloud, applet and Arduino
Shell script - string
如何高效拉齐团队认知
Why is the Ltd independent station a Web3.0 website!
How to manage fixed assets well? Easy to point and move to provide intelligent solutions