先序遍历伪代码1：
void preOrder1(TNode *root)
{
Stack st;
while((root != NULL) || !st.empty())
{
if(root!=NULL)
{
visit(root); //先访问再入栈
st.push(root);
root = root->left;
}
else
{
root = st.pop();
root = root->right;
}
}
}
先序遍历伪代码2：
void preOrder2(TNode* root)
{
if(root != NULL)
{
Stack st;
st.push(root);
while( !st.empty() )
{
TNode* node = st.pop();
visit(node); //先访问根节点，然后根节点就不用入栈了
st.push(node->right); //先push右节点，然后是左节点
st.push(node->left); //这样上边先访问到左节点
}
}
}
先序遍历不用栈：
void preOrder3(TNode* root)
{
while(root != NULL)
{
if(!root->bVisited)
{
visit(root);
root->bVisited = true;
}
if(root->left && !root->left->bVisited)
{
root = root->left;
}
else if(root->right!=NULL && !root->right->bVisited)
{
root = root->right;
}
else
{ //回溯
root = root->parent;
}
}
}
=================中序遍历===============
中序遍历伪代码：
void inOrder1(TNode* root)
{
Stack s;
while(root != NULL || !s.empty())
{
while(root!=NULL) //找到左子树
{
s.push(root); //先入栈
root = root->left;
}
if(!s.empty())
{
root = s.pop(); //再访问
visit(root);
root = root->right; //通过下一次循环遍历右子树
}
}
中序遍历不用栈：
void inOrder3(TNode* root)
{
while(root!=NULL)
{
while(root->left!=NULL && !root->left->bVisited)
{
root = root->left;
}
if(!root->bVisited)
{
visit(root);
root->bVisited = true;
}
if(root->right!=NULL && !root->right->bVisited)
{
root = root->right;
}
else
{
root = root->parent; // 回溯
}
}
}
=================后序遍历===============
后序遍历的伪代码：
void PostOrder(TNode* root)
{
stack s;
if(root != NULL)
s.push(root);
while(!s.empty())
{
TNode* node = s.pop();
if(node->bPushed) //其左右子树都已入栈，则访问该节点
{
visit(node);
}
else
{ //左右子树尚未入栈，则依次将根节点、右节点和左节点入栈
s.push(node); // 1> root入栈
if( node->right != NULL)
{
node->right->bPushed = false; //先把左右子树设为false
s.push(node->right); // 2> 右子树入栈
}
if( node->left != NULL)
{
node->left->bPushed = false; //先把左右子树设为false
s.push(node->left); // 3> 左子树入栈
}
node->bPushed = true; // 左右子树都已入栈，根节点可以访问了
}
}
}
=================层序遍历===============
分层遍历伪代码：
void levelOrder(TNode* root)
{
Queue Q;
Q.push(root);
while(!Q.empty())
{
TNode* node = Q.front();
visit(node);
if( node->left != NULL)
{
Q.push(node->left);
}
if(node->right != NULL)
{
Q.push(node->right);
}
}
}
《