What is the linked storage structure of a binary tree?

The linked storage structure of a binary tree refers to using a linked list to represent a binary tree, that is, using a linked list to indicate the logical relationship between elements. The linked storage structure of a binary tree usually has two storage forms: binary linked list and triplet linked list.

The operating environment of this tutorial: windows7 system, c99 version, Dell G3 computer.

The linked storage structure of a binary tree uses a linked list to represent a binary tree, that is, a linked list is used to indicate the logical relationship between elements. There are usually two storage forms:

• Each node in the linked list consists of three fields. In addition to the data field, there are also two pointer fields, which are used to give the The storage addresses of the node's left child and right child.

• Each node in the linked list consists of four fields. In addition to the data field, there are also three pointer fields, which are used to give the left child and right child of the node. and the storage address where the parent node is located.

Linked storage structure of binary tree (detailed explanation in C language)

Figure 1 Normal Schematic diagram of a binary tree

As shown in Figure 1, this is an ordinary binary tree. If it is stored in a linked list, you only need to start from the root node of the tree and store each node and its left and right children using a linked list. That’s it. Therefore, the chain storage structure corresponding to Figure 1 is shown in Figure 2:

Figure 2 Schematic diagram of chained storage structure of binary tree

It can be seen from Figure 2 that when chained storage of binary trees is used, the node structure consists of 3 parts (as shown in Figure 3):

• Pointer to the left child node (Lchild);

• The data stored in the node (data);

• Pointer to the right child node Pointer (Rchild);

Figure 3 Binary tree node structure

The C language code indicating the node structure is:

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    struct BiTNode *parent;
}BiTNode,*BiTree;

The C language code corresponding to the chain storage structure in Figure 2 is:

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("%d",Tree->lchild->lchild->data);
    return 0;
}

Program output result:

4

In fact, the chain storage structure of the binary tree is far more than the one shown in Figure 2. For example, in some actual scenarios, the operation of "finding the parent node of a node" may be performed. In this case, a pointer field can be added to the node structure for each node to point to its parent node, as shown in Figure 4. ：

## Figure 4 The linked storage structure of a custom binary tree

Such a linked list structure is usually called a triple linked list.

Using the three-way linked list shown in Figure 4, we can easily find the parent node of each node. Therefore, when solving practical problems, using a suitable linked list structure to store binary trees can achieve twice the result with half the effort.

Related recommendations: "

C Language Video Tutorial"

The above is the detailed content of What is the linked storage structure of a binary tree?. For more information, please follow other related articles on the PHP Chinese website!