【正确答案】正确答案：算法的基本设计思想：叶子结点只有在遍历中才能知道。使用中序递归遍历，设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rehild指针指向它，最后叶子结点的rchild为空。算法的代码： LinkList head，pre=NULL； ／／全局变量 LinkList InOrder(BiTree bt){ ／／中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head if(bt) { InOrder(bt一>lchiid)； ／／中序遍历左子树 if(bt一>lchild==NULL＆＆bt一>rchild==NULL) ／／叶子结点 if(pre==NULL) { ／／处理第一个叶子结点 head=bt； pre=bt； } e1Se f ／／将叶子结点链入链表 pre一>rchiid=bt; pre=bt; } InOrder(bt一>rchiid)； ／／中序遍历右子树 pre一>rchild=NULL； ／／设置链表尾 } return head； }／／InOrder 时间复杂度为0(n)，辅助变量使用head和pre，栈空间复杂度为0(n)。