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

．[题目分析]由孩子兄弟链表表示的树求高度的递归模型是若树为空高度为零若第一子女为空高度为和兄弟子树的高度的大者否则高度为第一子女树高度加和兄弟子树高度的大者其非递归算法使用队列逐层遍历树取得树的高度

int Height(CSTree bt) //递归求以孩子兄弟链表表示的树的深度

{int hchs;

if (bt==null) return ();

else if (!bt>firstchild) return (+height(bt>nextsibling);//子女空查兄弟的深度

else // 结点既有第一子女又有兄弟高度取子女高度+和兄弟子树高度的大者

{hc=height(bt>firstchild) //第一子女树高

hs=height(bt>nextsibling)//兄弟树高

if(hc+>hs)return(hc+); else return (hs);

}

}//结束height

int height(CSTree t) //非递归遍历求以孩子兄弟链表表示的树的深度

{if(t==null) return();

else{int front=rear=; //frontrear是队头队尾元素的指针

int last=h=; //last指向树中同层结点中最后一个结点h是树的高度

Q[rear]=t; //Q是以树中结点为元素的队列

while(front<=last)

{t=Q[front++]; //队头出列

while(t!=null) //层次遍历

{if (t>firstchild) Q[++rear]=t>firstchild; //第一子女入队

t=t>nextsibling; //同层兄弟指针后移

}

if(front>last) //本层结束深度加（初始深度为）

{h++;last=rear;} //last再移到指向当前层最右一个结点

}//while(front<=last)

}//else

}//Height

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