当前位置：网站首页>树结构---二叉树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;
}
边栏推荐
- Microcomputer principle - bus and its formation
- 中考体育项目满分标准（深圳、安徽、湖北）
- nacos简易实现负载均衡
- Performance improvement 2-3 times! The second generation Kunlun core server of Baidu AI Cloud was launched
- Football and basketball game score live broadcast platform source code /app development and construction project
- How to manage fixed assets efficiently in one stop?
- Public network cluster intercom +gps visual tracking ｜ help the logistics industry with intelligent management and scheduling
- 类加载
- Shell script -while loop explanation
- MySQL optimization
猜你喜欢
Understanding and implementation of AVL tree
FreeRTOS learning easy notes
集团公司固定资产管理的痛点和解决方案
Daily practice of C language - day 80: currency change
Reproduced Xray - cve-2017-7921 (unauthorized access by Hikvision)
Redis -- lattice connects to redis cluster
3D打印Arduino 四轴飞行器
【检测技术课案】简易数显电子秤的设计与制作
jeecg 重启报40001
FAQ | FAQ for building applications for large screen devices
随机推荐
Imitation of Baidu search results top navigation bar effect
In the middle of the year, where should fixed asset management go?
Nacos - 服务发现
Shell脚本-变量的定义、赋值和删除
nacos简易实现负载均衡
Shell script - array definition and getting array elements
Common interview questions for embedded engineers 2-mcu_ STM32
Promise异步编程
Shell script - positional parameters (command line parameters)
Meituan machine test in 2022
Shell script -select in loop
【ESP 保姆级教程】疯狂毕设篇 —— 案例：基于阿里云和Arduino的化学环境系统检测，支持钉钉机器人告警
Jetson nano installs tensorflow GPU and problem solving
【pytorch】softmax函数
Bimianhongfu queren()
通过 代码实例 理解 浅复制 与 深复制
Key points of NFT supervision and overseas policies
Set the type of the input tag to number, and remove the up and down arrows
Shell script - special variables: shell $, $*, [email protected], $$$
【MFC开发（16）】树形控件Tree Control