트리 ADT

트리 ADT

구조체 정보

typedef struct s_node
{
	void		*content;
	struct s_node	*parent;
	struct s_node	*left;
	struct s_node	*right;
}			t_tnode;

• 명령어를 저장하는 구문 트리 생성 시 사용
• binary tree

트리 구조체 초기화

#include "ds_tree.h"

t_tnode	*init_node(void *content);

사용예시

int main(int argc, char **argv, char **envp)
{
        t_token *token; //토큰이 할당 되어있다고 가정
	t_tnode	*new;

	new = init_node(NULL);
	new = init_node(token); 
}

트리 구조체 변수 초기화

#include "ds_tree.h"

void	set_content(t_tnode *node, void *content);

트리 구조체 child 추가

#include "ds_tree.h"

t_tnode	*add_lchild(t_tnode *node, void *content);
t_tnode	*add_rchild(t_tnode *node, void *content);

설명

• content를 가지는 new 노드를 생성 후 node의 child로 연결
• 현재 코드에서 사용되지 않아 삭제될 수 있음

트리 구조체 child 연결

#include "ds_tree.h"

void	set_lchild(t_tnode *node, t_tnode *left);
void	set_rchild(t_tnode *node, t_tnode *right);

설명

• node에 child 연결
• child의 parent에 node를 연결

트리 구조체 삭제

1. 트리 구조체 node 삭제

#include "ds_tree.h"

void	del_node(t_tnode *node, void (*del)(void *));

설명

• node의 content는 함수 포인터 del을 이용하여 삭제
• node 메모리 해제

2. 트리 구조체 전체 삭제

#include "ds_tree.h"

t_tnode	*clear_node(t_tnode *node, void (*del)(void *));

설명

• tree에 연결되어 있는 모든 노드를 삭제
  • 내부에서 모든 노드에 대해 del_node 함수를 호출
• node의 content는 함수 포인터 del을 이용하여 삭제

반환값

• NULL 반환
  • 코드에서 함수를 호출하는 경우 대부분 메모리 할당 실패 오류 발생

3. 트리 구조체 node 삭제 후 content 반환

#include "ds_tree.h"

void	*pop_node(t_tnode *node);

설명

• node 메모리 해제
• node의 content 반환

트리 구조체 탐색

#include "ds_tree.h"

void	preorder(t_tnode *node, int level, char *direction);

설명

• preorder(루트->왼쪽 자식->오른쪽 자식)순으로 트리 순회하면서 node의 content 출력
• 디버깅용이라 이후 삭제할 수 있음

사용예시

int main(int argc, char **argv, char **envp)
{
	t_tnode	*tree;

	preorder(tree, 0, "root");
}