数据结构-树-通过前序遍历与中序遍历创建二叉树
一.算法思想关于通过前序遍历与中序遍历来创建二叉树,相信大家都用手工的方法推出来过,所以这里的算法思想就略过了。二.源代码BiTreeNode CreateBt(ElementType A[],ElementType B[],int PreL,int PreR,int InL,int InR) {//A,B两个数组存放前序和中序遍历的结果,且数组下标从1开始//PreL,PreR,InL,InR分
·
一.算法思想
关于通过前序遍历与中序遍历来创建二叉树,相信大家都用手工的方法推出来过,所以这里的算法思想就略过了。
二.源代码
BiTreeNode CreateBt(ElementType A[],ElementType B[],int PreL,int PreR,int InL,int InR) {
//A,B两个数组存放前序和中序遍历的结果,且数组下标从1开始
//PreL,PreR,InL,InR分别为前序,中序的第一个以及最后一个结点下标
BiTreeNode BT;
BT = new BiTreeStruct; //建立根节点
BT->data = A[PreL]; int i,llen, rlen;
for (i = InL; B[i] != BT->data; i++);//找到根节点在中序数组中的序号
llen =i-InL; //左子树长度
rlen =InR-i; //右子树长度
//根据序号划分,根节点的左子树及右子树
if (llen) //递归建立左子树
BT->Lchild = CreateBt(A, B, PreL + 1, PreL + llen, InL, InL + llen - 1);
else
BT->Lchild = NULL; //左子树为空
if(rlen) //递归建立右子树
BT->Rightchild = CreateBt(A, B, PreR-rlen,PreR,InR-rlen+1,InR);
else
BT->Rightchild = NULL; //右子树为空
return BT; //返回根节点
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献1条内容
所有评论(0)