二叉树的水平顺序遍历

我想执行二叉树的顺序遍历。因此，对于一个给定的树，说：二叉树的水平顺序遍历

输出将是：

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

二叉树的水平顺序遍历

回答

相关问题