[data structure] three traversals of binary tree -- creation and output

UltraMar1ne 2022-05-22 12:23:32 阅读数:975

datastructuretraversalsbinarytree

There are three ways to traverse a binary tree : The first sequence traversal 、 Middle order traversal and post order traversal .

Let's make it a rule now : In any traversal mode , We all let the left subtree traverse before the right subtree . In this way, the traversal mode can be changed from 6 The above three categories have been changed into the above three categories .

use N Represents the root node , These three traversal methods can be divided into :NLR,LNR,LRN.

One 、 About ADT Definition and statement of

Before creating a binary tree , We need to create an abstract data type first ( abbreviation ADT):

typedef struct bt{
 //binary tree For short , Ha ha ha quq
ElemType data;
bt *left,*right; // Left and right subtrees of nodes 
}BT;

Two 、 The creation of binary tree

notes : Default using namespace std; It's too late

Establishment of binary tree based on preorder traversal :

void preOrderCreateo(BT *&t){

ElemType elem;
cin>>elem;
if(elem=='#'){
 // You can use # As a sign not to create subtrees 
t=NULL;
}
else{

t=new BT;
t->data=elem;
t->left=NULL;
t->right=NULL;
preOrderCreate(t->left);
preOrderCreate(t->right); // Recursively create left and right subtrees 
}
}

Suggestions for establishing binary tree The first sequence traversal yo ~ The other two are not explained here quq

3、 ... and 、 Traversal of binary tree

1. Based on preorder traversal, the preorder traversal sequence of output binary tree is established

void preOrder(BT *&t){

if(t!=NULL){

cout<<t->data<<" "; // First output the current node 
preOrder(t->left); // And then I go through the left subtree 
preOrder(t->right); // Finally, traverse the right subtree 
}
}

2. Based on preorder traversal, a middle order traversal sequence of output binary tree is established

void preOrder(BT *&t){

if(t!=NULL){

preOrder(t->left); // First traverse the left subtree 
cout<<t->data<<" "; // Then output the current node 
preOrder(t->right); // Finally, traverse the right subtree 
}
}

3. Create a post order traversal sequence of output binary tree based on pre order traversal

void preOrder(BT *&t){

if(t!=NULL){

preOrder(t->left); // First traverse the left subtree 
preOrder(t->right); // And then I go through the right subtree 
cout<<t->data<<" "; // Finally, output the current node 
}
}

obviously , The traversal method is different , The output will also be affected .A Be sure to pay attention to the requirements of the topic !!

copyright:author[UltraMar1ne],Please bring the original link to reprint, thank you. https://en.javamana.com/2022/142/202205211828223960.html