두 갈래 찾기 트리의 C 언어 구현 (1)

무엇이 두 갈래로 나무를 찾습니까?
두 갈래 찾기 트리(Binary Search Tree), 질서정연한 두 갈래 트리(ordered binary tree), 정렬 두 갈래 트리(sorted binary tree)는 빈 나무 또는 아래의 성질을 가진 두 갈래 나무를 가리킨다.
만약 임의의 노드의 왼쪽 트리가 비어 있지 않으면 왼쪽 트리의 모든 결점의 값은 뿌리 결점의 값보다 작다
임의의 노드의 오른쪽 트리가 비어 있지 않으면 오른쪽 트리의 모든 결점의 값이 루트 결점의 값보다 크다
임의의 노드의 왼쪽, 오른쪽 나무도 각각 두 갈래로 나무를 찾는다
키 값이 같은 노드가 없습니다 (no duplicate nodes)..
자, 구조체를 정의하고,
struct  bnode_info {
	struct bnode_info *parent;
	struct bnode_info *lchild;
	struct bnode_info *rchild;
};
왜 데이터 영역이 없습니까?내핵 체인 시계를 모방하여 우리는 이 노드를 큰 구조체에 끼워 넣었다.
static inline void  bnode_init(struct bnode_info *bnode)
{
	bnode->parent = NULL;
	bnode->lchild = NULL;
	bnode->rchild = NULL;
}
노드의 초기화 함수는 다음 문장을 준비합니다.
struct data_info {
	int data;
	struct bnode_info bnode;
};
이것은 테스트용입니다. 노드를 끼워 넣은 것을 볼 수 있습니다.
static int  bnode_cmp(struct bnode_info *a, struct bnode_info *b)
{
	struct data_info *pa = list_entry(a, struct data_info, bnode);
	struct data_info *pb = list_entry(b, struct data_info, bnode);
	return  pa->data - pb->data;
}
비교 함수입니다.list_entry홍, 앞의 박문은 이미 말했으니, 여기는 군더더기 없습니다.
struct  btree_info {
	struct bnode_info *root; // 
	int (*key_cmp)(struct bnode_info *a, 
				struct bnode_info *b);
	void (*push)(struct bnode_info *bnode, 
				struct btree_info *info);
	int (*del)(struct bnode_info *bnode, struct btree_info *info);
	struct bnode_info *(*find)(struct bnode_info *bnode, 
						struct btree_info *info);
	void (*pre_order)(struct btree_info *info, 
			void (*todo)(struct bnode_info *bnode));
	void (*in_order)(struct btree_info *info, 
			void (*todo)(struct bnode_info *bnode));
	void (*post_order)(struct btree_info *info, 
			void (*todo)(struct bnode_info *bnode));
	// 
	void (*pre_order_norecur)(struct btree_info *info, 
			void (*todo)(struct bnode_info *bnode));
	void (*in_order_norecur)(struct btree_info *info, 
			void (*todo)(struct bnode_info *bnode));
	void (*post_order_norecur)(struct btree_info *info, 
			void (*todo)(struct bnode_info *bnode));
	void (*level_order)(struct btree_info *info, 
			void (*todo)(struct bnode_info *bnode));
	size_t (*get_depth)(const struct btree_info *info);
	int (*is_empty)(const struct btree_info *info);
};
여기에는 많은 방법이 정의되어 있다. 우리는 우선 상관하지 않는다. 안에 바늘이 있다는 것을 알고 나무 뿌리를 가리키면 된다.
static int btree_is_empty(const struct btree_info *btree)
{
	return	btree->root == NULL;	
}
나무가 비어 있다면 뿌리도 없는 것이다.
다음은 원소를 나무에 삽입하는 것을 본론으로 들어갑니다.
분석: 1.이 나무는 비어 있다.그 문제는 간단하다. 이 노드가 바로 나무 뿌리다.
   2.이 나무는 비어 있지 않다.그럼 나무 뿌리에서 찾아야지.새로운 원소와 뿌리를 비교해 보면 작으면 뿌리의 왼쪽 아이와 비교하고, 크면 뿌리의 오른쪽 아이와 비교한다.만약 왼쪽 아이나 오른쪽 아이가 비어 있다면, 그것은 위치를 찾은 것이다. 이 새로운 요소를 아이가 되게 하면 된다.주의해라, 여기는 우리가 차례로 돌아갈 필요가 없고, 교체할 필요가 없다.
static void btree_push2(struct bnode_info *bnode, 
					struct btree_info *info)
{
	assert(bnode != NULL && info != NULL);

	bnode_init(bnode);

	//[1]. 
	if (btree_is_empty(info)) 
	{
		info->root = bnode;
		return;
	}
	
	//[2]. 
	struct bnode_info *cur = info->root;
	struct bnode_info *parent = NULL;
	int flag = 0;
	
	while (cur != NULL) 
	{
		parent = cur; 
		if (info->key_cmp(bnode, cur) >= 0) 
		{
			// 
			cur = cur->rchild;
			flag = 1;
		}
		else 
		{
			// 
			cur = cur->lchild;
			flag = 0;
		}
	}	

	
	if(flag==0) 
		parent->lchild=bnode;
	else
		parent->rchild=bnode;
		
	bnode->parent = parent;
	
}

옳고 그름을 검증하기 위해서 우리는 나무를 두루 훑어보는 방법을 써야 한다.차례차례 훑어보기 - 차례차례 버전, (뿌리부터 왼쪽 나무, 마지막 오른쪽 나무)
static void __pre_order(struct bnode_info *bnode,
                        void (*todo)(struct bnode_info *bnode))
{
	if (bnode != NULL) {
		todo(bnode);
		__pre_order(bnode->lchild, todo);
		__pre_order(bnode->rchild, todo);
	}
}

	

static void btree_pre_order(struct btree_info *info,
                        void (*todo)(struct bnode_info *bnode))
{
	__pre_order(info->root, todo);
}
void print_node(struct bnode_info *node)
{
	struct data_info *pa = list_entry(node, struct data_info, bnode);

	printf("%d ", pa->data);
}
이것은 인쇄용입니다. 그때 todo에게 전해 주십시오.
테스트 함수:
int main()
{
	
	struct data_info s[]={
		{50},{24},{80},{16},{26},{5}
	};
	struct btree_info *btree = (struct btree_info *)
			malloc(sizeof(struct btree_info));
	assert(btree != NULL);

	btree_init(btree, bnode_cmp);


	int i;
	for (i = 0; i < sizeof s/ sizeof *s; ++i) {
		btree->push(&s[i].bnode, btree);
	}

	// 
	printf("--pre_order--
"); btree->pre_order(btree, print_node); printf("
");

먼저 실행 결과를 살펴보겠습니다.
--pre_order--
50 24 16 5 26 80 
이어서 삽입, 앞의 시비 귀속 방법을 말한다.이번에 우리는 차례대로 귀속한다.사고방식은 매우 간단하다. 삽입할 노드를 뿌리와 비교하면 뿌리가 비어 있으면 이 노드는 뿌리가 된다.뿌리보다 작으면 뿌리의 왼쪽 아이와 비교한다.뿌리보다 크면 뿌리의 오른쪽 아이와 비교해라.여기서 주의해야 할 것은 나무뿌리보다 작다고 가정하면 나무뿌리의 왼쪽 아이와 비교하고 들어오는 파라미터가 새 노드와 왼쪽 아이라고 가정하면 왼쪽 아이가 NULL이라는 것을 발견하면 어떻게 합니까?물론 새 노드의 주소를 여기에 써야 합니다. NULL을 바꾸기 위해서 우리는 이 영역의 주소를 알아야 합니다. 여기에 2급 지침이 도입되었습니다.즉, 우리의 함수를 설계할 때 매개 변수는 새 노드의 주소와 나무 뿌리의 2급 지침이다.
static void __push(struct bnode_info *bnode, struct bnode_info **pnode, 
					int (*cmp)(struct bnode_info *a, struct bnode_info *b))
{
	if (*pnode == NULL)
	{
		bnode_init(bnode);
		*pnode = bnode; 
	}
	else
    {	
		if (cmp(bnode, *pnode) > 0)
			__push(bnode, &(*pnode)->rchild,cmp);
			
		else 
			__push(bnode, &(*pnode)->lchild,cmp);		
	}
}



void btree_push_recursion(struct bnode_info *bnode, struct btree_info *info)
{
	assert(bnode != NULL && info != NULL);
	__push(bnode, &info->root,info->key_cmp);// 
}

총결해 봐, 이 문장에서 우리가 무슨 말을 했지?1. 노드의 삽입(귀속 및 비귀속) 2.순차 반복 (반복 버전)
다음에 이어서 얘기합시다.

좋은 웹페이지 즐겨찾기