南小山 2019-07-19 00:10 采纳率: 0%
浏览 529
已结题

数据结构问题:一棵普通的树转化成二叉树,为什么输出的时候无法输出呢(是我转化没有成功吗)?

/*
树转换为二叉树
题目说明:建立一棵树,将其转化为二叉树,并给出该二叉树的先序遍历序列。
要求:树为任意输入,以孩子链表法存储,转换所得二叉树以二叉链表为存储结构。
*/ 
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_SIZE 100
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
typedef int TElemType;
typedef int Status;
#define OK 1

void visit(TElemType e) 
{
    printf("%d", e);
}

typedef struct CTNode
{
    //孩子结点
    int child;
    struct CTNode *next;
}*ChildPtr;

typedef struct  
{
    TElemType data;//结点值
    ChildPtr firstchild; //孩子链表头指针
               //可增设一个双亲的域,能方便地找到其双亲。int Parent;
}CTBox;

typedef struct 
{
    CTBox nodes[MAX_TREE_SIZE];  //建立顺序表头结构
    int n, r;  //结点数和根的位置 
}CTree;

typedef struct BTNode
{
    int data;
    CTBox list[MAX_TREE_SIZE]; 
    struct BTNode *lchild;
    struct BTNode *rchild;//兄弟结点
}BTNode;

typedef struct
{
    CTBox list[MAX_TREE_SIZE];//邻接表表头
    int n;//结点个数
}Tree;//定义树


//--------------树的孩子链表存储表示-------------------

Status CreateTree(CTree &T)
{
    //构建一棵树
    int i;
    printf("请输入结点数及根结点的位置下标:\n");
    scanf("%d %d",&T.n, &T.r);
    printf("请输入各节点的值\n");
    for(i = 0; i < T.n; ++i)
    {
        scanf("%d",&T.nodes[i].data);
        T.nodes[i].firstchild = NULL;
    }
    printf("创建每个结点的孩子结点...\n");
    system("pause");
    for(i =0; i < T.n; ++i)
    {
        printf("请输入位置为%d的结点的孩子个数(>=0)(有孩子则输入孩子们的位置,无则输入0):\n",i);
        int nChild=0;
        scanf("%d",&nChild);
        ChildPtr p=NULL;  //p指向插入孩子位置的前一个位置
        ChildPtr q=NULL;  //q用于提示即将插入的新b孩子链表结点
        for(int j = 0; j < nChild; ++j)
        {
            q= (ChildPtr)malloc(sizeof(struct CTNode));//为孩子的位置开辟一个空间   
            if(!q)
                exit(OVERFLOW);
            scanf("%d",&(q->child));  //将孩子链表结点置入位置值
            q->next = NULL;
            if(j == 0)//将孩子链表头结点指向孩子链表第一个结点
            {
                T.nodes[i].firstchild = q;
            }
            else
            {
                p->next = q;
            }
            p = q;  
        }
    }
    return OK;
}


Status PrintChild(const ChildPtr &C)
{//打印出结点的孩子
    if(C)
    {
        ChildPtr p;
        p = C;
        while(p)
        {
            printf("[%d| ] ->",p->child);
            p = p->next;
        }
        printf("^");
        //return TRUE;
    }
    else
    {
        printf("^");
        //return FALSE;
    }

}
void PrintChildTree(const CTree &T)//输出树的结点及他们的孩子
{
    printf("\n位置%d为树的根%d\n\n", T.r, T.nodes[T.r].data);
    for(int i = 0; i < T.n; ++i)
    {
        printf("位置%d,结点值[%d| ] ->", i, T.nodes[i].data);
        PrintChild(T.nodes[i].firstchild);
        printf("\n");

    }   printf("---建立树成功----"); 
}

//--------------树转化为二叉树-------------- 
?
void treeToBtree(Tree *t,BTNode *bt,int i)
{//树转二叉树
    if(t != NULL)
    {
        CTBox *p = &(t->list[i]);
        bt->list[i]= t->list[i];//二叉树的头结点等于树的头结点
        ChildPtr b = p->firstchild;//该结点的孩子结点
        BTNode *q = bt->lchild;//二叉树的左孩子结点
        while(b)//把该层的树全部转为二叉树
        {
            treeToBtree(t,q,b->child);//若该结点以及该结点的子孙结点转为二叉树
            b = b->next;//指向树结点下一个孩子结点
            q = q->rchild;//指向二叉树的右孩子结点
        }
    }
}

void PrintAsTree(BTNode *T,int i) //显示转化结果 
{
    int cnt;
    if (T!=NULL) 
    {
        printf("转化后的二叉树:"); 
        for (cnt=1; cnt<i; cnt++) 
        //visit(T->data);
        printf("\n");
        printf("位置%d,结点值[%d| ] ->", cnt, T->data);
        PrintAsTree(T->lchild, i+1); //遍历左孩子 
        PrintAsTree(T->rchild, i);   //遍历右孩子 
    }
}

//---------------二叉树的先序遍历---------------- 
void PreOrder(BTNode *T)
{
    if(T==NULL)
        return;
    else
    {
        printf("二叉树的先序遍历结果为:"); 
        printf("%d--",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}


int main() 
{
    CTree T;
    Tree *Y;
    BTNode *bt;
    ChildPtr C;
    int i;
    i=T.n;
    CreateTree(T);
    PrintChildTree(T);//输出普通树的结点值 
    PrintChild(C);    //输出各结点的孩子结点值 
    treeToBtree(Y,bt,i);//树转化为二叉树 
    PrintAsTree(bt,i);//输出转化后的二叉树
    PreOrder(bt);    //输出二叉树的先序遍历序列 
    return 0;
}



  • 写回答

1条回答 默认 最新

  • 关注
    评论

报告相同问题?

悬赏问题

  • ¥20 有关区间dp的问题求解
  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
  • ¥15 对于相关问题的求解与代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
  • ¥15 保护模式-系统加载-段寄存器
  • ¥15 电脑桌面设定一个区域禁止鼠标操作
  • ¥15 求NPF226060磁芯的详细资料