스택을 사용하여 이진 트리를 돌아 오는 순서로 표시
18374 단어 C
대상 나무
아래의 이분목을 재귀적인 방법을 사용하지 않고 스택을 이용하여 돌아가는 순서의 표시를 합니다.
코드 이미지 다이어그램
※스텝 4에 있어서는 이하의 조건의 경우, 스택에 노드를 되돌리지 않습니다.
・각 노드에 몇 번 스택에 푸시되었는지의 카운터를 보관 유지하고 있으므로, 그 카운터수가 2의 경우
· 노드에 자식 수가 1이고 스택에 이미 한 번 푸시 된 경우
코드
postorder.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 postorder(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 postorder mode
postorder(bt);
}
//display tree in postorder mode
void postorder(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){
//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)){
//print data of node
printf("Data: %d\n",temp->data);
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;
}
실행 결과
Reference
이 문제에 관하여(스택을 사용하여 이진 트리를 돌아 오는 순서로 표시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/sabewe/items/e9f0fd3615c2150e349c
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
※스텝 4에 있어서는 이하의 조건의 경우, 스택에 노드를 되돌리지 않습니다.
・각 노드에 몇 번 스택에 푸시되었는지의 카운터를 보관 유지하고 있으므로, 그 카운터수가 2의 경우
· 노드에 자식 수가 1이고 스택에 이미 한 번 푸시 된 경우
코드
postorder.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 postorder(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 postorder mode
postorder(bt);
}
//display tree in postorder mode
void postorder(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){
//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)){
//print data of node
printf("Data: %d\n",temp->data);
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;
}
실행 결과
Reference
이 문제에 관하여(스택을 사용하여 이진 트리를 돌아 오는 순서로 표시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/sabewe/items/e9f0fd3615c2150e349c
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#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 postorder(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 postorder mode
postorder(bt);
}
//display tree in postorder mode
void postorder(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){
//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)){
//print data of node
printf("Data: %d\n",temp->data);
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;
}
Reference
이 문제에 관하여(스택을 사용하여 이진 트리를 돌아 오는 순서로 표시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/sabewe/items/e9f0fd3615c2150e349c텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)