面試100 12從上向下遍歷二叉樹

從上向下遍歷二叉樹

問題描述：
      該題要求，從根節點開始向下遍歷樹，且同層之間從左向右一次遍歷。
分析：
      這一題目實質上，就是樹的廣度遍歷。因為樹實質上是一種特殊的圖。
代碼如下：

#include <iostream>

#include <queue>

using namespace std ;

template <class T>

struct BinaryTree{

T data ;

BinaryTree * lc ;

BinaryTree * rc ;

} ;

BinaryTree <int> * root ;

const int N = 7 ;

template <class T>

void buildTree(T x) //正規的二叉查找樹

{

if(root == 0)

{

root = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;

root->lc = 0 ;

root->rc = 0 ;

root->data = x ;

return ;

}

BinaryTree <T> * p = root ;

BinaryTree <T> * q = root ;

while(p)

{

q = p ;

if(p->data <= x)

p = p->rc ;

else

p = p->lc ;

}

p = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;

p->data = x ;

p->lc = 0 ;

p->rc = 0 ;

if(q->data > x)

q->lc = p ;

else

q->rc = p ;

}

template <class T>

void postOrder(BinaryTree <T> * p)

{

if(p)

{

cout<<p->data<<" " ;

postOrder(p->lc) ;

postOrder(p->rc) ;

}

//template <class T>//使用廣度優先遍歷算法獲取

void bfs(BinaryTree <int> * p , queue <BinaryTree<int> *> Q)

{

while(!Q.empty())

{

BinaryTree <int> * tops = Q.front() ; //取頭部

cout<<tops->data<<" ";

Q.pop() ;

if(tops->lc)

Q.push(tops->lc) ;

if(tops->rc)

Q.push(tops->rc) ;

}

int main()

{

int i ;

int a[] = {8 ,6 ,10 , 5 ,7, 9 , 11} ;

for(i = 0 ; i < N ; i++)

buildTree(a[i]) ;

postOrder(root) ;

cout<<endl ;

queue<BinaryTree<int>*> que ;

que.push(root) ;

bfs(root , que) ;

system("pause");

return 0 ;

}

posted on 2011-05-17 09:09 kahn 閱讀(200) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

面試100 12從上向下遍歷二叉樹

從上向下遍歷二叉樹