二叉樹的水平順序遍歷

Question

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

 3 
    /\ 
    2 1 
/\ \ 
4 6 10 

輸出將是：

3 2 1 4 6 10 

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

Answer 1

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

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) 
} 

Answer 2

這裏你從維基百科的僞

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是微不足道的......

Answer 3

這裏代碼（沒有遞歸函數）：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); 
    } 
    } 
} 

Answer 4

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

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(); 


    } 



} 

Answer 5

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. 
    } 
}