## current position：Home>[data structure] chain structure of binary tree (pre order traversal) (middle order traversal) (post order traversal) (sequence traversal)

# [data structure] chain structure of binary tree (pre order traversal) (middle order traversal) (post order traversal) (sequence traversal)

2022-01-27 06:28:17 【Zhou Zhouwang】

### Catalog

Hello, bald men , Let's continue to talk today

**Binary tree**

# Implementation of binary tree chain structure

First of all, we know that a binary tree is composed of a root node and a left subtree and a right subtree ,

As can be seen from the concept , The definition of a binary tree is recursive , Therefore, the basic operations in the subsequent sequence are basically implemented according to this concept .

## Traversal of binary tree

### Before the order 、 Middle order and post order traversal

Learning binary tree structure , The simplest way is to traverse . The so-called binary tree traversal (Traversal) According to certain rules , Operate the nodes in the binary tree in turn , And each node operates only once . The operation of the access node depends on the specific application problem . Traversal is one of the most important operations on binary trees , It is also the basis for other operations on the binary tree .

According to the rules , The traversal of binary tree has ：** Before the order / Middle preface / The recursive structure of post order traverses **

- The former sequence traversal (Preorder Traversal Also called preorder traversal )—— The operation of accessing the root node occurs before traversing its left and right subtrees . Preorder traversal results ：
**ABDCEF** - In the sequence traversal (Inorder Traversal)—— The operation of accessing the root node occurs in traversing its left and right subtrees （ between ）. Middle order traversal result ：
**DBAECF** - After the sequence traversal (Postorder Traversal)—— The operation to access the root node occurs after traversing its left and right subtrees . Subsequent traversal results ：
**DBEFCA**

Because the visited node must be the root of a subtree , therefore N(Node）、L(Left subtree） and R(Right subtree） It can also be interpreted as root 、 Left subtree of root and right subtree of root .NLR、LNR and LRN The difference is also called the first root traversal 、 Middle root traversal and back root traversal .

```
// Binary tree preorder traversal
void PreOrder(BTNode* root);
{
if(root==NULL)
return ;
printf("%c ",root->data);
PreOrder(root->left);
PreOrder(root->right);
}
// Order traversal in binary tree
vvoid InOrder(BTNode* root);
{
if(root==NULL)
return ;
InOrder(root->left);
printf("%c ",root->data);
InOrder(root->right);
}
// Postorder traversal of binary tree
void PostOrder(BTNode* root);
{
if(root==NULL)
return ;
PostOrder(root->left);
PostOrder(root->right);
printf("%c ",root->data);
}
```

Preorder traversal recursive diagram ：

### Sequence traversal

Sequence traversal ： Except for preorder traversal 、 In the sequence traversal 、 After order traversal , We can also traverse the binary tree sequence . Let the level of the root node of the binary tree be 1, Sequence traversal starts from the root node of the binary tree , First visit the root node of the first layer , And then, from left to right, visit number 2 Nodes on the layer , Then there are the nodes of the third layer , And so on , From top to bottom , The process of accessing the nodes of the tree layer by layer from left to right is sequence traversal .

The result of sequence traversal is ABCDEF

Sequence traversal requires the use of ** queue **

** The core idea ：**

1、 Go to the root first , hold A Put in queue ;

2、pop Current team leader A, And then put pop The left child at the head of the team B The right child C Put it in , And print A;

3、 Put the current team leader B node pop fall , And put B The left child D The right child NULL The team , And print B;

4、 Put the current team leader C node pop fall , And put C The left child E The right child F The team , And print C...

Finally print it out ABCDEF 了 .

```
void BinaryTreeLevelOrder(BTNode*root)
{
if(root==NULL)
return ;
Queue q;
QueueInit(&q);
QueuePush(&q,root);
while(!QueueEmpty(&q))
{
BTNode*front=QueueFront(&q);
QueuePop(&q);
printf("%c ",front->data);
if(front->left)
QueuePush(&q,front->left);
if(front->right)
QueuePush(&q,front->right);
}
printf("\n");
QueueDestroy(&q);
}
```

Binary tree ** Sequence traversal ** amount to ** breadth-first ** Traverse ,** The former sequence traversal ** amount to ** Depth first ** Traverse

Next up ： Binary tree correlation OJ topic

Thank you for reading , See you next time

If there is a mistake Welcome to exchange

copyright notice

author[Zhou Zhouwang],Please bring the original link to reprint, thank you.

https://en.cdmana.com/2022/01/202201270628121145.html

## The sidebar is recommended

- [thinking] the difference between singleton mode and static method - object-oriented programming
- C / C + +: static keyword summary
- Idea does not have the artifacts option when configuring Tomcat
- I don't know how to start this
- MySQL slow log optimization
- Two pronged approach, Tsinghua Professor Pro code JDK and hotspot source code notes, one-time learning to understand
- C + + recursive knapsack problem
- The use of GIT and GitHub and the latest git tutorial are easy to understand -- Video notes of crazy God speaking
- Ignition database test
- A list that contains only strings. What other search methods can be used except sequential search