数据结构考研分类复习真题 第六章 答案 (五)[8]

．[题目分析]本题静态链表中结点是按动态二叉链表的前序遍历顺序存放的首先对动态二叉链表的二叉树进行前序遍历填写静态链表的下标和data域再对动态二叉链表的二叉树进行层次遍历设队列Q填写静态链表的lchild域和rchild域

typedef struct node //静态链表结点结构

{ElemType data; //结点数据

int rowlchildrchild ; //下标左右子女

}component

component st[]; //st容量足够大

struct node {BiTree t; int idx; }qbt;

static int num=;

void PreOrder(BiTree bt);

// 前序遍历二叉树填写静态链表的下标和data域

{if (bt)

{st[++num]data=bt>data; st[num]row=num;

PreOrder(bt>lchild); PreOrder(bt>rchild);

} }

int Locate(ElemType x)

//在静态链表中查二叉树结点的下标

{for (i=;i<=num;i++) if (st[i]data==x) return (i);

}

void DynaToST (BiTree bt) //将二叉树的动态二叉链表结构转为静态链表结构

{int i=; //i为静态链表st的下标

if (bt!=null)

{QueueInit(Q); //Q是队列容量足够大队列元素是qbt

qbtt=bt; qbtidx=; QueueIn(Qqbt); st[]data=bt>data;

while(!QueueEmpty(Q))

{qbt=QueueOut(Q); //出队列

p=qbtt; i=qbtidx; //二叉树结点及在静态链表中的下标

if (p>lchild!=null) //若左子女存在查其在静态链表中的下标 填lchild域值

{lch=Locate(p>lchild>data)st[i]lchild=lch;

qbtt=p>lchild; qbtidx=lch; QueueIn(Qqbt); }

else st[i]lchild=; //无左子女其lchild域填

if (p>rchild!=null) //若右子女存在查其在静态链表中的下标填rchild域值

{rch=Locate(p>>rchild>data)st[i]rchild=rch;

qbtt=p>rchild; qbtidx=rch; QueueIn(Qqbt); }

else st[i]rchild=; //无左子女其lchild域填

}//while

}//结束DynaToST

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []