《数据结构-C语言版：二叉树例题2》由会员分享，可在线阅读，更多相关《数据结构-C语言版：二叉树例题2（3页珍藏版）》请在金锄头文库上搜索。
1、二叉树例题二叉树例题2 已知一个具有已知一个具有n个结点的二叉树的先序序列和中序序列分别存放个结点的二叉树的先序序列和中序序列分别存放于字符指针（字符串）于字符指针（字符串）ppos和和ipos所指示的空间中（设该二叉树各所指示的空间中（设该二叉树各结点的数据值均不相同）。下面是用类程序设计语言描述的算法结点的数据值均不相同）。下面是用类程序设计语言描述的算法ctree，其功能是由一棵二叉树的先序序列和中序序列构造该二叉树。，其功能是由一棵二叉树的先序序列和中序序列构造该二叉树。 类程序设计语言描述形式：算法中，类程序设计语言描述形式：算法中，ptr指向结点的数据域用指向结点的数据域用ptr
2、.data表示，两个指针域分别用表示，两个指针域分别用ptr.lchild、ptr.rchild表示。函数表示。函数copy(s,i,len)的功能是返回字符串的功能是返回字符串s的子串，该子串是的子串，该子串是s中从第中从第i个字符个字符开始，长度为开始，长度为len的字符串。字符数组的下标从的字符串。字符数组的下标从1开始，开始， “-”为赋值为赋值号，号，nil为空指针。为空指针。databtreerchildlchildptr 假设二叉树的结点结构如图所假设二叉树的结点结构如图所示：其中，示：其中，ptr为指向二叉树结点的为指向二叉树结点的指针，指针，data是字符型数据，存放结是字符
3、型数据，存放结点值，点值，lchild和和rchild为分别指向左为分别指向左子树和右子树的指针域。函数调用子树和右子树的指针域。函数调用方式为方式为ptr-ctree(ppos,ipos,n)Algorithm ctree(ppos,ipos,n) if (1) then return (nil); else new(ptr); (2); for rpos- 1 to n do if iposrpos=ppos1 then break; k-rpos-1; pp-copy(ppos,2,k); ip-copy( (3),1,k); ptr.lchild-ctree(pp,ip,k); pp-
4、copy(ppos,rpos+1,n-1-k); ip-copy(ipos, (4),n-1-k); ptr.rchild-ctree(pp,ip,n-1-k); return (ptr); /函数返回值为指向二叉树根结点的指针函数返回值为指向二叉树根结点的指针/ppos为字符串，存放二叉树的先序序列为字符串，存放二叉树的先序序列/ ipos为字符串，存放二叉树的中序序列为字符串，存放二叉树的中序序列/n为整型，是二叉树的结点个数为整型，是二叉树的结点个数/ptr为指向二叉树结点的指针为指向二叉树结点的指针/rpos，k为整型为整型/pp，ip为字符串为字符串/(5)算法中算法中,for语句的
5、作用是找出语句的作用是找出 结结点在中序遍历序列中的位置。点在中序遍历序列中的位置。(6)如果上述算法中如果上述算法中ppos中的值为中的值为“ABDEHCFGI”，ipos中的值为中的值为“DBEHAFCIG”，则执行上述算法所构造，则执行上述算法所构造出的二叉树（出的二叉树（ptr）中叶子结点的个数为）中叶子结点的个数为 。(7)后序遍历上述二叉树，其结果序列的后序遍历上述二叉树，其结果序列的第一个和最后一个节点分别为第一个和最后一个节点分别为 。(8)根据一棵二叉树的先序遍历序列和后根据一棵二叉树的先序遍历序列和后序遍历序列序遍历序列 （选填（选填“能能”或者或者“不能不能”）唯一地确定这棵二叉树。）唯一地确定这棵二叉树。参考答案参考答案(1) n=0(2) ptr.data-ppos1(3) ipos(4) rpos+1(5) 根根(6) 4(7)DA(8)不能不能
