当前位置：网站首页>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;
}
边栏推荐
- Daily office consumables management solution
- Naoqi robot summary 28
- pcl_ Viewer command
- 【pytorch】nn. AdaptiveMaxPool2d
- Meituan machine test in 2022
- 【ESP 保姆级教程】疯狂毕设篇 —— 案例：基于物联网的GY906红外测温门禁刷卡系统
- 【pytorch】2.4 卷积函数 nn.conv2d
- LogBack
- Yidian Yidong helps enterprises to efficiently manage equipment and improve equipment utilization
- Full mark standard for sports items in the high school entrance examination (Shenzhen, Anhui and Hubei)
猜你喜欢
2.2 【pytorch】torchvision. transforms
【pytorch】nn. Crossentropyloss() and nn NLLLoss()
How to manage fixed assets efficiently in one stop?
2.4 激活函数
Nacos - gestion de la configuration
Bimianhongfu queren()
TV size and viewing distance
Dynamic proxy
An overview of the design of royalties and service fees of mainstream NFT market platforms
How to manage fixed assets well? Easy to point and move to provide intelligent solutions
随机推荐
Is it safe to dig up money and make new shares
Graduation season, I want to tell you
【pytorch】transforms. Normalize((0.5, 0.5, 0.5), (0.5, 0.5, 0.5))
Understand shallow replication and deep replication through code examples
Class loading
【ESP 保姆级教程 预告】疯狂Node.js服务器篇 ——案例：ESP8266 + MQ系列 + NodeJs本地服务 + MySql存储
Databinding source code analysis
Shell script - special variables: shell $, $*, [email protected], $$$
Set the type of the input tag to number, and remove the up and down arrows
Promise异步编程
2.3 [pytorch] data preprocessing torchvision datasets. ImageFolder
Shell script -select in loop
Shell script echo command escape character
Ranking list of domestic databases in February, 2022: oceanbase regained the "three consecutive increases", and gaussdb is expected to achieve the largest increase this month
序列化、监听、自定义注解
C language student information management system
OSPF - virtual link details (including configuration commands)
Nacos - Configuration Management
Jetson Nano 安装TensorFlow GPU及问题解决
易点易动助力企业设备高效管理，提升设备利用率