当前位置：网站首页>Tree structure -- binary tree 2 non recursive traversal
Tree structure -- binary tree 2 non recursive traversal
2022-07-01 09:11:00 【Roaming brother laugh】
Catalog
Complete code （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){
// Due to the output value , So the queue stores values
// To test the function , Call the implemented function directly
if(t.root==NULL) return;
seqQueue<T> s;
s.enQueue(t.root->data);// value
T tmp,lc,rc;
while(!s.is_empty()){
tmp=s.deQueue();
// Call the left and right children
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;
// Pass parameters to public nonparametric functions
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);
// Auxiliary function --- Find the node pointer of the given node value
node* find(T x,node* t) const{// Pass value x And the pointer to return t
node* tmp;
if(t==NULL) return NULL;
// Root left and right
if(t->data==x) return t;
tmp=find(x,t->lchild);
if(tmp) return tmp;
else return find(x,t->rchild);
}
public:
/* Constructors */
binTree(){ root=NULL;}
/* Hierarchical traversal creates a tree + Traverse the existing tree hierarchically */
void createTree(T flag);// use flag Represents an empty node
void levelTraverse() const;// Level traversal
/* Recursive implementation of the sequence before, during and after traversal */
void preTraverse() const;
void midTraverse() const;
void postTraverse() const;
/* Find the height of the tree + Number of leaf nodes */
int nodeSize() const;
int treeHigh() const;
/* Find the left and right child node values --- The ginseng x And denote empty flag*/
T lchild(T x,T flag) const;
T rchild(T x,T flag) const;
// Empty + prune
void clear();
void defLeft(T x);
void defRight(T x);
};
// Create trees + Level traversal
template<class T>
void binTree<T>::createTree(T flag){
seqQueue<node*> s;// Create a queue with node pointers
// Enter the root node and join the queue
T x;
cout<<" Enter the root node :";
cin>>x;
s.enQueue(root=new node(x));
// access node , And join the children around Feikong
node* tmp;
T ldata,rdata;
while(!s.is_empty()){
tmp=s.deQueue();
cout<<" Input node "<<tmp->data<<" Right and left :";
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 Level traversal :";
if(root==NULL) return;
seqQueue<node*> s;
s.enQueue(root);
while(!s.is_empty()){
node* tmp=s.deQueue();
cout<<tmp->data<<" ";// Output
if(tmp->lchild) s.enQueue(tmp->lchild);
if(tmp->rchild) s.enQueue(tmp->rchild);
}
}
// Recursive implementation of the sequence before, during and after traversal
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 The former sequence traversal :";
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 In the sequence traversal :";
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 After the sequence traversal :";
postTraverse(root);
}
// Find the number of knots + Tree height
template<class T>
int binTree<T>::nodeSize(node* t) const{
if(t==NULL) return 0;
// Number of nodes = root + The left subtree + Right subtree
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);// root +max( Height of left subtree , Height of right subtree )
}
template<class T>
int binTree<T>::treeHigh() const{
return treeHigh(root);
}
// Ask for the right child
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;
}
// Empty + prune
template<class T>
void binTree<T>::clear(node* &t){
if(t==NULL) return;
clear(t->lchild);
clear(t->rchild);
delete t;
t=NULL;// Leave the root node empty
}
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);
}Main function test
#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;
}
Non recursive traversal
Import stack file ----stack.h
template<class elemType>
class seqStack{
private:
elemType* data;
int maxsize;
int top_s;
void doublespace();// Capacity expansion
public:
// structure + destructor
seqStack(int initszie=10){
data=new elemType[initszie];
maxsize=initszie;
top_s=-1;
}
~seqStack(){ delete[] data;}
// Function operation
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;
}
};
// Capacity expansion
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;
}Preamble implementation ：
void preTraverse() const{ seqStack<node*> s; if(root==NULL) return; cout<<" The former sequence traversal ："; s.push(root); node* tmp; while(!s.is_empty()){ tmp=s.pop(); cout<<tmp->data<<" "; // Because stack LIFO , Be sure to turn right before left if(tmp->rchild) s.push(tmp->rchild); if(tmp->lchild) s.push(tmp->lchild); } }Relatively simple , Similar to hierarchical traversal , Just be sure to put your child in the stack first , Then left the child into the stack
Middle preface
void midTraverse() const{// Non recursive middle order /* Because you need to record the number of times out of the stack , So introduce structure elem*/ if(root==NULL) return; struct elem{ node* cur; int time; elem(node* p=NULL):cur(p),time(0){ }// Constructors }; cout<<" Non recursive middle order traversal ："; // initialization --- Equipped with elem And elem Variable seqStack<elem> s; elem bt(root); s.push(bt); elem tmp;// Record the stack while(!s.is_empty()){ tmp=s.pop(); if(tmp.time==1){ // It indicates that it has been out of the stack once , That is, the left node access ends cout<<tmp.cur->data<<" "; // Next, visit the right child node if(tmp.cur->rchild) s.push(tmp.cur->rchild); } else{ tmp.time+=1; s.push(tmp);// This is my first visit , Push ,time+1 // The left child enters the stack if(tmp.cur->lchild) s.push(tmp.cur->lchild); } } cout<<endl; }Be careful ：elem(tmp.cur->lchild)----- yes elem type , Variable name is not specified , Similar temporary variables
Be careful ： If it comes out of the stack once , that time+1, And when visiting the left node , must do ： Go back to the stack push once
In the following order
void postTraverse() const{// Non recursive postorder /* Because you need to record the number of times out of the stack , So introduce structure elem*/ if(root==NULL) return; struct elem{ node* cur; int time; elem(node* p=NULL):cur(p),time(0){ }// Constructors }; cout<<" Non recursive postorder traversal ："; // initialization --- Equipped with elem And elem Variable seqStack<elem> s; elem bt(root); s.push(bt); elem tmp;// Record the stack // The above is consistent with the middle order traversal code while(!s.is_empty()){ tmp=s.pop(); if(tmp.time==2){ // Visited twice , That is, the left and right children have traversed , Output results cout<<tmp.cur->data<<" "; } else{ if(tmp.time==1){ // Left child has visited , The right child enters the stack tmp.time+=1; s.push(tmp);// Don't forget , When the right child enters the stack , Enter the stack again if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));// Pay attention to the type } else{ tmp.time+=1; s.push(tmp);// Enter the stack by yourself , Then traverse the left child if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild)); } } } }The only difference from the middle order is ：
while(!s.is_empty()){
// difference
}
if(tmp.time==2){ // Visited twice , That is, the left and right children have traversed , Output results cout<<tmp.cur->data<<" "; } else{ if(tmp.time==1){ // Left child has visited , The right child enters the stack tmp.time+=1; s.push(tmp);// Don't forget , When the right child enters the stack , Enter the stack again if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));// Pay attention to the type } else{ tmp.time+=1; s.push(tmp);// Enter the stack by yourself , Then traverse the left child if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild)); } }Notice this root - left and right process ：
if Access root
else if for the first time --- Left the child
else The second time --- The right child
The whole program
#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();// Static initialization tree
void preTraverse() const{// Non recursive preamble
if(root==NULL) return;
cout<<" Non recursive preamble traversal ：";
// Stack the root node
seqStack<node*> s;// The element type of the stack is --node*
s.push(root);
node* tmp;// Record the stack elements
while(!s.is_empty()){
tmp=s.pop();// Stack top element out of stack
cout<<tmp->data<<" ";// The former sequence traversal -- Visit root first
// Because of the last in, first out of the stack , The right child enters the stack before the left child
if(tmp->rchild) s.push(tmp->rchild);
if(tmp->lchild) s.push(tmp->lchild);
}
cout<<endl;
}
void midTraverse() const{// Non recursive middle order
/* Because you need to record the number of times out of the stack , So introduce structure elem*/
if(root==NULL) return;
struct elem{
node* cur;
int time;
elem(node* p=NULL):cur(p),time(0){ }// Constructors
};
cout<<" Non recursive middle order traversal ：";
// initialization --- Equipped with elem And elem Variable
seqStack<elem> s;
elem bt(root);
s.push(bt);
elem tmp;// Record the stack
while(!s.is_empty()){
tmp=s.pop();
if(tmp.time==1){
// It indicates that it has been out of the stack once , That is, the left node access ends
cout<<tmp.cur->data<<" ";
// Next, visit the right child node
if(tmp.cur->rchild) s.push(tmp.cur->rchild);
}
else{
tmp.time+=1;
s.push(tmp);// This is my first visit , Push ,time+1
// The left child enters the stack
if(tmp.cur->lchild) s.push(tmp.cur->lchild);
}
}
cout<<endl;
}
void postTraverse() const{// Non recursive postorder
/* Because you need to record the number of times out of the stack , So introduce structure elem*/
if(root==NULL) return;
struct elem{
node* cur;
int time;
elem(node* p=NULL):cur(p),time(0){ }// Constructors
};
cout<<" Non recursive postorder traversal ：";
// initialization --- Equipped with elem And elem Variable
seqStack<elem> s;
elem bt(root);
s.push(bt);
elem tmp;// Record the stack
// The above is consistent with the middle order traversal code
while(!s.is_empty()){
tmp=s.pop();
if(tmp.time==2){
// Visited twice , That is, the left and right children have traversed , Output results
cout<<tmp.cur->data<<" ";
}
else{
if(tmp.time==1){
// Left child has visited , The right child enters the stack
tmp.time+=1;
s.push(tmp);// Don't forget , When the right child enters the stack , Enter the stack again
if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));// Pay attention to the type
}
else{
tmp.time+=1;
s.push(tmp);// Enter the stack by yourself , Then traverse the left child
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);
}Test the main function
int main(){
binTree<char> bt;
bt.createTree();
bt.preTraverse();
bt.midTraverse();
bt.postTraverse();
return 0;
}
边栏推荐
- Shell脚本-while循环详解
- Shell脚本-select in循环
- Yidian Yidong helps enterprises to efficiently manage equipment and improve equipment utilization
- 2.4 激活函数
- jeecg 重启报40001
- Principles of Microcomputer - Introduction
- FAQ | FAQ for building applications for large screen devices
- nacos服务配置和持久化配置
- Pain points and solutions of equipment management in large factories
- Input标签的type设置为number，去掉上下箭头
猜你喜欢
![2.3 [kaggle dataset - dog feed example] data preprocessing, rewriting dataset, dataloader reading data](/img/6e/d8ef618127ac492f5142f7b600266d.png)
2.3 [kaggle dataset - dog feed example] data preprocessing, rewriting dataset, dataloader reading data
I use flask to write the website "one"
FreeRTOS learning easy notes
Pain points and solutions of equipment management in large factories
Nacos - gestion de la configuration
2.4 激活函数
MySQL optimization
小鸟识别APP
2.2 【pytorch】torchvision.transforms
Mise en œuvre simple de l'équilibrage de la charge par nacos
随机推荐
Shell脚本-位置参数（命令行参数）
Record a redis timeout
日常办公耗材管理解决方案
Full mark standard for sports items in the high school entrance examination (Shenzhen, Anhui and Hubei)
Common interview questions for embedded engineers 2-mcu_ STM32
Installing Oracle EE
Key points of NFT supervision and overseas policies
2.3 【pytorch】数据预处理 torchvision.datasets.ImageFolder
毕业季，我想对你说
Mysql8.0 learning record 17 -create table
Win7 pyinstaller reports an error DLL load failed while importing after packaging exe_ Socket: parameter error
An overview of the design of royalties and service fees of mainstream NFT market platforms
如何一站式高效管理固定资产？
nacos服务配置和持久化配置
通过 代码实例 理解 浅复制 与 深复制
猿人学第20题（题目会不定时更新）
Jetson Nano 安装TensorFlow GPU及问题解决
如何做好固定资产管理？易点易动提供智能化方案
Shell脚本-字符串
Which method is good for the management of fixed assets of small and medium-sized enterprises?