144-18 中序创建线索二叉树

同理，先序创建线索二叉树只需要将InThread中的某部分调换位置

死记硬背

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

typedef struct node{
    int data;
    struct node *lchild,*rchild;
    int lefttag,righttag; 
}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;
        T->lefttag=0;
        T->righttag=0;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

void InThread(Tree &p,Tree &pre)
{
    if(p!=NULL)
    {
        InThread(p->lchild,pre);
        if(p->lchild==NULL)
        {
            p->lchild=pre;
            p->lefttag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL)
        {
            pre->rchild=p;
            pre->righttag=1;
        }
        pre=p;
        InThread(p->rchild,pre);
    }
}

void CreateThread(Tree &T)
{
    Tree pre=NULL;
    if(T!=NULL)
    {
        InThread(T,pre);
        pre->lchild=NULL;
        pre->lefttag=1;
    }
}

int main()
{
    Tree T;
    CreateTree(T);
    CreateThread(T);
    return 0;    
}