Hello everyone , this lecture of data structure and algorithm is Chapter 6: tree.
We introduce the abstract data type of tree today, and traverse the tree.
After describing the logical structure of the tree,
We express its abstract data types, mainly through a template.
Tree is similar as the binary tree ,
we have to define the class of node and the class of the whole tree.
In the class of node, particularly important is the function of LeftMostChild and the RightSibling function .
This LeftMostChild means this node is the first child of my current node.
In the representation of the binary chain,
It is the first of left nodes, so we call it left most child.
And RightSibling is my current node's right brother.
in fact, in the representation of binary chain,
it is my next sibling node , we have a common parent node .
Others are some of our regular expression .
In abstract data type of tree, we particularly pay attention to the function of parent.
About this function, in fact, under normal circumstances we can not directly get the parent of a node , because we really only save from a node , its left most child, as well as its right sibling.
What if I want to find a parent, we need some algorithms , we will be back on .
The other is the operation of traverse.
Then we look at traversal operations.
It is similar to a binary tree , we have the root first sequence.
This sequence is in fact equivalent to the pre-order traversal of a binary tree.
Then I would travel this subtree.
In the first subtree, I'm starting from the root
And then, I will traverse its first subtree , and the rest subtrees.
After traversing the first tree, we'll traverse the rest of the other trees .
The root last sequence is like root first. This process has a similar depth first search, but then it would not visit the root before all the subtrees are finished.
Then we look at , traversing forests and the corresponding binary tree traversal .
First root was just said. It is similar to the preorder of binary tree.
Root last traversal is actually similar to the in order of the binary sequence .
Do we have a method of root in middle? We actually do not.
Because for a tree, it has several child nodes , we do not know from where we start to visit the root after the left subtrees.
then the rest of right the subtrees.
In some special applications, if you have the need for it,
You can also define your own traversal of the root in middle.
Then we look at the root first traversal algorithms.
Our algorithm is that we first visit the root node.
And then, we recursively visit its first subtree ,
which is the entire subtree represented by the left most child,
because in this structure of the binary chain left most child and its right sibling is directly to string together , so we went down to the left most child,
then the whole information of these several subtrees has been expressed.
Then we complete their first tree root and its corresponding sub-tree.
We dropped down to this tree , it 's right sibling. That is, the next subtree, and then ,
Then go to the next level of the cycle , it is just repeat the process. Then reenter next subtree.
We, in this order, complete the forest.
Then we look at the root last depth first search algorithm.
We must first go down to its subtree represented by the left most child.
Then, access can be recursive . After the visit is over , let's visit the root .
Then we dropped down to the right sibling, which is the second sub-trees
Repeat the process again ,
then we go to the third sub-trees, and repeat the process until the deal is completed.
Then we look at this width first search .
It is also known as a hierarchy traversal.
That we first visit the zero layer and then the first layer, and then visit the other layers until the last layer.
Then we see the traversal of the width first search.
In this representation, we are top to bottom, layer after layer.
Inside the corresponding binary chain, in fact, we can see the form of wire ,
In this way , to express.
To pay attention to is such an order.
Then we see the algorithm of width first search.
We start from the root ,
We put all roots of these sub-trees into a queue.
Because we are width first , in the form of a FIFO , the queue is used as the intermediate data structure.
When the queue is not empty, we pop an element from the head of the queue , then, we visit this element.
Then we enter the left child node of this element.
After left child node, here is along the left child of its right sibling of this chain , we come to visit .
After we visit, all the child nodes of the left and right as well as its sibling chain itself are put into the queue.
Here , we note in particular in the form of binary chain, we have such a structure that we start with a node , then it falls to the left child node .
Then along the right chain , this is the child of the node,
so when we look for the child nodes , it is also such a structure.
When we talk about storage implementation, we will introduce such an algorithm to find the parent node
using the L-shaped structure of such a turning point .
Then finally leave you something to think about .
That is, can we use the binary tree preorder traversal framework to write the root first traversal of the forest ?
Can we use a binary tree in order traversal framework to write its root last traversal?
Also how to write the framework of non-recursive depth first traversal of the forest.
There we look at these perspectives of width first search.
Then we just said , width first search, we corresponds to such a forest , we are layers come.
It corresponds to the form of binary chain, is this slash
Then we can not also use such a width first search form of a binary tree.
So from top to bottom , left to right, one to come, meaning that it is completely not the forest.
Well, this talk is all, thank you