struct?BTNode_s{????int?value;????
????????????????????????????????BTNode_s*?pLeft;???
?????????????????????????????BTNode_s*?pRight;}BTNode;?
?//非遞歸?前序
void?preOrder(BTNode?*?pRoot){
? ??????????if(pRoot?!=NULL){
? ??????????????????return;
? ? ? ? ? ?}
????BTNode*?p?=?pRoot;
????std::stack?treeStack;
? ??while(p?!=NULL?||?!treeStack.empty()){
? ??????????????while(p?!=NULL) ? {
????????????????????printf("%d\t", p->value);
????????????????????????????treeStack(p);
????????????????????????????p=?p->pLeft;
????????????????}
? ? ? ? ? ??if(!treeStack.empty()） ? {
????????????????????????p=?treeStack.top();
????????????????????????treeStack.pop();
????????????????????????p=?p->pRight;
? ? ? ? ? ? ? }
????}
}
//非遞歸?中序
void?inOrder(BTNode*?pRoot)
{
if(pRoot?==NULL)
????{
? ? ? ? ?retrun;
????}
BTNode*?p?=?pRoot;
std::stack?treeStack;
while(p?!=NULL?||?!treeStack.empty())?{
? ??????while(p?!=NULL){
????????????treeStack.push(p);
????????????p=?p->pLeft;
????????}
if(!treeStack.empty()) {
p=?treeStack.top();
printf("%d\t", p->value);
????????????treeStack.pop();
p=?p->pRight;
????????}
????}
}????
//非遞歸?后序
void?postOrder(BTNode*?pRoot)
{
if(pRoot?==NULL)
return;
std::stack?treeStack;
std::stack<int>nodeState;
BTNode*?p?=?pRoot;
while(p?!=NULL)
????{
????????treeStack.push(p);
nodeState.push(0);
p=?p->pLeft;
????}
while(!treeStack.empty())
????{
p=?treeStack.top();
while(p->pRight!=?NULL?&&nodeState.top()?==?0)
????????{
????????????nodeState.pop();
nodeState.push(1);
p=?p->pRight;
while(p?!=NULL)
????????????{
????????????????treeStack.push(p);
nodeState.push(0);
p=?p->pLeft;
????????????}
p=?treeStack.top();
????????}
p=?treeStack.top();
printf("%d\t", p->value);
????????treeStack.pop();
????????nodeState.pop();
????}
}
