대상 나무

코드 이미지 다이어그램

코드

#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 inorder(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 inorder mode
  inorder(bt);
}

//display tree in inorder mode
void inorder(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 == 1){
        //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;
}

실행 결과