Hello
We begin to learn the sixth chapter, tree, in this lecture.
First, we define the basic terminology and
introduce the conversion of forest and tree.
Tree is the finite set of nodes,
one of which is called the root.
Below the root, other nodes are
divided into many disjoint finite sets,
which are all the subtrees of this tree.
This is recursively-defined. In data structure and algorithm,
the tree we defined is in order. That is,
the order of subtrees is very important.
An ordered tree with degree of two is not binary tree.
Because in this tree, when the first subtree is cut out,
the second node becomes first.
In binary tree, when the left node is cut out,
the right node is still the right node at right and can not
replace the left one. Let us look at the logic structure of tree.
A tree is a set of n nodes.
Beyond the set, we have a relation.
In this relation, the feature is that
the root does not have precursor.
Other nodes have an only precursor.
Then when we represent the set,
the relation is represented by ordered pairs.
This angle brackets mean that this is in order.
In the data structure, the tree is in the order from root to leaves.
So the order is from root to leaves and
we omit the arrows.
There are some terminology in tree. First is Node. In this, there are child node and parent node.
This is similar as the binary tree. In the ordered pair,
the one close to root is parent node and the one close to leave is child node.
We have also the before and after concept in sibling node.
That is, in this tree,
first second third, the neighbor are sibling nodes.
There are also branch and leave. A node without children is leave.
Otherwise it is branch node.
The root is a special branch node.
About the edge, it is an ordered pair.
From root to leave,
if there are a sequence of node,
we call it a path.
In this sequence,
they are all reasonable ordered pairs.
In the middle of this is also a path.
The nodes close to root are ancestor nodes.
Otherwise are subsequent nodes.
The degree of node is important.
In binary tree, there are only two nodes.
In a tree, the number of subtrees
mean the width of the tree.
About layers, we define the root is at the 0th layer.
The layer of other nodes is one more than its parent.
The depth is the layer of the largest one.
The height is layer plus one.
Also, the depth is the number of edges.
And height is the number of nodes.
Let us look at the represent of a tree.
A tradition one is hang upside down with root up and leave down.
Another formalized way use set
to represent the nodes and relation. Node that
this relation is in order. We can use Venn diagram.
Because the tree does, it is a hierarchical one directed acyclic graph . So then,
If you use Venn diagrams to express , we can see
the circle represent the nodes, they are nested within each other ,
not intersect. That if in this Venn diagram ,
We put the circle ranked in the same horizontal line,
Then in the middle we cut up, we put these circle into the form of brackets ,
they becomes the expression of nested parentheses .
The expression of this nested parentheses it , it actually
represent tree ,such a complex nonlinear structure, in linear.
that is the sequence. After which, we can restore the tree in a file.
We can also read such a sequence from the file,
becomes a tree structure in memory.
Recessed method is that we sometimes
Use the console to print this tree
Then we can level the tree according to the layer,
That is , the layer 0 A, and the first layer B and C.
Such layers of nested expression is very lively.
Then in the Dewey method ,
We can see that it is actually a recessed method. It is also a tree structure.
Forest and binary tree has some equivalent
Relationships. Forest it is actually 0 or a set of multiple disjoint trees.
That could also say , a tree , and if we delete the root , it becomes a forest .
If in the forest , such as this with the two trees,
Plus above a node, it becomes a forest of an only tree.
It is actually a special case of the forest.
Definitions of forest trees is 0 or a set of multiple disjoint trees ,
So it is actually a forest even if there is one tree.
Forests and binary tree can convert to each other correspondingly.
When a forest is converted into a binary tree,
the root of the first tree is the root of the binary tree.
Then the child nodes under this, the T11, T12
becomes the left subtree.
What about the rest. They are on the right and become the subtree
in this chain. Well, this is a recursive definition process.
Let's look at an example, how do we convert it.
First , let's put the
sibling node. Node that it must be brothers and not cousins
The brothers at the same layer have the same parent node .
if it on the first forest layer, we have such a virtual one
parent node , and they are also brothers. There is a line between the brothers.
And then, we remove this node,
except this connection with the first child
About the other second third and so on, we remove the line.
The third step is to tidy up a little , put it into
a formal of a normal binary tree.
Then we convert the forest into a binary tree.
In reverse, we can also convert
A binary tree into a forest. In this conversion process ,
The root of the binary tree becomes the root our first forest,
Then the left subtree
becomes the rest of the subtree , we correspondingly do the conversion.
About the right chain, we do the conversion.
We take it as the rest of the forest , and just do recursive conversion.
Let's look at an example.
That we turn this binary tree into a forest , we first
begin from one node , let us look at the first left child node,
And then, we have , except the first left child node , it would have already a connection with the node.
So right chain under the node, sets up a connection with the parent,
We associate them, like the blue line.
And then, we remove the original chain ,
that is, the original right chain.
Then we adjust it into a forest in the form of a normal one. Then this conversion is complete.
Today's lesson is here , thank you.