Shulou(Shulou.com)05/31 Report--

In this article, the editor introduces in detail "what is the chain storage structure of C language binary tree". The content is detailed, the steps are clear, and the details are handled properly. I hope this article "how the chain storage structure of C language binary tree is" can help you solve your doubts.

The linked storage structure of binary tree means that a binary tree is represented by a linked list, that is, a linked list is used to indicate the logical relationship between elements. The linked storage structure of binary tree usually has two storage forms: binary linked list and trigeminal linked list.

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

The linked storage structure of a binary tree is to use 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 forms of storage:

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 storage addresses of the left and right children of the node.

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

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

Fig. 1 schematic diagram of ordinary binary tree

As shown in figure 1, this is a common binary tree. If it is stored in a chain, 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. Therefore, the chained storage structure corresponding to figure 1 is shown in figure 2:

Fig. 2 schematic diagram of binary tree chain storage structure

As can be seen from figure 2, when a chain storage binary tree is used, its node structure is composed of three parts (as shown in figure 3):

Pointer to the left child node (Lchild)

Data stored by the node (data)

Pointer to the right child node (Rchild)

Fig. 3 binary tree node structure

The C language code that represents the node structure is:

Typedef struct BiTNode {TElemType data;// data field struct BiTNode * lchild,*rchild;// around child pointer struct BiTNode * parent;} BiTNode,*BiTree

The C language code corresponding to the chained storage structure in figure 2 is:

# include # include # define TElemType inttypedef struct BiTNode {TElemType data;// data field struct BiTNode* lchild,*rchild;// around child pointer} 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;}

The output result of the program:

four

In fact, the chain storage structure of binary tree is much more than that shown in figure 2. For example, in some real scenarios, you might do the "find the parent of a node" operation, and you can add another pointer field to the node structure for each node to point to its parent, as shown in figure 4:

Fig. 4 chained storage structure of custom binary tree

Such a linked list structure is often called a trigeminal linked list.

Using the trigeminal 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 the binary tree can get twice the result with half the effort.

After reading this, the article "what is the chain storage structure of C language binary tree" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it before you can understand it. If you want to know more about related articles, welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.