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

[题目分析] 由定义结点的平衡因子bf等于结点的左子树高度与右子树高度之差设计一遍历算法在遍历结点时求结点的左子树和右子树的高度然后得到结点的平衡因子

int Height(BiTree bt)//求二叉树bt的深度

{int hlhr;

if (bt==null) return();

else {hl=Height(bt>lchild); hr=Height(bt>rchild);

if(hl>hr) return (hl+); else return(hr+);

} }// Height

void Balance(BiTree bt)

//计算二叉树bt各结点的平衡因子

{if (bt)

{Balance(bt>lchild); //后序遍历左子树

Balance(bt>rchild); //后序遍历右子树

hl=Height(bt>lchild); hr=Height(bt>rchild);//求左右子树的高度

bt>bf=hlhr; //结点的平衡因子bf

} }//算法结束

[题目分析]本题应采用层次遍历方式若树不空则二叉树根结点入队然后当队列不空且队列长不超过n重复如下操作出队若出队元素不为空则记住其下标且将其左右子女入队列若出队元素为空当作虚结点也将其虚子女入队列为节省空间就用树T的顺序存储结构A[n]作队列队头指针front队尾指针rear元素最大下标last

void Traverse(BiTree bt int n)

// 求二叉树bt的顺序存储结构A[n]下标超过n报错给出实际的最大下标

{BiTree A[] p;

if(bt!=null)

{int front=rear=last=; A[]=bt;

while(front<=rear)

{p=A[++front]; if(p) last=front; // 出队;用last记住最后一个结点的下标

rear=*front;//计算结点（包括虚结点）左子女下标

if (p) //二叉树的实际结点

{if(rear>n) printf(%c结点无左子女); else A[rear]=p>lchild;

if(rear+>n) printf(%c结点无右子女); else A[rear+]=p>rchild;

}

else //p是虚结点

{ if(rear<=n) A[rear]=null; if(rear+<=n) A[rear+]=null; }

}// while(front<=rear)

printf(实际的最大下标是%dlast);

}//if(bt!=null) }//Traverse

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