/*
树转换为二叉树
题目说明：建立一棵树，将其转化为二叉树，并给出该二叉树的先序遍历序列。
要求：树为任意输入，以孩子链表法存储，转换所得二叉树以二叉链表为存储结构。
*/
#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;
}
分享
