我的线索二叉树

首先讲一下我的思路

首先就是用递归的方式建立一颗普通的二叉树，注意建树的时候把坐标志和右标标记为孩子节点

接着线索化二叉树：

　　首先新建一个节点，并把这个节点的左标志记为孩子节点，右标志记为线索，并让右边的线索指向自身

　　如果二叉树为空，那么左标志也指向自身

　　否则的话左边孩子指向要线索化的二叉树的树根，定义一个中间变量pre指向已经线索化的前一个节点,pre初始的时候指向新建的那个节点

　　然后从树根开始，用递归的方法线索花二叉树

　　　　　　　先线索化二叉树的左孩子

　　　　　　　然后线索化当前节点

　　　　　　　　　　如果当前节点的左孩子为空，那么左标志变为线索标志，左线索指向pre

　　　　　　　　　　如果pre的右孩子为空，那么pre的右标志指向当前节点，右标志变为线索标志

　　　　　　　然后把当前节点的地址赋给pre

　　此时pre指向二叉树的最后一个节点，把最后一个节点的右标志记为线索标记，并让右孩子指向新建的那个头结点，新建的那个节点的右孩子指向最后一个节点

 

接着就是遍历线索二叉树了

　　定义一个节点p指向线索二叉树的头的左孩子

　　只要p不重新指向线索二叉树的头，就一直进行下面操作

　　　　顺着p找到二叉树的最左边的节点，此时p指向这个节点

　　　　然后只要线索不断，就顺着这个节点一直往下访问，如果线索断了，那么p指向p的右孩子

　　下面是我的代码：

　　　　注意刚开始写代码的时候有几个错误：

　　　　　　1：当前节点不空才能递归访问这个节点的左孩子右孩子以及它本身，才能输出，忘了加判断if(p != NULL)

　　　　　　2:注意线索化之后的头结点就不是原来的头节点了，遍历的时候传参不要传错了

　　　　　　3：注意输出的时候是根据原来的节点对线索的记录，先找到下一个节点，然后再输出，不要写反了，

/*
    思路：
        先序建立普通的二叉树，记得建树的时候吧坐标志和右标志标记为孩子节点
        然后就是二叉树的线索化
            另外建立一个头结点，把这个头结点的左标志记为孩子节点，右标志记为线索，指向自身
            如果二叉树为空，那么左节点头的左节点为空，
            如果二叉树不为空，那么让pre指向头，找到最左端的节点，头指向这个节点
                用递归的方式把二叉树线索化
                    如果这个节点的左孩子为空，那么左孩子指向pre，坐标志为线索，
                    如果pre的右孩子为空，那么pre的右孩子指向当前节点，pre的右标志位记为线索
                    然后把pre置为当前节点
            此时pre指向二叉树的最后一个节点，把他的右标志指向新建的头，右标志即为线索，
            新建的头的右线索指向他

*/
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <iostream>
using namespace std;

typedef struct BinTNode
{
    char data;
    struct BinTNode *lchild, *rchild;
    int ltag, rtag;
}BinTNode, *BinTree;
BinTree pre;
void CreatBinTree(BinTree &p)
{
    char ch;
    scanf("%c", &ch);
    if(ch != '*')
    {
        p = (BinTree)malloc(sizeof(BinTNode));
        p->data = ch;
        p->ltag = p->rtag = 0;
        CreatBinTree(p->lchild);
        CreatBinTree(p->rchild);
    }
    else
        p = NULL;
}
void InThreading(BinTree &p)
{
    if(p != NULL)
    {
        InThreading(p->lchild);
        if(p->lchild == NULL)
        {
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre->rchild == NULL)
        {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThreading(p->rchild);
    }
}
void InOrder1(BinTree p)
{
    if(p)
    {
        InOrder1(p->lchild);
        cout << p->data;
        InOrder1(p->rchild);
    }
}
void InOrderThread(BinTree &thrt, BinTree &p)
{
    thrt = (BinTree)malloc(sizeof(BinTNode));
    thrt->ltag = 0;
    thrt->rtag = 1;
    thrt->rchild = thrt;
    if(p == NULL)
        thrt->lchild = thrt;
    else
    {
        pre = thrt;
        thrt->lchild = p;
        InThreading(p);
        pre->rchild = thrt;
        pre->rtag = 1;
        thrt->rchild = pre;
    }
}
void InOrder(BinTree root)
{
    BinTree p = root->lchild;
    while(p != root)
    {
        while(p->ltag == 0)
            p = p->lchild;
        cout << p->data;
        while(p->rtag == 1 && p->rchild != root)
        {
            p = p->rchild;//注意输出的时候是先找到线索所指向的节点，然后再输出
            cout << p->data; 
        }
        p = p->rchild;
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    BinTree root, thrt;
    CreatBinTree(root);
    InOrderThread(thrt, root);
    InOrder(thrt); //注意遍历线索二叉树的时候，头节点已经不再是原来的头节点了
    return 0;
}