鱼C论坛

 找回密码
 立即注册
查看: 3488|回复: 0

数据结构与算法第49讲

[复制链接]
发表于 2014-3-5 16:02:36 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
和小甲鱼视频里打的一样一样的,就是改成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;
}



想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-22 22:45

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表