[공학]Binary tree deletion

소개글

입력 받는 숫자를 binary tree 구조로 노드 연결 후
지우고자 하는 노드를 지운후 중위 전임자로 트리를 연결해준다

목차

알고리즘
Output

본문내용

☐ 알고리즘

29 - 41 - 15 - 52 - 25 27 10 36 20 48 7 13 11 24

주어진 숫자 입력시 <그림 I> 과 같은 binary tree 생성
처음 입력된 29의 숫자를 기준으로 setleft()와 setright() 함수를 통해
좌우로 이진 트리를 생성해준다.

15란 노드를 삭제할 때 predecessor인(지워질 노드의 왼쪽에서 가장 오른쪽 노드)
13을 15의 자리에 놓은 뒤 좌우 노드를 이어주는 알고리즘.

출력시 inorder traverse후 preorder traverse 또한 보임으로써 15노드의 위치에
13 노드가 왔음을 보여준다.


// 컴파일러: Visual C++ 6.0

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

struct node{

int info;
struct node *left; //왼쪽 노드 가리킴
struct node *right; //오른쪽 노드 가리킴
};

typedef struct node *NODEPTR; //struct node 포인터를 설정

//하나의 노드에 대한 동적 할당
NODEPTR getnode(void)
{

NODEPTR q;
q = (NODEPTR)malloc(sizeof(struct node));

return(q);
}

//값을 받아 노드를 하나 설정
NODEPTR maketree(int x)
{

참고 자료

c로 구현한 자료구조