#ifndef _HEAD_
#define _HEAD_

#include <queue>
#include <iostream>
using namespace std;

typedef char TElemType;
typedef int Status;
#define OK 0
#define ERROR -2
#define OverFlow -1

//普通二叉树
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//线索二叉树
typedef enum {Link, Thread} PointerTag;

typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;

//仅为普通二叉树
void CreateBiTree(BiTree &T);
void PreOrderTraverse(BiTree T);
void LevelTraverse(BiTree T);

//线索二叉树
void CreateBiThrTree(BiThrTree &T);
Status InOrderThread_Head(BiThrTree &head, BiThrTree &T);
Status InOrderTraverse_Thr(BiThrTree T);

#endif

#include "Header.h"

//因为BiTree是一个结构体，所以这里必须用“引用&”，否则将会新建一个空的BiTree，导致在创建二叉树时，创建失败（我们指定的BiTree为空）；
//进而导致后面的遍历直接退出（因为传进去的BiTree不管是否为“引用&”都为空）；
//另外只要创建的树正确，那么在遍历的时候不论是否“引用&”都可以得到正确的遍历顺序

//创建二叉树：过程理解为先序
void CreateBiTree(BiTree &T)
{
    TElemType ch;
    cin >> ch;
    if (ch == ‘#‘)
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        if (T == NULL)
        {
            cout << "Create BinaryTree failed!";
            exit(OverFlow);
        }
        T->data =http://www.mamicode.com/ ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

//先序遍历
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    cout << T->data;
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

//深度优先遍历

//广度优先遍历

//层次遍历
void LevelTraverse(BiTree T)
{
    BiTree temp;
    queue<BiTree>q;
    q.push(T);
    do
    {
        temp = q.front();
        cout << temp->data;
        q.pop();
        if (temp->lchild != NULL)
        {
            q.push(temp->lchild);
        }
        if (temp->rchild != NULL)
        {
            q.push(temp->rchild);
        }
    } while (!q.empty());
}

//前面是二叉树，下面是线索二叉树
BiThrTree pre;

void CreateBiThrTree(BiThrTree &T)
{
    TElemType ch;
    cin >> ch;
    if (ch == ‘#‘)
        T = NULL;
    else
    {
        T = (BiThrTree)malloc(sizeof(BiThrNode));
        if (T == NULL)
        {
            cout << "Create BinaryTree failed!";
            exit(OverFlow);
        }
        T->data =http://www.mamicode.com/ ch;
        CreateBiThrTree(T->lchild);
        CreateBiThrTree(T->rchild);
    }
}

void InThreading(BiThrTree &p)    //p：present
{
    if (p)
    {
        InThreading(p->lchild);
        if (p->lchild != NULL)
        {
            p->LTag = Thread;
            p->lchild = pre;
        }
        if (pre->rchild != NULL)
        {
            pre->RTag = Thread;
            pre->rchild = p;
        }
        pre = p;
        InThreading(p->rchild);
    }
}

//建立头结点，中序线索二叉树本来的其与结点
Status InOrderThread_Head(BiThrTree &head, BiThrTree &T)
{
    if (head == NULL)
    {
        return ERROR;
    }

    head->rchild = head;
    head->RTag = Link;

    if (T == NULL)      //如果为NULL
    {
        head->lchild = head;
        head->LTag = Link;
    }
    else
    {
        pre = head;
        head->lchild = T;        //第一步
        head->LTag = Link;
        InThreading(T);         //找到最后一个结点
        pre->rchild = head;        //第四步
        pre->RTag = Thread;
        head->rchild = pre;      //第二步
    }
    return OK;
}

Status InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;
    p = T->lchild;
    while (p != T)
    {
        while (p->LTag == Link)
            p = p->lchild;
        cout << p->data;
        while (p->RTag == Thread && p->rchild != T)
        {
            p = p->rchild;
            cout << p->data;
        }
        p = p->rchild;
    }
    return OK;
}

#include "Header.h"

int main()
{
    int choice;
    cout << "1：普通二叉树" << endl << "2：线索二叉树" << endl;
    cin >> choice;
    switch (choice)
    {
    case 1:
        BiTree binaryTree;
        CreateBiTree(binaryTree);
        PreOrderTraverse(binaryTree);
        cout << endl;
        LevelTraverse(binaryTree);
        cout << endl;
        break;
    case 2:
        //必须用一个新的函数，新建一个树，因为数据结构已被改变——>然后建立头节点（就像链表），
        //并随即线索化——>像链表一样遍历（相对于普通树的遍历，减少了递归的堆栈导致的返回次数）
        BiThrTree threadBinaryTree;
        CreateBiThrTree(threadBinaryTree);
        BiThrTree head = (BiThrTree)malloc(sizeof(BiThrNode));
        InOrderThread_Head(head, threadBinaryTree);
        InOrderTraverse_Thr(head);
        cout << endl;
        break;
    }
    return 0;
}