1．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。【华南师范大学 1999 六、2 （13分）】

　　【参考答案】

　　[题目分析]叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。

　　LinkedList head,pre=null; //全局变量

　　LinkedList InOrder(BiTree bt)

　　//中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head

　　{if(bt){InOrder(bt->lchild); //中序遍历左子树

　　if(bt->lchild==null && bt->rchild==null) //叶子结点

　　if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点

　　else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表

　　InOrder(bt->rchild); //中序遍历左子树

　　pre->rchild=null; //设置链表尾

　　}

　　return(head); } //InOrder

　　时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)