“This is the 17th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”.

preface

No more nonsense, data structure must learn! I will update a chapter every day. If I can’t finish one, I will divide it into two chapters

6.3 Storage Structure of a tree

When it comes to storage structures, sequential storage and chain storage come to mind.

Let’s take a look at the sequential storage structure, which uses a sequence of contiguous storage cells to store the data elements of a linear table. That’s natural for a linear list, but what about a tree with multiple pairs?

A simple sequential storage structure is not sufficient for tree implementation.

​

6.3.1 Parental representation

Every node, it doesn’t have to have children, but it does have one and only one parent.

We assume that the nodes of a tree are stored in a set of contiguous Spaces, and that in each node there is an indicator indicating where its parents are placed in the linked list. In other words, every node knows not only who it is, but also where its parents are.

Data is a data domain, which stores data information of nodes. Parent is a pointer field that stores the subscripts of the node’s parents in an array.

The code says

/* Tree parent representation node structure definition */
#define MAX TREE SIZE 100
typedef int TElemType; 	/* Data type of the tree node, currently tentatively integer */
typedef struct PTNode/* Node structure */ {
    TElemType data;	/* Node data */
	int parent;	/* Parent position */
} PTNode ;

typedef	struct/* Tree structure */ {
	PTNode nodes[MAX_TREE SIZE]; /* Node array */
	int r,n;	/* Root position and number of nodes */
} PTree;
Copy the code

With this structure definition, we can implement the parental representation. Since the root node has no parents, we have agreed to set the root location field to -1, which means that all of our nodes have their parents’ locations.

In such a storage structure, we can easily find the parent node according to the parent pointer of the node, and the time complexity is O(1). When the parent is -1, it means that the root of the tree node is found. But if we want to know what the child of the node is, sorry, just walk through the structure.

We just need to make a little improvement, add a field of the node’s leftmost child, let’s call it the firstborn field, so that we can easily get the node’s child. If there are no children, the firstborn field is set to -1

For nodes with zero or one child, this structure solves the problem of finding children. Even if you have two children, you know who the first son is, and the second son is of course. Another problem scenario, we care a lot about the relationship between brothers, and the parent representation doesn’t show this relationship, so what do we do? Well, you can add a right sibling field to indicate fraternity, which means that every node if it has a right sibling, records the index of that right sibling. Similarly, if the right brother does not exist, the value is assigned to -1

But if the node has a lot of kids, more than two. We also care about the parent of the node, the child of the node, and the brother of the node, and the time traversal requirements are relatively high, so we can also extend this structure to have the parent domain, the eldest child domain, and the right brother domain. The design of storage structures is a very flexible process. Whether a storage structure is designed reasonably depends on whether the operation based on the storage structure is suitable, convenient, and time complexity. Note that the more is not the better, and design the corresponding structure when necessary. Just like even the most beautiful music will become bored after listening to it for thousands of times, even the most beautiful film will become bored after watching it for hundreds of times in a period of time, right?

Cow!!!!!! Read it a few times and you’ll get it!