數據結構考研分類復習真題 第六章 答案 (五)[28]

　　[題目分析]此樹看作度為的有序樹先將根結點入隊列當隊列不空重復以下動作結點出隊若結點有兩個子女先將第二（右）子女入隊列並轉向第一子女若結點有一個子女則入隊列如此下去直到碰到葉子結點或只有一個子女的結點再重復上述動作直至隊列為空定義樹結構如下

　　typedef struct node
　　{ElemType data; struct node *firstchild *secondchild; }*Tree;
　　void TreeTravers(Tree t)  //按字母順序輸出樹中各結點的值
　　{Tree pQ[];              //Q為隊列元素是樹結點指針容量是夠大
　　if (t)
　　{QueueInit(Q); QueueIn(Qt); //根結點入隊
　　while(!QueueEmpty(Q))
　　{p=QueueOut(Q);             //出隊
　　while (p>firstchild && p>secondchild)      //當有雙子女時
　　{QueueIn(Qp>secondchild);printf(p>data);//訪問結點
　　p=p>firstchild;}// 沿第一子女向下
　　if (p>firstchild){printf(p>data); QueueIn(Qp>firstchild)} //一個子女樹入隊
　　if (!p>firstchild && !p>secondchild) printf(p>data);//訪問葉子結點
　　}//while(!QueueEmpty(Q))
　　}//if
　　}//算法結束

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23706.html