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


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 .
 Insert picture description here According to the rules , The traversal of binary tree has : Before the order / Middle preface / The recursive structure of post order traverses

  1. 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
  2. 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
  3. 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 :
 Insert picture description here
 Insert picture description here

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 .

 Insert picture description here 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

Random recommended