Hello everyone. In this lecture of Data Structure and Algorithm,
we’re going to learn
the abstract data types and algorithms related to depth-first search in binary tree
When we discuss on the abstract data types,
we always discuss on the logical structures and operations,
but don’t consider how to store the data. We have definitions on
2 abstract data types of the whole tree and its nodes. For the whole tree, we define the methods of initialization and merge. For the nodes, we define its
left subtree, right subtree and father node, and the method of accessing the information of the node itself.
At first, we’re going to see the definition of ADT of the nodes of binary tree.
Here is some information of
the data domain of the node, and some related information of its left subtree and right one. Sometimes,
we may have some modification on the data domain and its left and right subtrees.
For the whole tree, the most important method is to
access the root node of the tree.
And we sometimes may define some methods to modify and find its father node and sibling nodes.
And methods to get the pre-order, in-order and
post-order traversal, and traversal related to breadth-first search.
Traversing the binary tree,
is in fact accessing the nodes in the data structure systematically. It’s preferred that
we only access every node only once. It’s in fact a process to linearize
the nodes of binary tree. We’ll have some applications over linearization.
We can save the tree in external memory after linearization.
There are mainly 3 algorithms belongs to traversal algorithm
related to depth-first search, i.e. pre-order, in-order and post-order traversal
In these 3 traversal algorithms, it is required that
we should access left subtree systematically first, and then right subtree. The difference among them is
when the root node is accessed.
For such a binary tree, its pre-order traversal sequence is
A, B, D, E, G, C, F,
H, I. And its in-order traversal sequence is
D, B, G, E, A, C, H,
F, I. And its post-order traversal sequence is D, G, E,
B, H, I, F, C, A.
For a binary expression tree, we can also get pre-order, in-order and post-order
traversal sequence, the pre-order and post-order sequence match prefix and
postfix expression respectively. They preserve information on the original order of calculation of the expression.
As for the sequence of in-order, it changes
the order of calculations with out brackets。It is not equal to the original expression binary tree.
That’s why we don’t call it infix expression. We should add some brackets to form a infix expression.
The recursion process of depth-first search to traverse
is very easy. If the current node is not null,
we will traverse its left and right subtrees recursively.
And the difference is when the node itself is accessed.
If the node is accessed before the two recursions, we’ll call it pre-order.
If the node is accessed between the two recursions, we’ll call it in-order. If the node is accessed
after the two recursions, we’ll call it post-order. The 3 access points
are useful in some applications. For the expression binary tree mentioned before,
if we want to get correct form of infix expression with brackets,
we should do some more operations at these 3 access points.
We need add left and right bracket, and of course we should determine the priority first.
Let us think that in these 3 traversal forms
which forms we can use to recover the structure of the binary tree?
Here is some concrete examples about traverse the binary tree by depth-first search.
The recursive algorithm is very concise. And we’re going to introduce non-recursive algorithm now.
As we mentioned before in simulate a recursion using a stack, we can
understand the principle in compiled stack, understand deeply
the process of recursion, and understand in some application environment
we can’t use recursion due to the limit of resources.
We will give 3 non-recursive algorithm related to the recursive version.
And we’ll have deeper understand in the binary tree.
First, we’re going to learn the algorithm of pre-order traversal.
For pre-order traversal, we’ll access a node when we see it.
Then, we’ll enter its left subtree, so we only need to save information related to its right child.
So we see the node, save its right node, and enter the left node.
We repeat the process over and over again until we can’t enter the left.
Then we pop a node from the stack
to continue the process before. For example, we pop the node C,
it retained its right node F, and enter its left node E.
By continuing this process, we make a correct
pre-order traversal sequence. It’s very simple.
Then we’re going to see the framework of the algorithm.
First, we assigned the root node to the current node.
Then we push a lookout, i.e. a null pointer, to the bottom of the stack.
Pushing a lookout to the stack makes the algorithm more unified,
We access the information of the current node if it’s not null.
Moreover, if its right child is not null,
we push the right node to the stack.
And then if the right child is not null,
we set the current node to
its left child. Otherwise, its left child
is null. Then we get a node from the stack to continue our process.
When at last the current node is null, that is
the lookout is popped, then the algorithm is over.
The feature of in-order traversal is that we can’t access a node immediately we meet it.
Therefore, we should retain it in the stack, for we should wait
until all the nodes in the left subtree is accessed before we access the node itself, and then enter the right subtree.
Therefore, we consistently push the left child in the stack and enter the left
until enter a node without left child such as D.
Therefore, we can access the node itself, and
we should have entered its right child, but it is null, so we back to B, and then back to A.
As for A, we can see that its right child is not null, and C
is pushed to the stack. And repeat the process before
until all the nodes are correctly accessed.
We can conclude the conception of in-order traversal is
pushing the node to the stack immediately we meet a node, and traverse the left subtree. After traverse the left subtree,
we pop the node from the stack and access it.
And then, we continue accessing the right subtree of the node
following the process mentioned before. Now, we’re going to see its framework.
We start from the root too, and the stack is empty at first.
If the stack is not empty,
or the node is not null.
At first, if the node is not null, we
push the node to the stack, and enter its left subtree.
Otherwise, the left subtree is all accessed.
At this time, we pop a element from the stack,
and then the element can be accessed, for its left subtree has been accessed.
And then we should make the pointer enter the right subtree that has been popped from the stack shortly,
and repeat the process. The access point is in the middle. We can see that
there is a access point in the front to handle
the related information about the pre-order traversal, that means if you have an application
just using the access point of in-order and pre-order traversal, you can use this framework of in-order traversal.
That is, we access the element immediately we see it,
this is the front access point. The non-recursive version of post-order traversal is more complex.
For we should access its left and right subtrees first, and then we can access the current node.
Thus, we should set a flag to determine whether we come from left or right.
It is like using a stack to handle
the recursive algorithm we mentioned before, we should save the return address when we convert the algorithm to non-recursive version.
Then we’re going to see the process of access of post-order traversal.
When we access the current node and push the node to the stack, we should determine
whether the node is entered from left or right. Recall the in-order traversal, we enter the left subtree immediately we see the node,
and for the right subtree, we enter it after we come back from left.
We get the node from the stack and drop it and only save its right child. However, for
post-order traversal, it’s different. We should save to the stack that we entered its left subtree and consistently enter the left.
We we comes to node D, we should see that whether we can enter the right.
Then we can access D itself after we access its left and right subtrees.
And likely, we should access the left and right subtrees and then
we can access node B it self. And then we have accessed all the nodes in the left subtree of node A.
At this time, we can get current node from the stack.
And we saved to the stack that we’re going to enter its right subtree,
and we enter the the left tree likely.
Then we access it. After we have accessed both left and right subtrees of C,
we can access the node C itself.
After we access node C, we can access A.
Because the left and right subtrees of A are all accessed.
In this process, we can see some pushes and pops of nodes are superfluous.
For example, both the left and right subtrees of D are null.
So the push and pop of D are superfluous. We can do some optimization
for it. However, if we consider it as a mechanical process
Then we can see in the non-recursive post-order traversal algorithm
we should pay more attention to the stack.
Its contents are the pointers of current nodes
with a return address showing whether it’s from left or right.
In this algorithm, we start from the root,
And, we test whether the stack is empty, i.e. whether the current node is null.
If the stack isn’t empty or the current node isn’t null,
we can enter the left over and over again and push the nodes to the stack.
And we make a tag that we have come from the left.
When we can’t enter the left, that is the left child is null,
We pop a element from the stack and examine the
its tag. If it has come from the left, we modify it to the right,
and push it back to the stack. Thus, we can’t access the node until we come from the right.
Otherwise, if we come from the right, that means we have access all the nodes of its left and right subtrees, we can access the current node.
And we notice that, we set the pointer to null,
then we back to the beginning of the loop to check.
If the stack isn’t empty, for the pointer is null,
we’ll continue to pop the stack. In fact, if we come from the right,
we can continuously pop the stack. The time complexities of these traversal algorithms
are all O(n), because for every node,
we just access it once. In fact we can calculate the complexity by
the times of the node is pushed and popped to the stack. For the post-order, every node
is pushed and popped to the stack from the left and right once, so the complexity is O(n).
The pre-order and in-order is even simpler. Some nodes are not pushed or popped
to the stack. So the time complexities are O(n) too.
As for the space complexity, it is related to the capacity of the stack, and the capacity is related to the height of the tree.
In the worst case, the tree is linear, then the complexities are O(n).
In the best case, we know that the depth of the binary in the best case is
log(n), so the complexities are O(log(n)) as well.
Think about following questions. In non-recursive version of traversal,
what are mainly pushed to the stack? Especially in post-order traversal.
What are the properties of the contents in the stack?
And how about the versatility of algorithm frameworks of pre-order, in-order and
post-order traversals? Think more about the non-recursive version.
How can we modify the algorithm to show the function of
the access point? That is, where is the access point of these 3 traversals? Thank you all!