題目描寫敘述

線索二叉樹概念
1．定義
　n個結點的二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結點在某種遍歷次序下的前趨和后繼結點的指針（這樣的附加的指針稱為”線索”）。

這樣的加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(Threaded BinaryTree)。依據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。
注意：
　線索鏈表攻克了二叉鏈表找左、右孩子困難的問題，出現了無法直接找到該結點在某種遍歷序列中的前趨和后繼結點的問題。

2．線索鏈表的結點結構
　線索鏈表中的結點結構為:

當中:
　ltag和rtag是添加的兩個標志域，用來區分結點的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。

以下你的任務：首先依據輸入的序列建立二叉樹，然后對二叉樹進行線索化。最后中序遍歷二叉線索樹并輸出結果。

輸入要求

輸入的第一行包括單獨的一個數字T，表示測試序列的數目；
以下每一行為一個測試序列,測試序列是按先序序列輸入字符 ,假設節點沒有左或右孩子,則輸入用空格表示,最后用一個空格結束一行的輸入。

輸出要求

相應每一個測試序列。採用中序遍歷二叉線索樹，輸出一行
假如輸入

2
ABC  DE G  F    
-+a  *b  -c  d  /e  f   

應當輸出

CBEGDFA
a+b*c-d-e/f

寫了個線索二叉樹
Code：

#include<bits/stdc++.h>
using namespace std;
typedef struct BTree
{
    char data;
    struct BTree *left,*right;
    int ltag,rtag;
}BTree;
BTree *CreatBTree()
{    
    char ch=getchar();
    if(ch==' ')
        return NULL;
    BTree *temp=(BTree *)malloc(sizeof(BTree));
    temp->data=ch;
    temp->ltag=temp->rtag=0;
    temp->left=CreatBTree();
    temp->right=CreatBTree();
    return temp;
}
void inThread(BTree *p,BTree *&pre)
{
    if(p)
    {
        inThread(p->left,pre);
        if(!p->left)
        {
            p->left=pre;
            p->ltag=1;
        }
        if(pre&&!pre->right)
        {
            pre->right=p;
            pre->rtag=1;
        }
        pre=p;
        inThread(p->right,pre);
    }
}
void CreateInThread(BTree *T)
{
    BTree *pre=NULL;
    if(T)
    {
        inThread(T,pre);
        pre->right=NULL;
        pre->rtag=1;
    }
}
BTree *first(BTree *p)
{
    while(p->ltag==0)
        p=p->left;
    return p;
}

BTree *next(BTree *p)
{
    if(p->rtag==0)
        return first(p->right);
    else
        return p->right;
}
void inOrder(BTree *T)
{
    for(BTree *p=first(T);p!=NULL;p=next(p))
        cout<<p->data;
}
void delBTree(BTree *T)
{
    BTree *pre=first(T);
    BTree *p=next(pre);
    for(;p!=NULL;pre=p,p=next(p))
        free(pre);
    free(pre);
}
int main()
{    
    int t;
    cin>>t;    
    while(t--)
    {    
        getchar();//吃掉回車    
        BTree *root=CreatBTree();
        getchar();//吃掉最后結尾的空格
        CreateInThread(root);
        inOrder(root);
        cout<<endl;
        delBTree(root);
    }
    return 0;
}