# [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