数据�l�构�W�六章算法设计题[8]_跨考网

1�Q?/span> 以孩子兄弟链表�ؓ存储�l�构�Q�请设计递归和非递归���法求树的深度。【北方交通大�?/span>1999�?/span>(18�?/span>)�?/span>

　　【参考答案�?/span>

　　[题目分析]由孩子兄弟链表表�C�的树，求高度的递归模型是：若树为空�Q�高度�ؓ�Ӟ��若第一子女为空�Q�高度�ؓ1和兄弟子树的高度的大者；否则�Q�高度�ؓ�W�一子女树高度加1和兄弟子树高度的大者。其非递归���法使用队列�Q�逐层遍历树，取得树的高度�?/span>

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

　　{int hc,hs;

　　if (bt==null) return (0);

　　else if (!bt->firstchild) return (1+height(bt->nextsibling);//子女�I�，查兄弟的深度

　　else // �l�点既有�W�一子女又有兄弟�Q�高度取子女高度+1和兄弟子树高度的大�?/span>

　　{hc=height(bt->firstchild)�Q?/span> //�W�一子女树高

　　hs=height(bt->nextsibling)�Q?/span>//兄弟树高

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

　　}

　　}//�l�束height

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

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

　　else{int front=1,rear=1; //front,rear是队头队���օ�素的指针

　　int last=1,h=0; //last指向树中同层�l�点中最后一个结点，h是树的高�?/span>

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

　　while(front<=last)

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

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

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

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

　　}

　　if(front>last) //本层�l�束�Q�深度加1�Q�初始深度�ؓ0�Q?/span>

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

　　}//while(front<=last)

　　}//else

　　}//Height