当前位置：网站首页>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;
}
边栏推荐
- 【pytorch】nn. AdaptiveMaxPool2d
- 【pytorch】nn.AdaptiveMaxPool2d
- Mysql8.0 learning record 17 -create table
- Shell script -select in loop
- The jar package embedded with SQLite database is deployed by changing directories on the same machine, and the newly added database records are gone
- I use flask to write the website "one"
- Shell脚本-select in循环
- 【ESP 保姆级教程 预告】疯狂Node.js服务器篇 ——案例：ESP8266 + DHT11 +NodeJs本地服务+ MySQL数据库
- 2.4 激活函数
- The fixed assets management system enables enterprises to dynamically master assets
猜你喜欢
小鸟识别APP
2.3 【kaggle数据集 - dog breed 举例】数据预处理、重写Dataset、DataLoader读取数据
3D打印Arduino 四轴飞行器
大型工厂设备管理痛点和解决方案
![[video game training] real topic of 2013 video game of infrared optical communication device](/img/ef/c2c45c1c6c24aed0a4e93101047372.png)
[video game training] real topic of 2013 video game of infrared optical communication device
Football and basketball game score live broadcast platform source code /app development and construction project
Redis -- lattice connects to redis cluster
Redis——Lettuce连接redis集群
Bimianhongfu queren()
How to solve the problem of fixed assets management and inventory?
随机推荐
2.3 [kaggle dataset - dog feed example] data preprocessing, rewriting dataset, dataloader reading data
Shell脚本-select in循环
3D打印Arduino 四轴飞行器
Dynamic proxy
[pytorch learning] torch device
Shell script -read command: read data entered from the keyboard
2.3 【kaggle数据集 - dog breed 举例】数据预处理、重写Dataset、DataLoader读取数据
Common interview questions for embedded engineers 2-mcu_ STM32
Embedded Engineer Interview frequently asked questions
Shell script case in statement
How to effectively align team cognition
Programming with C language: calculate with formula: e ≈ 1+1/1+ 1/2! …+ 1/n!， Accuracy is 10-6
[ESP nanny level tutorial] crazy completion chapter - Case: ws2812 light control system based on Alibaba cloud, applet and Arduino
It technology ebook collection
[pytorch] softmax function
3D printing Arduino four axis aircraft
Databinding source code analysis
Nacos - 配置管理
Input标签的type设置为number，去掉上下箭头
Why is the Ltd independent station a Web3.0 website!