二叉樹的水平順序遍歷

我想執行二叉樹的順序遍歷。因此，對於一個給定的樹，說：二叉樹的水平順序遍歷

輸出將是：

3 2 1 4 6 10

我明白，我可以使用某種形式的隊列，但算法做這在C遞歸是什麼？任何幫助讚賞。

來源

2013-03-01 Jonathan Swiecki

圖形算法稱爲廣度優先搜索，它使用隊列來執行水平序遍歷，這裏是僞

void breadth_first(Node root) 
{ 
    Queue q; 
    q.push(root); 
    breadth_first_recursive(q) 
} 

void breadth_first_recursive(Queue q) 
{ 
    if q.empty() return; 
    Node node = q.pop() 
    print Node 
    if (n.left) q.push(n.left) 
    if (n.right) q.push(n.right) 
    breadth_first_recursive(q) 
}

來源

2013-03-01 20:50:53 igarcia

我明白這一點，我所要求的算法與沒有循環遞歸做到這一點。 – 2013-03-01 20:51:55

好的，我要發佈一個遞歸的例子，給我一段時間 – igarcia 2013-03-01 20:53:25

謝謝，我想我可以很容易地實現這與我有的闕系統。 – 2013-03-01 21:00:18

這裏你從維基百科的僞

levelorder(root) 
    q = empty queue 
    q.enqueue(root) 
    while not q.empty do 
    node := q.dequeue() 
    visit(node) 
    if node.left ≠ null 
    q.enqueue(node.left) 
    if node.right ≠ null 
    q.enqueue(node.right)

然後你可以從C5庫其轉換成C是微不足道的......

來源

2013-03-01 20:52:43

我已經有這個，但不知道如何擺脫while循環。 – 2013-03-01 20:55:50

@JonathanSwiecki這裏這個很好地解釋http://www.cs.bu.edu/teaching/c/tree/breadth-first/也考慮這個鏈接http://stackoverflow.com/questions/6025632/bfs-in-binary -tree – 2013-03-01 21:02:12

這裏代碼（沒有遞歸函數）：C5 UserGuideExamples - TreeTraversal

public static void BreadthFirst(Tree<T> t, Action<T> action) 
{ 
    IQueue<Tree<T>> work = new CircularQueue<Tree<T>>(); 
    work.Enqueue(t); 
    while (!work.IsEmpty) 
    { 
    Tree<T> cur = work.Dequeue(); 
    if (cur != null) 
    { 
     work.Enqueue(cur.t1); 
     work.Enqueue(cur.t2); 
     action(cur.val); 
    } 
    } 
}

來源

2013-12-08 07:20:55 LeMoussel

另一個無遞歸之路探尋..

void LevelOrder(node * root) 
{ 
    queue<node *> q; 
    node *n=new node; 
    n=root; 
    while(n) 
    { 
     cout<<n->data<<" "; 
     if(n->left) 
      q.push(n->left); 
     if(n->right) 
      q.push(n->right); 
     n=q.front(); 
     q.pop(); 


    } 



}

來源

2015-09-13 10:53:33

void levelorder (Node *root) 
{ 
    if(!root) 
     return; 
    queue<Node*> Q; 
    Q.push(root); 
    while(!Q.empty()) 
    { 
    Node *current = Q.front();//returns the front element in queue 
    cout <<current->data;//printing the front node of queue 
    if(current->left!=NULL) 
     Q.push(current->left);//pushing left child 
    if(current->right!=NULL) 
     Q.push(current->right);//pushing right child 
    Q.pop();//removing front element from queue. 
    } 
}

來源

2016-09-28 15:33:08

這是C++代碼，我在頭文件中使用了C++中的可用空格隊列#include – 2016-09-28 15:34:50

二叉樹的水平順序遍歷

回答

相關問題