スタックを用いて、二分木を行きがけ順に表示させる

対象の木

下記の二分木を再帰的な方法を使用せずにスタックを用いて行きがけ順の表示をします。

コードのイメージ図

※ステップ4においては下記の条件の場合、スタックにノードを戻しません。
・各ノードに何回スタックにプッシュされたかのカウンターを保持しているので、そのカウンター数が2の場合
・ノードに子の数が1かつスタックにすでに1回プッシュされた場合

コード

preorder.c

#include <stdlib.h>
#include <stdio.h>

//declare node structure of tree
struct node{
  int data;
  struct node *left;
  struct node *right;
  int check; //variable to count number of time the node is put into the stack
};

//declare structure for stack
struct list{
  struct node *data;
  struct list *link;
};

//declare and set stack to null
struct list *q = NULL;

//function declaration
struct node * createNode(int);
void preorder(struct node *);
void push(struct node *);
struct node * pop();
int childcount(struct node *);

void main(){
  //create tree and add first node
  struct node *bt = createNode(1);

  //add nodes to tree
  bt->left = createNode(2);
  bt->right = createNode(3);
  (bt->left)->left = createNode(4);
  (bt->left)->right = createNode(5);
  (bt->right)->left = createNode(6);

  //traverse tree in preorder mode
  preorder(bt);
}

//display tree in preorder mode
void preorder(struct node *bt){
  //push root node to stack if tree is not empty
  if(bt!=NULL){
    push(bt);
  }

  //loop while stack is not empty
  while(q!=NULL){
    //retrieve node from stack
    struct node *temp = pop();

    //if node has child
    if(temp->left!=NULL || temp->right!=NULL){
      //check if node has been put in the stack before
      if(temp->check == 0){
        //print data of node
        printf("Data: %d\n",temp->data);
      }
      //if node has been stacked for 2 times or node has one child and been stacked once, continue to next loop
      if((temp->check == 2) || (temp->check == 1 && childcount(temp)==1)){
        continue;
      }
      //if node has left child
      if(temp->left!=NULL && temp->check==0){
        //add counter to stack check
        temp->check++;
        //push the node to stack
        push(temp);
        //push left child to stack
        push(temp->left);
      }
      //if node has right child
      else if(temp->right!=NULL && (temp->check==0 || temp->check==1)){
        //add counter to stack check
        temp->check++;
        //push the node to stack
        push(temp);
        //push right child to stack
        push(temp->right);
      }
    }
    //if node has no child(leaf node)
    if(temp->left == NULL && temp->right == NULL){
      //print data
      printf("Data: %d\n",temp->data);
    }

  }
}

//count number of child of node
int childcount(struct node *n){
  //set counter to 0
  int count = 0;
  //if node has left child
  if(n->left!=NULL){
    //add to counter
    count++;
  }
  //if node has right child
  if(n->right!=NULL){
    //add to counter
    count++;
  }

  return count;
}

//push node to stack
void push(struct node *l){
  //if stack is empty
  if(q==NULL){
    //create container
    q = malloc(sizeof(struct list));
    //add node address
    q->data = l;
    //set link of container to null
    q->link = NULL;
  }else{//if stack is not empty
    //create container
    struct list *temp = malloc(sizeof(struct list));
    //add node address
    temp->data = l;
    //set link of container to top of stack
    temp->link = q;
    //set stack pointer to the new container
    q = temp;
  }
}

//get node from stack
struct node * pop(){
  //declare locator pointer and set to top of stack
  struct list *temp = q;

  //get node address
  struct node *r = q->data;

  //if next container is not empty
  if(temp->link!=NULL){
    //set stack pointer to the next container
    q = temp->link;
  }else{// if next container is empty
    //set stack pointer to null
    q = NULL;
  }
  //free container
  free(temp);

  return r;
}

//function to create node
struct node * createNode(int num){
  //create node
  struct node *nd = malloc(sizeof(struct node));
  //set data to node
  nd->data = num;
  //set left child to null
  nd->left = NULL;
  //set right child to null
  nd->right = NULL;
  //set counter to zero
  nd->check = 0;

  return nd;
}

実行結果