将二叉树的叶节点从左到右的顺序连成一个单链表

设计一个算法将二叉树的叶节点按从左到右的顺序连成一个单链表，表头指针为head，二叉树按二叉链表方式存储，链接时用叶节点的右指针域来存放单链表指针。

思想：从左到右可以用中序遍历来实现。设置表头节点和指向前驱结点指针pre，初始均为空。第一个叶节点由指针head指向，遍历到叶节点时，将pre的右指针指向该叶节点，并更新pre指针。最后一个叶节点的pre的右指针为空。

代码：

LinkList head=NULL,pre=NULL;
LinkList InOrder(BiTree T){if(T!=NULL){InOrder(T->lchild);//中序遍历左子树 if(T->lchild==NULL&&T-rchild==NULL){if(pre==NULL){head=T;T=pre;}else{pre->rchild=T;T=pre;}} InOrder(T->rchild);//中序遍历右子树 pre->rchild=NULL}
}