二叉树创建及遍历算法

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

<编程思想>:
　首先,在前序遍历序列中的首元素是二叉树的根节点,接着
　,在中序遍历序列中找到此节点,那么在此节点以前的节点必为
　其左孩子节点,以后的必为其右孩子节点;
　然后,在中序遍历序列中,根节点的左子树和右子树再分别
　对应子树前序遍历序列的首字符确定子树的根节点,再由中序
　遍历序列中根节点的位置分别确定构成它们的左子树和右子树
　的节点;
　依次类推,确定二叉树的全部节点,构造出二叉树.
　参数描述：
　 char *pre:　前序遍历序列
　 char *mid:　中序遍历序列
　 int n:　　遍历序列中节点个数
　返回值:
　 dCreateBranchTree3 = 新建二叉树的根节点指针
*/
BTNode *dCreateBranchTree3(char *pre,char *mid,int n)
{
　BTNode *p;
　char *t;
　int left;
　if(n<=0)
　 return(NULL);
　p = (BTNode *)malloc(sizeof(BTNode));
　p->data = *pre;
　for(t=mid;t<mid+n;t++)
　 if(*t==*pre) break;　 /*在中序遍历序列中查找根节点*/
　left = t - mid;　 /*左子树的节点个数*/
　p->lchild = dCreateBranchTree3(pre+1,t,left);
　p->rchild = dCreateBranchTree3(pre+1+left,t+1,n-1-left);
　return(p);
}
/*
　二叉树创建函数CreateBranchTree()<非递归算法>
　参数描述：
　 int array[]: 二叉树节点数据域数组
　 int n:　　二叉树节点个数
　返回值:
　 CreateBranchTree = 新建二叉树的根节点指针
*/
BTNode *CreateBranchTree(int array[][2],int n)
{
　BTNode *head,*p;
　BTNode *NodeAddr[MAXNODE]; //节点地址临时缓冲区
　int i,norder,rorder;
　head = NULL;
　printf("二叉树原始数据<新建顺序>：\t");
　for(i=1;i<=n;i++)
　{
　 p = (BTNode *)malloc(sizeof(BTNode));
　 if(p==NULL)
　 {
　　 printf("\n新建节点时内存溢出！\n");
　　 return(NULL);
　 }
　 else
　 {
　　 p->data = array[i][0];
　　 p->lchild = p->rchild = NULL;
　　 norder = array[i][1];
　　 NodeAddr[norder] = p;
　　 if(norder>1)
　　 {
　　　 rorder = norder / 2; /*非根节点:挂接在自己的父节点上*/
　　　 if(norder % 2 == 0)
　　　　 NodeAddr[rorder]->lchild = p;
　　　 else
　　　　 NodeAddr[rorder]->rchild = p;
　　 }
　　 else
　　　 head = p; /*根节点*/
　　 if(SHOWCHAR)
　　　 printf("%c　　　 ",p->data);
　　 else
　　　 printf("%d　　　 ",p->data);
　 }
　}
　return(head);
}
//------------------------------递归部分------------------------------
/*
　二叉树前序遍历函数dpre_Order_Access()<递归算法>
　参数描述：
　 BTNode *head: 二叉树的根节点指针
*/
void dpre_Order_Access(BTNode *head)
{
　if(head!=NULL)
　{
　 if(SHOWCHAR)
　　 printf("%c　　　 ",head->data);
　 else
　　 printf("%d　　　 ",head->data);
　 dpre_Order_Access(head->lchild); /*递归遍历左子树*/
　 dpre_Order_Access(head->rchild); /*递归遍历右子树*/
　}
}
/*
　二叉树中序遍历函数dmid_Order_Access()<递归算法>
　参数描述：
　 BTNode *head: 二叉树的根节点指针
*/
void dmid_Order_Access(BTNode *head)
{
　if(head!=NULL)
　{
　 dmid_Order_Access(head->lchild); /*递归遍历左子树*/
　 if(SHOWCHAR)
　　 printf("%c　　　 ",head->data);
　 else
　　 printf("%d　　　 ",head->data);
　 dmid_Order_Access(head->rchild); /*递归遍

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

分享到：更多

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

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

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

随机推荐