二叉树创建及遍历算法

作者佚名技术来源程序设计浏览发布时间 2012-06-29

历右子树*/
　}
}
/*
　二叉树后序遍历函数dlast_Order_Access()<递归算法>
　参数描述：
　 BTNode *head: 二叉树的根节点指针
*/
void dlast_Order_Access(BTNode *head)
{
　if(head!=NULL)
　{
　 dlast_Order_Access(head->lchild); /*递归遍历左子树*/
　 dlast_Order_Access(head->rchild); /*递归遍历右子树*/
　 if(SHOWCHAR)
　　 printf("%c　　　 ",head->data);
　 else
　　 printf("%d　　　 ",head->data);
　}
}
//------------------------------递归部分------------------------------
//------------------------------非递归部分------------------------------
/*
　二叉树前序遍历函数pre_Order_Access()<非递归算法>
　参数描述：
　 BTNode *head: 二叉树的根节点指针
*/
void pre_Order_Access(BTNode *head)
{
　BTNode *pt;
　ABTStack *ps,*top;
　pt = head;
　top = NULL;
　printf("\n二叉树的前序遍历结果<非递归>：\t");
　while(pt!=NULL ||top!=NULL)　 /*二叉树未遍历完,或堆栈非空*/
　{
　 while(pt!=NULL)
　 {
　　 if(SHOWCHAR)
　　　 printf("%c　　　 ",pt->data);　 /*访问根节点*/
　　 else
　　　 printf("%d　　　 ",pt->data);　 /*访问根节点*/
　　 ps = (ABTStack *)malloc(sizeof(ABTStack));　 /*根节点进栈*/
　　 ps->ptree = pt;
　　 ps->link = top;
　　 top = ps;
　　 pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
　 }
　 if(top!=NULL)
　 {
　　 pt = top->ptree; /*栈顶节点出栈*/
　　 ps = top;
　　 top = top->link;
　　 free(ps); /*释放栈顶节点空间*/
　　 pt = pt->rchild; /*遍历节点右子树*/
　 }
　}
}
/*
　二叉树中序遍历函数mid_Order_Access()<非递归算法>
　参数描述：
　 BTNode *head: 二叉树的根节点指针
*/
void mid_Order_Access(BTNode *head)
{
　BTNode *pt;
　ABTStack *ps,*top;
　int counter =1;
　pt = head;
　top = NULL;
　printf("\n二叉树的中序遍历结果<非递归>：\t");
　while(pt!=NULL ||top!=NULL)　 /*二叉树未遍历完,或堆栈非空*/
　{
　 while(pt!=NULL)
　 {
　　 ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
　　 ps->ptree = pt;
　　 ps->link = top;
　　 top = ps;
　　 pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
　 }
　 if(top!=NULL)
　 {
　　 pt = top->ptree; /*栈顶节点出栈*/
　　 ps = top;
　　 top = top->link;
　　 free(ps); /*释放栈顶节点空间*/
　　 if(SHOWCHAR)
　　　 printf("%c　　　 ",pt->data); /*访问根节点*/
　　 else
　　　 printf("%d　　　 ",pt->data); /*访问根节点*/
　　 pt = pt->rchild; /*遍历节点右子树*/
　 }
　}
}
/*
　二叉树后序遍历函数last_Order_Access()<非递归算法>
　参数描述：
　 BTNode *head: 二叉树的根节点指针
*/
void last_Order_Access(BTNode *head)
{
　BTNode *pt;
　ABTStack *ps,*top;
　int counter =1;
　pt = head;
　top = NULL;
　printf("\n二叉树的后序遍历结果<非递归>：\t");
　while(pt!=NULL ||top!=NULL)　 /*二叉树未遍历完,或堆栈非空*/
　{
　 while(pt!=NULL)
　 {
　　 ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
　　 ps->ptree = pt;
　　 ps->link = top;
　　 top = ps;
　　 pt = pt->lchild; /*遍历节点右子树,经过的节点依次

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!

分享到：更多

你可能对下面的文章感兴趣

上一篇: 获取GetLastError返回信息下一篇: 如何在C++中集成Lua脚本(LuaPlus篇)

关于二叉树创建及遍历算法的所有评论

随机推荐