考研报名

数据结构第六章算法设计题[5]_跨考网

来源:跨考2011-11-25

1.有n个结点的完全二叉树存放在一维数组A[1..n]中,试据此建立一棵用二叉链表表示的二叉树 ,根由tree指向。 南京理工大学 1998 七、1 6分)】

  【参考答案】

  BiTree Creat(ElemType A[],int i)

  //n个结点的完全二叉树存于一维数组A中,本算法据此建立以二叉链表表示的完全二叉树

  {BiTree tree;

  if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];

  if(2*i>n) tree->lchild=nullelse tree->lchild=Creat(A,2*i)

  if(2*i+1>n) tree->rchild=nullelse tree->rchild=Creat(A,2*i+1) }

  return (tree) }//Creat

[算法讨论]初始调用时,i=1

2.已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2h-1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。【北京航空航天大学 1999 七、 (15)

  【参考答案】

  [题目分析]二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的,不是完全二叉树的二叉树顺序存储时,要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。

  typedef struct

  {BiTree bt; //二叉树结点指针

  int num; }tnode // num是结点在一维数组中的编号

  tnode Q[maxsize]; //循环队列,容量足够大

  void creat(BiTree T,ElemType BT[ ])

  //深度h的二叉树存于一维数组BT[1:2h-1]中,本算法生成该二叉树的二叉链表存储结构

  {tnode tq; //tq是队列元素

  int len=2h-1; //数组长度

  T=(BiTree)malloc(sizeof(BiNode)); //申请结点

  T->data=BT[1]; //根结点数据

  tq.bt=T; tq.num=1;

  Q[1]=tq; //根入队列

  front=0;rear=1; //循环队列头、尾指针

  while(front!=rear) //当队列不空时循环

  {front=(front+1) % maxsize ;

  tq=Q[front] ; p=tq.bt; i=tq.num ; //出队,取出结点及编号

  if (BT[2*i]==#||2*i>len) p->lchild=null; //左子树为空,‘#’表示虚结点

  else //建立左子女结点并入队列

  {p->lchild=(BiTree) malloc(sizeof(BiNode)); //申请结点空间

  p->lchildàdata=BT[2*i]; // 左子女数据

  tq.bt=p->lchild; tq.num=2*i; rear=(rear+1) % maxsize ;//计算队尾位置

  Q[rear]=tq; //左子女结点及其编号入队

  }

  if(BT[2*i+1]==#|| 2*i+1>len) p->rchild=null; //右子树为空

  else //建立右子女结点并入队列

  {p->rchild=(BiTree)malloc(sizeof (BiNode); //申请结点空间

  p->rchild->data=BT[2*i+1]; tq.bt=p->rchild; tq.num=2*i+1;

  rear=(rear+1)%maxsize; Q[rear]=tq; //计算队尾位置,右子女及其编号入队

  }

  } //while

  }//结束creat

  [算法讨论] 本题中的虚结点用‘#’表示。应根据二叉树的结点数据的类型而定。

展开全文
频道>考研报名

近期热点

相关推荐

大家都在看

2022管理类联考最基础的备考规划 你还不知道吗?

2022考研英语阅读核心词汇:食品类

2022考研英语阅读核心词汇:科普类

2022考研英语阅读核心词汇:宗教类

2022考研门类之:历史学门类考研院校排名

2022考研门类之:文学门类考研院校排名

2022考研门类之:艺术学门类考研院校排名

跨考分校

加盟