CODEWITHSUNDEEP
calgorithmbinary-tree
Jonathan Swiecki
Jonathan Swiecki

Reputation: 89

Level-order traversal of a binary tree

I want to perform level-order traversal of a binary tree. Hence, for a given tree, say:

     3
    / \
   2   1
  / \   \
 4   6   10

the output would be:

3 2 1 4 6 10

I understand that I could use some sort of queue, but what is the algorithm to do this in C recursively? Any help appreciated.

Upvotes: 4

Views: 9648

Answers (6)

LinconFive
LinconFive

Reputation: 2012

In C, basic queue can be used via stack, i.e. array

#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：");
    BuildTree(t);
    PrintTree(t);
    printf("\n");
    printf("BFS：");
    BFS(t);
    printf("\n");

    DelTree(t);
}

Upvotes: 0

Ranjan Srivastava
Ranjan Srivastava

Reputation: 3

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

Upvotes: 0

Vatsal Prakash
Vatsal Prakash

Reputation: 558

Another No-recursive apporoach..

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


    }



}

Upvotes: 1

LeMoussel
LeMoussel

Reputation: 5767

Here code (no recursive function) from C5 library : 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);
    }
  }
}

Upvotes: 1

igarcia
igarcia

Reputation: 701

The graph algorithm is called Breadth First Search, it uses a queue to perform the level-order traversal, here is the pseudo-code

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

Upvotes: 11

Filippo Savi
Filippo Savi

Reputation: 397

here to you the pseudocode from wikipedia 

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)

you can then transform it into C that is trivial...

Upvotes: 3

Related Questions