二叉树的非递归遍历与递归建树
void POrder(struct User* pRoot) //非递归前序调用
{
//(1)将根作为当前节点
//(2)若当前节点不为空，则打印当前节点，并将当前节点入栈;将当前节点的左儿子赋给当前节点，循环。
//(3)否则，出栈一个元素，将当前节点置为当前节点的右儿子，循环直到当前节点为NULL或者栈为空。
stack s1;
struct User *pRootTemp=pRoot; //位置指针//(1)将根作为当前节点
while(1)
{
//(2)若当前节点不为空，则打印当前节点，并将当前节点入栈;将当前节点的左儿子赋给当前节点，循环。
if (pRootTemp!=NULL)
{
printf("%s",pRootTemp->cName);
s1.push(pRootTemp);
pRootTemp=pRootTemp->pNext[0];
}
else
{
//(3)否则，出栈一个元素，将当前节点置为当前节点的右儿子，循环直到当前节点为NULL或者栈为空。
pRootTemp=s1.top();
s1.pop();
pRootTemp=pRootTemp->pNext[1];
if ((pRootTemp==NULL) && (s1.empty())) break;
}
}
}
void MOrder(struct User* pRoot) //非递归完成中序遍历
{
//(1)将根作为当前节点
//(2)若当前节点不为空，则将当前节点入栈;将当前节点的左儿子赋给当前节点，
循环。
//(3)否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。
stack s1;
struct User *pRootTemp=pRoot; //位置指针//(1)将根作为当前节点
while(1)
{
//(2)若当前节点不为空，则将当前节点入栈;将当前节点的左儿子赋给当前节点，循环。
if (pRootTemp!=NULL)
{
s1.push(pRootTemp);
pRootTemp=pRootTemp->pNext[0];
}
else
{
//(3)否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。
pRootTemp=s1.top();
s1.pop();
printf("%s ",pRootTemp->cName);
pRootTemp=pRootTemp->pNext[1];
if ((pRootTemp==NULL) && (s1.empty())) break;
}
}
}
void BOrder(struct User* pRoot) //非递归完成后序调用
{
//(1)将根作为当前节点
//(2)若当前节点不为空，则将当前节点入栈;将当前节点的左儿子赋给当前节点，循环。
//(3)否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。
//在前面算法的基础上增加二次入栈的算法
stack s1;
struct User *pRootTemp=pRoot; //位置指针//(1)将根作为当前节点
while(1)
{
//(2)若当前节点不为空，则将当前节点入栈;将当前节点的左儿子赋给当前节点，循环。
if (pRootTemp!=NULL)
{
pRootTemp->isFirst=true;//第一次
s1.push(pRootTemp);
pRootTemp=pRootTemp->pNext[0];
}
else
{
//(3)否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。
pRootTemp=s1.top();
s1.pop();
if (pRootTemp->isFirst==true)
{
pRootTemp->isFirst=false;
s1.push(pRootTemp);//入栈右边的,也叫二次入栈
pRootTemp=pRootTemp->pNext[1];
}
else
{
//第二次出现才打印
printf("%s ",pRootTemp->cName);
pRootTemp=NULL;
if ((pRootTemp==NULL) && (s1.empty())) break;
}
}
}
}
先序创建二叉树:
顺序为:A bd##e## cf###
struct User* CreateBefore() {
char ch;
ch=getchar();
struct User* root;
if(ch=='#')
return NULL;
else
{
root=new struct User;
root->cName[0]=ch;
root->cName[1]=0;
root->pNext[0]= CreateBefore ();
root->pNext[1]= CreateBefore ();
return root;
}
}
本文档为【二叉树的非递归遍历与递归建树】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483