[data structure] binary tree

1. Binary tree chain structure implementation:

The node structure of the chained binary tree:

typedef char BTDatatype;
typedef struct BinaryTreeNode
{
    BTDatatype data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

Before learning the basic operations of a binary tree, you need to create a binary tree before you can learn its related basic operations. Since everyone does not have a deep understanding of the binary tree structure, in order to reduce everyone’s learning costs, here is a quick manual to create a simple binary tree, and quickly enter the binary tree operation learning. When the binary tree structure is almost understood, we will turn to study the real binary tree. How to create.

Before looking at the basic operations of the binary tree, review the concept of the binary tree. The binary tree is:

1. Empty tree

2. Non-empty: the root node, the left subtree of the root node, and the right subtree of the root node.

Code:

BTNode* BuyNode(BTDatatype x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        perror("mallco fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
}

BTNode* n1 = BuyNode(1);
    BTNode* n2 = BuyNode(2);
    BTNode* n3 = BuyNode(3);
    BTNode* n4 = BuyNode(4);
    BTNode* n5 = BuyNode(5);
    BTNode* n6 = BuyNode(6);


    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;

It can be seen from the concept that the definition of a binary tree is recursive, so the basic operations in the subsequent order are basically implemented according to this concept.

Binary tree traversal:

According to the rules, the traversal of the binary tree includes: preorder/inorder/postorder recursive structure traversal:

Preorder traversal (Preorder Traversal, also known as preorder traversal) – the operation of visiting the root node occurs before traversing its left and right subtrees.

Inorder Traversal (Inorder Traversal) – the operation of visiting the root node occurs while traversing its left and right subtrees (in the middle).

Postorder Traversal-The operation of visiting the root node occurs after traversing its left and right subtrees.

2.1 Preorder traversal:

Preorder traversal: visit in the order: root -> left subtree -> right subtree.

It means to visit all the roots on a road, then visit all the left subtrees, and finally visit all the right subtrees.

According to the tree in the above figure, the access order of preorder traversal is:

1, 2, 3, NULL, NULL, NULL, 4, 5, NULL, NULL, 6, NULL, NULL.

The function stack frame expansion diagram is as follows:

Code:

void PrevOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL");
        return;
    }
    // visit first and then recurse
    printf("%d ", root->data);//First visit the node to print
    PrevOrder(root->left);//left subtree traversal
    PrevOrder(root->right);//Right subtree traversal
}

In order to facilitate the understanding of the traversal process, the child nodes of the leaf nodes are represented by NULL in the code, and there is no NULL in normal traversal.

Carefully observe the code implementation, how is recursion implemented?

The ultimate idea of recursion is to divide and conquer big problems into small ones. Taking the above picture as an example, we need to traverse the whole tree, so I can divide the whole tree into several small trees:

And this tree can be divided into two small trees as shown below:

We traverse and decompose the small tree above in detail, and we can see that its left subtree is 3 and its right subtree is NULL. According to the code implementation, first visit and print 2, then recurse to its left subtree (3), visit And print, and continue to recurse to its left subtree, but the left subtree of 3 is NULL, when root == NULL, return, then the program proceeds to visit the right subtree of 3, which is also NULL, return, the child of 3 After the tree traversal is completed, the program goes to the right subtree of 2 to traverse, and the right subtree of 2 is NULL, and returns as well.

Understanding the above process, we can see that the recursion will not go on forever. There must be a cut-off condition in the program. When the cut-off condition is encountered, the program will return until the entire program is recursively completed.

The best way to understand recursion is to draw an expanded diagram of a function’s stack frame yourself.

2.2 Inorder traversal:

In-order traversal: that is, visit in the order of: left subtree -> root -> right subtree.

According to the tree in the above figure, the access order of inorder traversal is:

NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

In-order traversal is to visit and print the left subtree nodes first, and the order of access is different compared with the previous order.

Code:

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

2.3 Postorder traversal:

Post-order traversal: that is, visit in the order of: left subtree -> right subtree -> root node.

According to the tree in the above figure, the post-order traversal access order is:

NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

Code:

void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

2.4 Layer sequence traversal:

Level-order traversal: In addition to pre-order traversal, in-order traversal, and post-order traversal, level-order traversal of binary trees can also be performed. Assuming that the root node of the binary tree is at 1 layer, the layer order traversal is to start from the root node of the binary tree where it is located, first visit the root node of the first layer, then visit the nodes on the second layer from left to right, and then the third The nodes of the layer, and so on, the process of visiting the nodes of the tree layer by layer from top to bottom and from left to right is layer order traversal.

So how to implement layer order traversal?

We use queues to implement hierarchical traversal. First, when the tree is not empty, we will join the queue with the root node. Note! ! Here we enqueue the root node, not the value of the root node, so why enqueue the root node? How to join the team? If the value of the root node will be enqueued, then we will not be able to find its subtree and continue to traverse. Enqueuing the entire root node is complicated, so what we put in the queue is the pointer of the node, so the type of the queue It will program the BTNode* type. According to the characteristics of the queue (first in, first out), the root node will be dequeued, and the left and right subtrees will not be empty into the queue, and the cycle will go back and forth until the complete tree is traversed. Let’s do it below:

Just operate according to the tree in the above picture:

If the tree is not empty, put 1 into the queue, then print 1 out of the queue, put 2, 4 into the queue, print 2, 4 out of the queue, and put 3, 5, 6 into the queue, then print 3, 5 , 6 out of the team to print, complete the traversal.

Code:

void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit( &q);
    //The tree is not empty, put the first one into the queue
    if (root)
    {
        QueuePush( & amp;q, root);
    }
    while (!QueueEmpty( & amp;q))
    {
        // Dequeue the elements in the queue, and then enqueue its subtree
        BTNode* front = QueueHead( &q);
        printf("%d ", front->data);
        QueuePop( &q);
        //The left subtree is not empty, join the queue
        if (front->left)
        {
            QueuePush( &q, front->left);
        }
        if (front->right)
        {
            QueuePush( &q, front->right);
        }
    }
    printf("\\
");
    QueueDestory( &q);
}

The number and height of binary tree nodes, etc.

3.1 The number of nodes in the binary tree:

For the number of nodes in the binary tree, of course, recursive thinking is also used to solve the problem, and the problem is split level by level. The nodes of the whole tree = left subtree node + right subtree node + root node.

Now we split a small tree to find the number of nodes:

The number of nodes in the small tree above = the number of left nodes of 4 + the number of right nodes of 4 + 1, that is, the number of nodes of 5 + the number of nodes of 6 + 1, the number of nodes of 5 = the number of left nodes of 5 Number + number of right nodes of 5 + 1 = 0 + 0 + 1; 6 and 5 are both leaf nodes, the same number of nodes = 0 + 0 + 1, then the number of nodes in this small tree = 1 + 1 + 1 = 3, and then this small tree will be used as the number of nodes in the right subtree of a node to calculate the number of nodes in the entire tree.

Code:

int BTreeSize(BTNode* root)
{
    //Divide and conquer management -- the whole tree = left subtree + right subtree + 1 (tree top node)
    return root == NULL ? 0 :
        BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

Function stack frame expansion diagram:

3.2 Number of binary tree leaf nodes:

What node is a leaf node? A leaf node is a node without a subtree, so how to find the number of leaf nodes? We adopt the idea of divide and conquer, for example: if the school wants to count the number of students, one principal assigns the task to two deans, the two deans assign the task to four directors, and the directors distribute the tasks to each Head teacher, the head teacher asks the head teacher to count the number of people and report back to the upper level layer by layer. The leaf node is equivalent to each student, so there is no need to + 1 when encountering “head teacher” and “dean”, but when encountering “students ” + 1 is enough.

Code:

int BTreeLeafSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->left == NULL & amp; & amp;
        root->right == NULL)
    {
        return 1;
    }
    return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

Notice! ! If possible, draw the expansion diagram of the function stack frame by yourself to deepen your understanding of binary tree recursion.

3.3 The number of nodes in the kth layer of the binary tree:

Finding the number of nodes on the k-th layer looks similar to finding the number of leaf nodes, but it is actually the case, that is, the conditions for judging nodes change, so how do we judge the nodes on the k-th layer?

As shown in the above figure, k is reduced by one for each recursive layer from the beginning of recursion. When k=1, it is the target layer number.

Code:

int BTreeLevelKSize(BTNode* root, int k)
{
    //According to the difference between the current recursive layer and the target layer, determine which layer is the kth layer
    if (root == NULL)
    {
        return 0;
    }
    if (k == 1)
    {
        return 1;
    }
    return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}

3.4 Binary tree height:

To find the height of a binary tree, one node counts as one height, but the binary tree is divided into left and right subtrees, and the height of the binary tree is the height of the highest subtree, so it is necessary to compare the heights of the left and right subtrees and take the larger one, plus the root The height of the node.

Code:

int BTreeHeight(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    int leftHeight = BTreeHeight(root->left);
    int rightHeight = BTreeHeight(root->right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

3.5 Binary tree search for a node whose value is x:

Find the node according to the value, the same idea, first search in the left tree, if you can’t find it, go to the right tree to find it. When searching, it is the address of the node returned by the x node, and then judge whether the returned pointer is empty.

Code:

BTNode* BTreeFind(BTNode* root, BTDatatype x)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->data == x)
    {
        return root;
    }

    BTNode* ret1 = BTreeFind(root->left, x);
    if (ret1)
        return ret1;
    BTNode* ret2 = BTreeFind(root->right, x);
    if (ret2);
        return ret2;
    return NULL;
}

Function stack frame expansion diagram:

3.6 Judging whether it is a complete binary tree:

How to judge whether a tree is a complete binary tree? A full binary tree can be judged according to its height and the number of nodes, while the number of nodes in a complete binary tree is uncertain and cannot be judged from this direction. However, a complete binary tree has a characteristic that the nodes are continuous, and we can solve the problem according to this direction. Traverse the complete binary tree in order, stop traversing when encountering NULL, and then check whether there is a non-NULL in the queue, if there is, it is not a complete binary tree.

Code:

bool BTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit( &q);
    if (root)
    {
        QueuePush( & amp;q, root);
    }
    
    while (!QueueEmpty( & amp;q))
    {
        BTNode* front = QueueHead( &q);
        QueuePop( &q);
        //Jump out of judgment when encountering empty space
        if (front == NULL)
        {
            break;
        }
        else
        {
            QueuePush( &q, front->left);
            QueuePush( &q, front->right);
        }
    }

    //judgment - if the following is all empty, it is a complete binary tree
    while (!QueueEmpty( & amp;q))
    {
        BTNode* front = QueueHead( &q);
        QueuePop( &q);
        if (front != NULL)
        {
            QueueDestory( &q);
            return false;
        }
    }
    QueueDestory( &q);
    return true;
}

3.7 Binary tree destruction:

As the name suggests, the destruction of the binary tree must also be implemented recursively, so in what order do we destroy the binary tree? If the preorder is used, after destroying a node, we will not be able to find its subtree nodes. It can be seen that the postorder traversal can solve this problem very well. First destroy the left and right nodes of the node and then destroy the changed node.

Code:

void BTreeDestory(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    BTreeDestory(root->left);
    BTreeDestory(root->right);
    free(root);
}

3.8 Build a binary tree according to the traversal order of the binary tree:

Or the above tree, I use 0 to represent the empty tree, and its preorder traversal array is: 1 2 3 0 0 0 4 5 0 0 6 0 0

Code:

BTNode* BTreeCreate(BTDatatype* a, int* pi)
{
    if (a[(*pi)] == 0)
    {
        (*pi) + + ;
        return NULL;
    }
    
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if (root == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    root->data = a[(*pi) + + ];
    root->left = BTreeCreate(a, pi);
    root->right = BTreeCreate(a, pi);
    //Similar with minor differences, the in-order and post-order methods remain the same -- that is, change the order of the above three codes
    return root;
}

Summary:

For the learning of binary trees, the most important point is to understand the process of recursion. You can draw more function stack frame expansion diagrams of programs to further understand the recursion of binary trees.

The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill treehome page overview 41876 people are studying systematically

1. Binary tree chain structure implementation:

The node structure of the chained binary tree:

Binary tree traversal:

2.1 Preorder traversal:

2.2 Inorder traversal:

2.3 Postorder traversal:

2.4 Layer sequence traversal:

The number and height of binary tree nodes, etc.

3.1 The number of nodes in the binary tree:

3.2 Number of binary tree leaf nodes:

3.3 The number of nodes in the kth layer of the binary tree:

3.4 Binary tree height:

3.5 Binary tree search for a node whose value is x:

3.6 Judging whether it is a complete binary tree:

3.7 Binary tree destruction:

3.8 Build a binary tree according to the traversal order of the binary tree:

Summary: