In the previous article, I have said the recursive traversal calendar algorithm (binary tree first root (first sequence) traversal). This article mainly talks about the non -recursive algorithm of the binary tree, adopts the stack structure
Summarize the non -recursive algorithm of the first traversal.
1) Enter the stack, mainly to enter the stack first node, and then visit this node
2) WHIL
3) The right child of the IF node is true, transfer to 1) Continue to traverse, otherwise the current node will be exited and transferred to the parent node traversing 1)
First look at the algorithm that conforms to this idea:
Copy code code as follows:
INT PreordertraversenonRCURSIVEEX (Const Bitree & T, INT (*Visitnode) (Telemtype Data))
{{
if (t == null)
{{
Return -1;
}
Bitnode *pbinode = t;
Sqstack s;
Initstack (& s);
Push (& s, (selectype) t);
While (! Isstackedy (s))
{{
While (pbinode)
{{
Visitnode (pbinode-> data);
if (pbinode! = t)
{{
Push (& s, (selectype) pbinode);
}
pbinode = pbinode-> lchild;
}
if (pbinode == null)
{{
POP (& S, (Selemtype*) & Pbinode);
}
if (pbinode-> rchild == null)
{{
POP (& S, (Selemtype*) & Pbinode); // If the stack is empty at this time, there is a problem
}
pbinode = pbinode-> rchild;
}
Return 0;
}
Note: 1) The stack structure is used here, and you can see the stack stored in the order of the structure above
2) When saving the node here, what I save is the address of the pointer, that is, the address of the node, turning it into an INT storage. The pointer is used in POP, so the & pbinode is taken instead of pbinode. Why do you think about the use of pointers yourself? It is best to understand the Bitnode *pbinode; it is well understood to define it to be changed to Bitree Pbinode.
The above algorithm is actually wrong! Why? Here I checked for a long time. There was an infinite cycle appearing during the period, and there were also no shot trees on the right tree after exiting from the left tree. In the end, I modified the first While judgment condition. Why? Because if the stack is empty after the POP, but there is still the right tree tree, it will not continue. This has not been verified too much after I wrote it, and then explained it later. The example of the empty pointer is mainly when the left child tree is empty, as follows: as follows:
Copy code code as follows:
INT PreordertraversenOnRCURSIVE (Const Bitree & T, int (*Visitnode) (Telemtype Data))
{{
if (t == null)
{{
Return -1;
}
Bitnode *pbinode = t;
Sqstack s;
Initstack (& s);
Push (& s, (selectype) t);
While (! Isstackedy (s))
{{
Gettop (s, (selectype*) & pbinode);
While (pbinode)
{{
Visitnode (pbinode-> data);
pbinode = pbinode-> lchild;
Push (& s, (selectype) pbinode);
}
if (pbinode == null)
{{
POP (& S, (Selemtype*) & Pbinode);
}
if (! Isstackedy (s))
{{
POP (& S, (Selemtype*) & Pbinode);
pbinode = pbinode-> rchild;
Push (& s, (selectype) pbinode);
}
}
Return 0;
}
This is the case. First press the root node, then determine whether the left subtree is empty, and then press it into the stack if it is not empty. If the non -empty stack gets the parent node, then judge the right child, press it into the right child node, and then determine whether the left child of the right tree is empty, and continue the cycle.
There are two wastes here: one is to push into the nodes of the empty child to enter the stack, and the other is to frequently use Gettop to get the top element of the stack
Return here to see the algorithm designed first, where the null node is not pressed into the NULL pointer or the empty child, but it cannot be completely output. Here we think that it can be added when judging the stack. Whether the current node is NULL is NULL That's it, so that there will be no embarrassment that will not display the node of the right sub -tree tree, as follows: as follows:
Copy code code as follows:
// Non -recursively traversing binary tree
Int PreordertraversenonRCURSIVEEX (Const Bitree & T,
INT (*Visitnode) (Telemtype Data))
{{
if (t == null)
{{
Return -1;
}
Bitnode *pbinode = t;
Sqstack s;
Initstack (& s);
Push (& s, (selectype) t);
While (! Isstackedy (s) || pbinode) // The main modification is this sentence
{{
While (pbinode)
{{
Visitnode (pbinode-> data);
if (pbinode! = t)
{{
Push (& s, (selectype) pbinode);
}
pbinode = pbinode-> lchild;
}
if (pbinode == null)
{{
POP (& S, (Selemtype*) & Pbinode);
}
if (pbinode-> rchild == null)
{{
POP (& S, (Selemtype*) & Pbinode); // If the stack is empty at this time, there is a problem
}
pbinode = pbinode-> rchild;
}
Return 0;
}
After the first While loop is added, it is enough. The test case is similar to the binary tree. As follows, test the binary tree in the previous section:
At this time, the input data is still 12 34 0 0 78 0 0. The test results are as follows:
--- Bitree ---
Please Enter Bitree Node Data:
12
Please Enter Bitree Node Data:
34
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
78
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
0
12 34 78
This is not enough to test, look at the following binary tree
At this time, the input data should be: 12 34 24 0 0 0 0 0 0 78 37 0 0 0. The test results are as follows:
--- Bitree ---
Please Enter Bitree Node Data:
12
Please Enter Bitree Node Data:
34
Please Enter Bitree Node Data:
twenty four
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
50
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
78
Please Enter Bitree Node Data:
37
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
0
Please Enter Bitree Node Data:
0
12 34 24 50 78 37
It can be seen from the preliminary traversal that it is correct. In addition, these algorithms are not only traversed by the preface. If you want to become a medium or post -order, you only need to remove the visit in the above algorithm first, and then add it to join it. Suitable position, just fine