144-16

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

只需要找到叶子节点，然后将第一个叶子节点赋值给Head,其余的叶子结点按照顺序使用自己的右指针连接起来

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}TreeNode,*Tree;

void CreateTree(Tree &T)        //先序创建二叉树，中序后序创建和递归遍历一样，只修改位置 
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;    
    }
    else
    {
        T=(TreeNode*)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

TreeNode *Head=NULL,*r;
void List(Tree T)
{
    if(T==NULL)
        return;
    
    if(T->lchild==NULL&&T->rchild==NULL)
    {
        if(Head==NULL)
        {
            Head=T;
            r=T;    
        }
        else
        {
            r->rchild=T;
            r=T;    
        }    
    }
    
    List(T->lchild);
    List(T->rchild);    
}

void displayList(TreeNode *Head)
{
    while(Head)
    {
        printf("%d  ",Head->data);
        Head=Head->rchild;     
    }
}

int main()
{
    Tree T;
    CreateTree(T);
    List(T);
    displayList(Head);
    return 0;    
}