当前位置：网站首页>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;
}
边栏推荐
- How to manage fixed assets well? Easy to point and move to provide intelligent solutions
- Design and manufacture of simple digital display electronic scale
- Shell script - special variables: shell $, $*, [email protected], $$$
- 如何做好固定资产管理？易点易动提供智能化方案
- Promise异步编程
- 【pytorch】nn. AdaptiveMaxPool2d
- LogBack
- Mise en œuvre simple de l'équilibrage de la charge par nacos
- Shell script echo command escape character
- Daily office consumables management solution
猜你喜欢
2.2 【pytorch】torchvision. transforms
如何做好固定资产管理？易点易动提供智能化方案
Ape anthropology topic 20 (the topic will be updated from time to time)
An overview of the design of royalties and service fees of mainstream NFT market platforms
猿人学第20题（题目会不定时更新）
Dynamic proxy
Daily practice of C language - day 80: currency change
Reproduced Xray - cve-2017-7921 (unauthorized access by Hikvision)
NiO zero copy
Design and manufacture of simple digital display electronic scale
随机推荐
Personal decoration notes
Graduation season, I want to tell you
Vsync+ triple cache mechanism +choreographer
序列化、监听、自定义注解
3D printing Arduino four axis aircraft
Jetson nano installs tensorflow GPU and problem solving
Win7 pyinstaller reports an error DLL load failed while importing after packaging exe_ Socket: parameter error
Mysql8.0 learning record 17 -create table
Understanding and implementation of AVL tree
I use flask to write the website "one"
Daily office consumables management solution
【ESP 保姆级教程】疯狂毕设篇 —— 案例：基于阿里云、小程序、Arduino的温湿度监控系统
Microcomputer principle - bus and its formation
nacos簡易實現負載均衡
Shell script - array definition and getting array elements
Shell脚本-select in循环
Mise en œuvre simple de l'équilibrage de la charge par nacos
nacos服务配置和持久化配置
Shell script -select in loop
Log4j 日志框架