/*
二叉树前中后/层次遍历的递归与非递归形式
*/
//*************** void preOrder1(BinaryTreeNode* pRoot)
{
if(pRoot==NULL)
return;
cout<<pRoot->value;
if(pRoot->left!=NULL)
preOrder1(pRoot->left);
if(pRoot->right!=NULL)
preOrder1(pRoot->right);
} void preOrder2(BinaryTreeNode* pRoot)
{
stack<BinaryTreeNode*> s;
BinaryTreeNode *p=pRoot; if(pRoot==NULL)
return;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->value<<" ";
s.push(p);
p=p->left;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->right;
}
}
} void preOrder2(BinaryTreeNode* pRoot){
if(pRoot==NULL)
return;
stack<BinaryTreeNode*> s;
s.push(root);
BinaryTreeNode* p;
while(!s.empty()){
p = s.top();
cout<<p->data;//遍历根结点
s.pop();
if(p>right){
s.push(p->right); //先将右子树压栈
}
if(p->left){
s.push(p->left); //再将左子树压栈
}
}
} //***************** //中序遍历
void inOrder1(BinaryTreeNode* pRoot)
{
if(pRoot==NULL)
return; if(pRoot->left!=NULL)
inOrder1(pRoot->left);
cout<<pRoot->value;
if(pRoot->right!=NULL)
inOrder1(pRoot->right);
} void inOrder2(BinaryTreeNode* pRoot)
{
stack<BinaryTreeNode*> s;
BinaryTreeNode *p=pRoot; if(pRoot==NULL)
return;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->left;
}
if(!s.empty())
{
p=s.top();
cout<<p->value<<" ";
s.pop();
p=p->right;
}
}
} //***************** //后序遍历
void postOrder1(BinaryTreeNode* pRoot)
{
if(pRoot==NULL)
return;
postOrder1(pRoot->left);
postOrder1(pRoot->right);
cout<<pRoot->value<<" ";
} void postOrder2(BinaryTreeNode* pRoot)
{
stack<BinaryTreeNode*> s;
BinaryTreeNode *cur;
BinaryTreeNode *pre=NULL;//记录上一个输出的节点
s.push(pRoot);//根结点入栈
while(!s.empty())
{
cur=s.top();
if((cur->left==NULL&&cur->right==NULL)||(pre!=NULL&&(pre==cur->left||pre==cur->right)))
{
//左孩子和右孩子同时为空，或者当前结点的左孩子或右孩子已经遍历过了
cout<<cur->value<<" ";
s.pop();
pre=cur;
}
else
{
if(cur->right!=NULL)
s.push(cur->right);
if(cur->left!=NULL)
s.push(cur->left);
}
}
} //*****************
//层次遍历，使用队列
void PrintFromTopToBottom(BinaryTreeNode* pRoot)
{
if(pRoot == NULL)
return; deque<BinaryTreeNode *> dequeTreeNode; dequeTreeNode.push_back(pRoot);
while(dequeTreeNode.size())
{
BinaryTreeNode *pNode = dequeTreeNode.front();
dequeTreeNode.pop_front();
cout<<pNode->m_nValue<<" ";
if(pNode->m_pLeft)
dequeTreeNode.push_back(pNode->m_pLeft); if(pNode->m_pRight)
dequeTreeNode.push_back(pNode->m_pRight);
}
} //深度优先遍历～先序遍历
void dfs(BinaryTreeNode* root){
stack<BinaryTreeNode* *> nodeStack;
nodeStack.push(root);
Node *node;
while(!nodeStack.empty()){
node = nodeStack.top();
cout<<node->data;//遍历根结点
nodeStack.pop();
if(node->rchild){
nodeStack.push(node->rchild); //先将右子树压栈
}
if(node->lchild){
nodeStack.push(node->lchild); //再将左子树压栈
}
}
} //广度优先遍历～层次遍历
void bfs(BinaryTreeNode* root){
queue<BinaryTreeNode* *> nodeQueue;
nodeQueue.push(root);
Node *node;
while(!nodeQueue.empty()){
node = nodeQueue.front();
nodeQueue.pop();
cout<<node->data;//遍历根结点
if(node->lchild){
nodeQueue.push(node->lchild); //先将左子树入队
}
if(node->rchild){
nodeQueue.push(node->rchild); //再将右子树入队
}
}
}