4

我想执行二叉树的级别顺序遍历。因此，对于给定的树，说：

     3
    / \
   2   1
  / \   \
 4   6   10

输出将是：

3 2 1 4 6 10

我知道我可以使用某种队列，但是在 C 中递归执行此操作的算法是什么？任何帮助表示赞赏。

4

6 回答 6

11

图算法称为广度优先搜索，它使用队列进行层序遍历，这里是伪代码

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-01T20:50:53.183 回答
3

这里给你来自维基百科的伪代码

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)

然后，您可以将其转换为微不足道的 C...

于 2013-03-01T20:52:43.533 回答
1

这里来自 C5 库的代码（无递归函数）：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-08T07:20:55.443 回答
1

另一种无递归方法..

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-13T10:53:33.927 回答
0 
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-28T15:33:08.583 回答
0

在C语言中，基本队列可以通过栈使用，即数组

#include<stdio.h>

#include<stdlib.h>

#define MaxSize 10

//typedef char ElemType;
typedef int ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode * lchild, * rchild;
}
BiTNode, * BiTree;

void BuildTree(BiTree * T) {
    /*
                            t1
                    t2              t3
                t4       t5              t6

    */
    BiTNode * t1 = T;
    t1 -> data = 3;

    BiTree t2 = (BiTNode * ) malloc(sizeof(BiTNode));
    t2 -> data = 2;
    t1 -> lchild = t2;

    BiTree t3 = (BiTNode * ) malloc(sizeof(BiTNode));
    t3 -> data = 1;
    t1 -> rchild = t3;

    BiTree t4 = (BiTNode * ) malloc(sizeof(BiTNode));
    t4 -> data = 4;

    BiTree t5 = (BiTNode * ) malloc(sizeof(BiTNode));
    t5 -> data = 6;
    t2 -> lchild = t4;
    t2 -> rchild = t5;

    BiTree t6 = (BiTNode * ) malloc(sizeof(BiTNode));
    t6 -> data = 10;
    t3 -> rchild = t6;

    t3 -> lchild = NULL;
    t4 -> lchild = NULL;
    t4 -> rchild = NULL;
    t5 -> lchild = NULL;
    t5 -> rchild = NULL;
    t6 -> lchild = NULL;
    t6 -> rchild = NULL;
}
void print2DUtil(struct BiTNode * root, int space) {
    // Base case
    if (root == NULL)
        return;

    // Increase distance between levels
    space += MaxSize;

    // Process right child first
    print2DUtil(root -> rchild, space);

    // Print current node after space
    // count
    printf("\n");
    for (int i = MaxSize; i < space; i++)
        printf(" ");
    printf("%d\n", root -> data);

    // Process left child
    print2DUtil(root -> lchild, space);
}
// Wrapper over print2DUtil()
void PrintTree(struct BiTNode * root) {
    // Pass initial space count as 0
    print2DUtil(root, 0);
}
void visit(BiTree T) {
    printf("%d  ", T -> data);
}
//BFS
void BFS(BiTree T) {
    if (T != NULL) {
        int front = 0;
        int rear = 0;
        BiTree queue[MaxSize];
        BiTree p;
        p = T;
        rear = (rear + 1) % MaxSize;
        queue[rear] = p;
        while (rear != front) {
            front = (front + 1) % MaxSize;
            p = queue[front];
            visit(p);
            if (p -> lchild != NULL) {
                rear = (rear + 1) % MaxSize;
                queue[rear] = p -> lchild;
            }
            if (p -> rchild != NULL) {
                rear = (rear + 1) % MaxSize;
                queue[rear] = p -> rchild;
            }

        }
    }
}

void DelTree(BiTree T) {
    if (T == NULL) return;
    DelTree(T -> lchild);
    DelTree(T -> rchild);
    free(T);
}

int main() {
    BiTree t = (BiTNode * ) malloc(sizeof(BiTNode));
    printf("Tree：&quot;);
    BuildTree(t);
    PrintTree(t);
    printf("\n");
    printf("BFS：&quot;);
    BFS(t);
    printf("\n");

    DelTree(t);
}
于 2021-05-28T06:56:15.873 回答