资源描述：
《确定二叉树实习报告1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实习二树、图及其应用 ——唯一地确定一棵二叉树一．需求分析【问题描述】如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。【基本要求】已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法：（1）构造一棵二叉树；（2）证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。【测试数据】前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC二．设计1.设计思想（1）存储结构顺序存储（2）主要算法基本思想a用两个一维数组A和B分别存放前序和
2、中序序列。b算法基本思想：①将前序和中序序列分别读入数组A和B。②根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的所有元素一定在左子树中，其余元素则在右子树中。所以，首先从数组A中取出第一个元素A[0]作根结点，然后在数组B中找到A[0]，以它为界，在其前面的是左子树中序序列，在其后面的是右子树中序序列。③若左子树不为空，沿前序序列向后移动，找到左子树根结点，转②。④左子树构造完毕后，若右子树不为空，沿前序序列向后移动，找到右子树根结点，转②。⑤前序序列中各元素取完则二叉树构造完毕。⑥对二叉树进行前序和中序遍历，并
3、将结果分别与数组A和B进行比较，若相同，则证明二叉树构造正确。主要算法：voidVisit(charitem)//输出显示函数设计{printf("%c",item);}voidCreateTree(BiTNode*T,intA_f,intA_l,intB_f,intB_l,charA[],charB[])//根据前序和后序创建二叉树{intinterval=0;//中序遍历数组的第一个下标intsame=B_f;/*same为计数器，用来确定根节点的位置，初始化为中序的起始地址*/if(A[A_f]!=B[same]){while
4、(A[A_f]!=B[same])//在中序序列中找到根节点{same++;interval++;//数组下标自增}}if((interval==0)&&(A_f==A_l))//找到了叶节点，也是递归出口{T->data=A[A_f];//确定根节点T->LeftChild=NULL;//根结点的左孩子制空T->RightChild=NULL;//根结点的右孩子制空}if((interval!=0)&&(intervalLeftChild=(BiTNode*)malloc(si
5、zeof(BiTNode));/*申请左子树根结点的内存*/T->RightChild=(BiTNode*)malloc(sizeof(BiTNode));/*申请右子树根结点的内存*/T->data=A[A_f];CreateTree(T->LeftChild,A_f+1,A_f+interval,B_f,B_f+interval-1,A,B);/*递归调用createtree函数，创建根结点的左子树*/CreateTree(T->RightChild,A_f+1,interval+1,A_l,B_f+interval+1,B_l
6、,A,B);/*递归调用createtree函数，创建根结点的右子树*/}if((interval!=0)&&(interval==A_l-pre_f))//只有左子树没有右子树{T->LeftChild=(BiTNode*)malloc(sizeof(BiTNode));/*申请左子树根结点的内存*/T->data=A[A_f];CreateTree(T->LeftChild,A_f+1,A_l,B_f,B_f+interval-1,A,B);/*递归调用createtree函数，创建根结点的左子树*/T->RightChild=
7、NULL;}if((interval==0)&&(A_f!=pre_l))//只有右子树没有左子树{T->RightChild=(BiTNode*)malloc(sizeof(BiTNode));/*申请右子树根结点的内存*/T->data=A[A_f];T->LeftChild=NULL;CreateTree(T->RightChild,A_f+interval+1,A_l,B_f+interval+1,B_l,A,B);/*递归调用createtree函数，创建根结点的右子树*/}}2.设计表示（1）函数调用关系图Main->I
8、nitiate(&T)->CreateTree(T,0,Pre_len-1,0,In_len-1,A,B)->PrintBiTree(T,0)->PreOrder(T,Visit)->InOrder(T,Visit)->PostOrd
