数据结构与算法第49讲

小干

和小甲鱼视频里打的一样一样的，就是改成c++了，为什么输入字符后就是没输出，快哭了！！！
谁知道到底哪里出问题了？？？


#include <iostream>
#include <string>

using namespace std;

//线索存储标志位
//link(0):表示指向左右孩子的指针
//thread(1):表示指向前去后继的线索
typedef enum
{
        link, thread
} pointerNag;

typedef struct tree
{
        char data;
        struct tree *lchild, *rchild;
        pointerNag ltag;
        pointerNag rtag;
} Node, *Tree;

//全局变量，始终指向刚刚访问过的结点
Tree pre;

//创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreateTree(Tree *T)
{
        char c;
       
        cin >> c;
        if(' '==c)
        {
                *T = NULL;
        }
        else
        {
                *T = (tree*) new tree;
                (*T)->data = c;
                (*T)->ltag = link;
                (*T)->rtag = link;
               
                CreateTree(&(*T)->lchild);
                CreateTree(&(*T)->rchild);
        }
}

//中序遍历线索花
void InThreading(Tree T)
{
        if(T)
        {
                InThreading(T->lchild);//递归左孩子线索化
               
                //结点处理
                if(!T->lchild)//如果该结点没有左孩子，设置ltag为thread，并把lchild指向刚刚访问的结点
                {
                        T->ltag = thread;
                        T->lchild = pre;//指向前驱
                }
               
                if(!pre->rchild)
                {
                        pre->rtag = thread;
                        pre->rchild = T;
                }
               
                pre = T;
               
                InThreading(T->rchild);//递归右孩子线索化
        }
}

void InOrderThreading(Tree *p, Tree T)
{
        *p = (tree*) new tree;
        (*p)->ltag = link;
        (*p)->rtag = thread;
        (*p)->rchild = *p;
       
        if(!T)
        {
                (*p)->lchild = *p;
        }
       
        else
        {
                (*p)->lchild = T;
                pre = *p;
               
                InThreading(T);
               
                pre->rchild = *p;
                pre->rtag = thread;
                (*p)->rchild = pre;
        }
}

void visit(char c)
{
        cout << c;
}

//中序遍历二叉树，非递归
void InOrderTraverse(Tree T)
{
        Tree p;
        p = T->lchild;
         
        while(p!=T)
        {
                while(p->ltag == link)
                {
                         p = p->lchild;
                }
                visit(p->data);
               
                while(p->rtag == thread && p->rchild!=T)
                {
                        p = p->rchild;
                        visit(p->data);
                }
               
                p = p->rchild;
        }
}

int main()
{
        Tree P, T = NULL;
       
        CreateTree(&T);
       
        InOrderThreading(&P,T);
       
        cout << "中序遍历输出结果为：" << endl;
       
        InOrderTraverse(P);
       
        cout << endl;
       
        return 0;
}