Hello everyone , in this lecture of data structures and algorithms , we introduce the final content of Chapter VI
Sequential storage structure of tree and K -tree ,
There are many sequential storage methods of trees.
What is the point of sequential storage method?
In fact, the tree
is a dynamic and complex data structures in the memory.
If we need to put it to the external memory to store up
And, later to restore the memory inside, and do some calculation that we must make these nodes serialized,.
About the sequence operation, we first
would consider / i, which traversal methods we have, it is a sequence when traversing the tree.
However , a simple traversal is not sufficient to restore the tree.
Let us have a look at the root first traversal methods, because it is the root first traverse,
if a node has
left child , the left child will right follow
this node , so we only need to express it with the ltag information
And its rlink is more complex
Because it may appear far away.
Then we have ltag and rlink information
Which is able to completely express the tree structure,
Of course, we also need to save its domain of "info"
Let us have a look with rlink and ltag information , how do we restore the tree
Suppose that I have saved the information in an array.
This is the corresponding array , each of the subscript of corresponding node information
First, we can "new" the corresponding pointer in the memory
for these nodes.
After that,
I also put then into a corresponding array of pointers, of course , I can also
create a parallel array , and then I read here
the rlink and ltag information. According to this information,
I easily restore its structure, e.g. , the node C , the
/ i, rlink
is D, then , this ltag shows that it has a left child node
The following one E, is its left child , then we just build in this way.
According to this approach, we establish this information in order.
Finally, we form the structure of a binary chain corresponding to such an equivalence
declaration expression,
then we see that this information earlier , in fact, is
some redundancy , that this redundancy is in rlink,
Then can we also let it be an indication tag bit, / i,
0,1 , can express, because in this rlink, ltag information
If there is a tree structure expressed by / i, a binary chain in memory
and I want you to lead it to external memory, you have to
obtain this information rlink and to write a relatively complex
code , that if I need only the rtag information
In other words, if there is a child , it was 0 , if no children , is a
If that happens, you only need a simple preorder traversal
and put the whole information to the external memory. Let us look at this structure
iii is a statement.
It corresponds to the form of a binary chain , then it is quite convenient for us to export its
ltag and rtag, I'll directly get this information in the root first traversal.
Then we now want from rtag, ltag
to restore the tree. About the operation for us to restore this tree, first of all, we
/ i, for one node , that, if its rtag is equal to 0 , it means that it has
right child , where the right child is, for now I do not know. So I just put it into the stack
and we continue to deal. When we encounter / i this
node boundary , there is no left child node , that is, it does not have
Left child , then the following Key, because it is not someone else's left child
It should be linked to the binary chain structure, it must be a right brother of a certain node.
So who is it the right brother of. We pop an element from the top of the stack,
then it is the right brother of j, and we hang it on.
Well, then , we'll continue to deal with it ,
Similarly , these several elements of iii are also right brothers of others
So, we pop from the top of the stack, iii, the corresponding elements up in turn, then, put the node to hang to its right brother, we ,remember this position,it also
has no right brother, and no left child. For D,
it must be a right brother of others, and we find C from the top of the stack ,
Then this node is right brother of C , we hang D up.
Then we continue this treatment in turn, finish, and then we get
the equivalent structure of a , iii, forest
Then we look at the root first recover of this iii with double labeled
Algorithm that first ,
the double labeled node information is saved in an array. Every element of the array has an info domain as well as ltag, rtag. That we first
new a pointer that it is ready to become root
node, and then , we , for this array of information , scan sequentially
Because I 've got ead
the address of this node , that I just hang this "point" domain up to its "info"
Then , I decide whether its rtag is 0.
If so, which means that it has a right brother, I'll put it into the stack.
Otherwise , let's put this right brother as empty, then we prepare for the next one
If the ltag of the node itself is equal to 0,
That is , it has left child , then the next node
is just that current node 's left child. Then we hang the pre-prepared information for this node up
Otherwise , the , iii, node's
left child is empty , the node behind it is
a right brother for a certain node.
Who is it right brother of, this information is retained in the stack , we pop an element from the stack
Then , mount, and we continue to circulate , we should pay attention to
Well, because we actually in the beginning , already apply position for a node
and then, we in the cycle every time assign for this position
so in the algorithm ,
the final node is in fact not processed,
We must note that it need a separate deal , and that
Its left child and right child is empty , its value is the one at the final position of our entire array
Correspondingly,
we take a look at , the layer representation with double labeled
we can express it only with ltag and rtag.
We look at such a layer representation sequence with double labeled,
give you this layer sequence / i, rtag, / i, ltag
you look very faint and do not know, this is what kind of structure ,
Since it is a layer sequence, we need to use such a queue , as auxiliary
again, we follow left to right , the order of the sequence to scan
What if this node , / i, says it has ltag, which means / i
has left child , then we put it into
the queue inside , / i, we wait behind
until the left child node appears and then mount it , but if it says
, / I, rtag equal to 0, that is, it has
right brother, at this layer sequence, the next one is its immediate right brother , we can hang
Well, when one node
, it says it 's , the right brother is 1, it means
the next node is not its right brother, who it is
then it is clearly the left child node of the front one, / i,
because we have to put these nodes attached to the Internal data structures represented by the binary chain
that a node , he must either be someone else's left child , or someone else's right brother.
That is to say , if it is not someone else's right brother, it is clearly one node's left
child, so we can use this principle, / i, to continue,
internal processing , so we get
the internal structure of such a tree represented by the binary chain
it corresponds to the statement of , / i, at right side
, / i, with a layer sequence with double labeled,
It is similar as the construction of root first sequence with double labeled
The difference firstly is , / i,
use the queue , and then , from this on , they are really very similar
First of all, we prepare a root , then, we , / i, for this
hierarchical sequence with double labeled, / i, conduct a scan , of course , we only scan
N-1 times , / i, then, we can know that this first is the root
Information. We set , / i, this node , this information field as
the beginning one, / i, and then we see , / i, a
certain node , / i, which is to say if it 's ltag
, is equal to 0 , then say, it has left child , then we put it
into the queue, otherwise, we set its left child empty
then we prepare for the next node , then we
/ i, look at this node , / i, its rtag is not equal to 0,
If it is, it is equal to 0 , then this
node prepared just now can be set as its right sibling
Otherwise, that is to say , it does not have the right brother,
Then we set its right brother as empty, and then, we have to be responsible for the next prepared node
that is , the next node is not a right brother of others.
That it must be someone else's left child , we find the first element
from the queue just now, then, we set this new node as
the left child of the one just got out of the queue,
Then the pointer is , / i, and then , / i, down
to this node that we have just prepared and continue the cycle operation earlier ,
Well, finally, we will have to deal with, / i, the last node separately
/ i, its left child , / i, right sibling , are set
empty , and its value is the value of last element of the sequence
/ i, we also have a root last sequence with a degree.
In the representation of root last,
this node , / i, is visited according to the order of root last.
And then, we store the node , their
degree , and that this expression is very complete. Let us see how do we
make the root last sequence with a degree into a tree.
When we visit each node, we take the degree into account.
/ i, if the degree is 0 , I can directly put it into the stack.
Because the root traversal is a , / i,
LIFO structure, that is, depth first search structure, which uses the stack as the intermediate data structures.
Well, when we encounter E, the
element , / i, it says it has three child nodes , so its degree is 3, then we pop 3 elements from the stack.
It should be noted that when pop the elements,
pay attention to , / i, the order , i.e. , that one first in is the left most
child node and then , / i, the one final in is , / i, the right most child node
/ i, after we combine it into a subtree,
put the E node into the stack again, we continue to deal. When we encounter this
C , another three elements are needed to pop out. Then the C itself , / i, need to be pushed in.
X and I, both have a degree of 0,
Therefore , / i, when we encounter D , its degree is 2. From this
/ i, stack we take two elements, then a new subtree is built. Note that
after the treatment of stack is over, it may still have several
nodes, it means the roots of the whole forest.
In different storage expressions,
for some storage expressions, you may need to go through these roots,
and in other expressions , / i, for example ,
the full binary tree with labeled, that is, we need to mark
about which nodes are internal nodes , which nodes are
leaf nodes , / i. You can go back and think about it , this information is very complete. With this information we can
restore such a tree structure or a forest well.
, if / i, the corresponding structure of such a binary chain is not a
, / I, full binary tree , that is to say, some nodes may have a
child node, in this case , we can fulfill this empty place.
That is , in the form of fake full binary tree, that is , like
node B , its , / i, left child is empty , then an
empty mark added. At last, leave you a thinking
question, that is , , in these sequence expression, what about the redundancy information?
in addition , there are a lot of
methods of sequence expression, you can think about, for example , the root first with a degree, as well as the layer sequence with a degree.
There is an important issue,
that is, the binary tree is also a dynamic structure, and if we want to save it into
the external memory, and I want to serialize such complex dynamic structure, of course, we
also corresponds to all kinds of traversal methods, and similar with the forest , / i, you
can also design sequence methods for binary tree, / i.
But it should be noted that semantics is slightly different.
Then , we'll introduce the K-tree.
It is actually very similar to the binary tree, that is to say,
The left and right of a binary tree is needed for strict distinction, if you see left as the first child and right as second.
In the K-tree , it is also very strict
about the distinction between the several children, of course , the number here is iii, from 0 to K-1
Well, for these kids, if someone empty , nothing else can replace its position.
In fact, in the K-tree , each node has a complete
K pointer domains, when a domain is empty, others are not able to replace it.
Then you have to leave it empty.
Well, similarly , iii, full K-tree
Also, the complete K-tree , / i, the associated definitions, of course ,
K-tree also has some applications that you can go to think about it. Thank you