트리의 동일한 계층에 노드 추가
19576 단어 C
이번에 만드는 나무의 구조
동일한 계층구조에 모든 노드를 채우고 다음 계층구조에 노드를 추가합니다.
코드 이미지 다이어그램
큐에 트리의 노드의 정보를 보관 유지해, 큐에 새로운 노드를 추가하는 것으로, 트리에 같은 노드가 추가시킵니다.
코드
insertbt.c#include <stdio.h>
#include <stdlib.h>
//declare struct for queue
struct list{
struct node *data;
struct list *link;
};
//declare struct for tree
struct node{
int data;
struct node *left;
struct node *right;
};
//initialized queue
struct list *lst = NULL;
//function declaration
void push(struct node *);
void pop();
void insert(struct node **, int);
void inorder(struct node *);
void main(){
//initialized tree
struct node *bt = NULL;
//insert node to tree
insert(&bt,1);
insert(&bt,2);
insert(&bt,3);
insert(&bt,4);
insert(&bt,5);
insert(&bt,6);
//display tree in inorder traversal
inorder(bt);
}
//display tree in inorder traversal
void inorder(struct node *s){
//if node is not empty
if(s!=NULL){
//call inorder function recursively for left child of node
inorder(s->left);
//print data of node
printf("%d\n",s->data);
//call inorder function recursively for right child of node
inorder(s->right);
}
}
//insert node at available position on the same level of tree
void insert(struct node **bt, int num){
//if tree is empty
if(*bt == NULL){
//create root node
*bt = malloc(sizeof(struct node));
//set data of node
(*bt)->data = num;
//set left child of node to null
(*bt)->left = NULL;
//set right child of node to null
(*bt)->right = NULL;
//push root node to queue
push(*bt);
}else{
//initialized locator pointer to queue
struct list *temp = lst;
//loop through queue
while(temp!=NULL){
//if both child of node is full, remove node from queue
if((temp->data)->left !=NULL && (temp->data)->right != NULL){
pop();
}else{
//if left child of node is empty
if((temp->data)->left == NULL){
//initialized pointer to left child of node
struct node **p = &((temp->data)->left);
//create new node at left child
*p = malloc(sizeof(struct node));
//set data of new node
(*p)->data = num;
//set left child of new node to null
(*p)->left = NULL;
//set right child of new node to null
(*p)->right = NULL;
//push new node to queue
push(*p);
//go back to main
return;
}
//if right child of node is empty
if((temp->data)->right == NULL){
//initialized pointer to right child of node
struct node **p = &((temp->data)->right);
//create new node at right child
*p = malloc(sizeof(struct node));
//set data of new node
(*p)->data = num;
//set left child of new node to null
(*p)->left = NULL;
//set right child of new node to null
(*p)->right = NULL;
//push new node to queue
push(*p);
return;
}
}
//go to next node in queue
temp = temp->link;
}
}
}
//add node to queue
void push(struct node *t){
//if queue is empty
if(lst==NULL){
//create new node in queue
lst = malloc(sizeof(struct list));
//set address of tree's node
lst->data = t;
//set link of new node to null
lst->link = NULL;
}else{//if queue is not empty
//declare locator pointer
struct list *temp;
//set pointer to queue
temp = lst;
//loop until the last node of queue
while(temp->link != NULL){
//go to next node in queue
temp = temp->link;
}
//set link of last node to new node
temp->link = malloc(sizeof(struct list));
//set address of tree's node
(temp->link)->data = t;
//set link of new node to null
(temp->link)->link = NULL;
}
return;
}
//remove node from queue
void pop(){
//if queue is empty
if(lst == NULL){
return;
}else{//if queue is not empty
//initialized locator pointer to queue
struct list *temp = lst;
//if next node in queue is not empty
if(temp->link!=NULL){
//set queue's pointer to next node in queue
lst = temp->link;
}else{//if last node in queue
//set queue's pointer to null
lst = NULL;
}
//free node in queue
free(temp);
}
return;
}
코드 실행 결과
트리의 노드를 통과 순서로 표시합니다.
Reference
이 문제에 관하여(트리의 동일한 계층에 노드 추가), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/sabewe/items/57ce6380f864a1e27477
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
큐에 트리의 노드의 정보를 보관 유지해, 큐에 새로운 노드를 추가하는 것으로, 트리에 같은 노드가 추가시킵니다.
코드
insertbt.c#include <stdio.h>
#include <stdlib.h>
//declare struct for queue
struct list{
struct node *data;
struct list *link;
};
//declare struct for tree
struct node{
int data;
struct node *left;
struct node *right;
};
//initialized queue
struct list *lst = NULL;
//function declaration
void push(struct node *);
void pop();
void insert(struct node **, int);
void inorder(struct node *);
void main(){
//initialized tree
struct node *bt = NULL;
//insert node to tree
insert(&bt,1);
insert(&bt,2);
insert(&bt,3);
insert(&bt,4);
insert(&bt,5);
insert(&bt,6);
//display tree in inorder traversal
inorder(bt);
}
//display tree in inorder traversal
void inorder(struct node *s){
//if node is not empty
if(s!=NULL){
//call inorder function recursively for left child of node
inorder(s->left);
//print data of node
printf("%d\n",s->data);
//call inorder function recursively for right child of node
inorder(s->right);
}
}
//insert node at available position on the same level of tree
void insert(struct node **bt, int num){
//if tree is empty
if(*bt == NULL){
//create root node
*bt = malloc(sizeof(struct node));
//set data of node
(*bt)->data = num;
//set left child of node to null
(*bt)->left = NULL;
//set right child of node to null
(*bt)->right = NULL;
//push root node to queue
push(*bt);
}else{
//initialized locator pointer to queue
struct list *temp = lst;
//loop through queue
while(temp!=NULL){
//if both child of node is full, remove node from queue
if((temp->data)->left !=NULL && (temp->data)->right != NULL){
pop();
}else{
//if left child of node is empty
if((temp->data)->left == NULL){
//initialized pointer to left child of node
struct node **p = &((temp->data)->left);
//create new node at left child
*p = malloc(sizeof(struct node));
//set data of new node
(*p)->data = num;
//set left child of new node to null
(*p)->left = NULL;
//set right child of new node to null
(*p)->right = NULL;
//push new node to queue
push(*p);
//go back to main
return;
}
//if right child of node is empty
if((temp->data)->right == NULL){
//initialized pointer to right child of node
struct node **p = &((temp->data)->right);
//create new node at right child
*p = malloc(sizeof(struct node));
//set data of new node
(*p)->data = num;
//set left child of new node to null
(*p)->left = NULL;
//set right child of new node to null
(*p)->right = NULL;
//push new node to queue
push(*p);
return;
}
}
//go to next node in queue
temp = temp->link;
}
}
}
//add node to queue
void push(struct node *t){
//if queue is empty
if(lst==NULL){
//create new node in queue
lst = malloc(sizeof(struct list));
//set address of tree's node
lst->data = t;
//set link of new node to null
lst->link = NULL;
}else{//if queue is not empty
//declare locator pointer
struct list *temp;
//set pointer to queue
temp = lst;
//loop until the last node of queue
while(temp->link != NULL){
//go to next node in queue
temp = temp->link;
}
//set link of last node to new node
temp->link = malloc(sizeof(struct list));
//set address of tree's node
(temp->link)->data = t;
//set link of new node to null
(temp->link)->link = NULL;
}
return;
}
//remove node from queue
void pop(){
//if queue is empty
if(lst == NULL){
return;
}else{//if queue is not empty
//initialized locator pointer to queue
struct list *temp = lst;
//if next node in queue is not empty
if(temp->link!=NULL){
//set queue's pointer to next node in queue
lst = temp->link;
}else{//if last node in queue
//set queue's pointer to null
lst = NULL;
}
//free node in queue
free(temp);
}
return;
}
코드 실행 결과
트리의 노드를 통과 순서로 표시합니다.
Reference
이 문제에 관하여(트리의 동일한 계층에 노드 추가), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/sabewe/items/57ce6380f864a1e27477
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <stdio.h>
#include <stdlib.h>
//declare struct for queue
struct list{
struct node *data;
struct list *link;
};
//declare struct for tree
struct node{
int data;
struct node *left;
struct node *right;
};
//initialized queue
struct list *lst = NULL;
//function declaration
void push(struct node *);
void pop();
void insert(struct node **, int);
void inorder(struct node *);
void main(){
//initialized tree
struct node *bt = NULL;
//insert node to tree
insert(&bt,1);
insert(&bt,2);
insert(&bt,3);
insert(&bt,4);
insert(&bt,5);
insert(&bt,6);
//display tree in inorder traversal
inorder(bt);
}
//display tree in inorder traversal
void inorder(struct node *s){
//if node is not empty
if(s!=NULL){
//call inorder function recursively for left child of node
inorder(s->left);
//print data of node
printf("%d\n",s->data);
//call inorder function recursively for right child of node
inorder(s->right);
}
}
//insert node at available position on the same level of tree
void insert(struct node **bt, int num){
//if tree is empty
if(*bt == NULL){
//create root node
*bt = malloc(sizeof(struct node));
//set data of node
(*bt)->data = num;
//set left child of node to null
(*bt)->left = NULL;
//set right child of node to null
(*bt)->right = NULL;
//push root node to queue
push(*bt);
}else{
//initialized locator pointer to queue
struct list *temp = lst;
//loop through queue
while(temp!=NULL){
//if both child of node is full, remove node from queue
if((temp->data)->left !=NULL && (temp->data)->right != NULL){
pop();
}else{
//if left child of node is empty
if((temp->data)->left == NULL){
//initialized pointer to left child of node
struct node **p = &((temp->data)->left);
//create new node at left child
*p = malloc(sizeof(struct node));
//set data of new node
(*p)->data = num;
//set left child of new node to null
(*p)->left = NULL;
//set right child of new node to null
(*p)->right = NULL;
//push new node to queue
push(*p);
//go back to main
return;
}
//if right child of node is empty
if((temp->data)->right == NULL){
//initialized pointer to right child of node
struct node **p = &((temp->data)->right);
//create new node at right child
*p = malloc(sizeof(struct node));
//set data of new node
(*p)->data = num;
//set left child of new node to null
(*p)->left = NULL;
//set right child of new node to null
(*p)->right = NULL;
//push new node to queue
push(*p);
return;
}
}
//go to next node in queue
temp = temp->link;
}
}
}
//add node to queue
void push(struct node *t){
//if queue is empty
if(lst==NULL){
//create new node in queue
lst = malloc(sizeof(struct list));
//set address of tree's node
lst->data = t;
//set link of new node to null
lst->link = NULL;
}else{//if queue is not empty
//declare locator pointer
struct list *temp;
//set pointer to queue
temp = lst;
//loop until the last node of queue
while(temp->link != NULL){
//go to next node in queue
temp = temp->link;
}
//set link of last node to new node
temp->link = malloc(sizeof(struct list));
//set address of tree's node
(temp->link)->data = t;
//set link of new node to null
(temp->link)->link = NULL;
}
return;
}
//remove node from queue
void pop(){
//if queue is empty
if(lst == NULL){
return;
}else{//if queue is not empty
//initialized locator pointer to queue
struct list *temp = lst;
//if next node in queue is not empty
if(temp->link!=NULL){
//set queue's pointer to next node in queue
lst = temp->link;
}else{//if last node in queue
//set queue's pointer to null
lst = NULL;
}
//free node in queue
free(temp);
}
return;
}
트리의 노드를 통과 순서로 표시합니다.
Reference
이 문제에 관하여(트리의 동일한 계층에 노드 추가), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/sabewe/items/57ce6380f864a1e27477텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)