데이터 및 구조: 트리 (1)

두 갈래 검색 트리 (1)

구현 방법: 스택 + 트리
실현 기능: 나무 한 그루를 비우고 특정 요소를 삽입하고 노드를 삭제하며 나무 한 그루를 훑어본다
중요 절차:

요소 삽입

반복 삽입

Tree Insert_1(type val, Tree tree){
    if(tree==NULL){
        tree=(Tree)malloc(sizeof(struct TreeNode));
        if(!tree){
            exit(0);
        }else{
            tree->val=val;
            tree->left=tree->right=NULL;
        }    
    }
    else if(valval){
        tree->left=Insert_1(val,tree->left);
    }
    else if(val>tree->val){
        tree->right=Insert_1(val,tree->right);
    }
}

비반복 삽입

Tree Insert_2(type val, Tree tree){
    Tree node = (Tree)malloc(sizeof(struct TreeNode));
	if (node == NULL) {
		exit(-1);
	}
	node->val = val;
	node->left = node->right = NULL;

    if (tree == NULL) {
		tree = (Tree)malloc(sizeof(struct TreeNode));
		if (tree == NULL) {
			exit(-1);
		}
		tree = node;
	}
    else{
        while (tree!=NULL)
        {
            if(valval){
                if(tree->left==NULL){
                    tree->left=node;
                    return tree;
                }else{
                    tree=tree->left;
                }
            }
            else if(val>tree->val){
                if(tree->right==NULL){
                    tree->right=node;
                }else{
                    tree=tree->right;
                }
            }
        }
        
    }
    
}

관건: 왼쪽의 노드 값은 루트 노드보다 작고 오른쪽의 노드 값은 루트 노드보다 크다

노드 삭제

1. 관련 검색 과정 준비

앞부분 찾기

Position Find_prev(const type val, const Tree tree){
    if(tree==NULL){
        return;
    }
    if((tree->left!=NULL && tree->left->val==val)||(tree->right!=NULL && tree->right->val==val)){
        return tree;
    }
    if(valval){
        return Find_prev(val,tree->left);
    }
    if(val>tree->val){
        return Find_prev(val,tree->right);
    }
}

요소 찾기

Position Find(const type val, const Tree tree){
    if(tree==NULL){
        return;
    }
    if(val==tree->val){
        return tree;
    }
    if(valval){
        Find(val,tree->left);
    }
    if(val>tree->val){
        Find(val,tree->right);
    }
}

최소 찾기

차례로 찾아라

Position FindMin_1(const Tree tree){
    if(tree==NULL){
        return;
    }
    if(tree->left==NULL){
        return tree;
    }
    else{
        return FindMin_1(tree->left);
    }
}

비귀속 찾기

Position FindMin_2(const Tree tree){
    if(tree==NULL){
        return;
    }
    Tree tmp=(Tree)malloc(sizeof(struct TreeNode));
    tmp=tree;
    while (tmp->left!=NULL)
    {
        tmp=tmp->left;
    }
    return tmp;
    
}

최대값 찾기

차례로 찾아라

Position FindMax_1(const Tree tree){
    if (tree == NULL) {
		return NULL;
	}
	if (tree->right == NULL) {
		return tree;
	}
	else{
		return FindMax_1(tree->right);
	}
}

비귀속 찾기

Position FindMax_2(const Tree tree){
    if (tree == NULL) {
		return NULL;
	}
	Tree temp = (Tree)malloc(sizeof(struct TreeNode));
	temp = tree;
	while (temp->right != NULL) {
		temp = temp->right;
	}
	return temp;
}

삭제

노드가 잎 노드라면 직접 삭제합니다

노드에 아들이 한 명 있으면 아버지 노드 바늘을 조절할 수 있다

아들 2명을 두고 오른쪽 나무의 가장 작은 데이터로 이 노드를 대체한다(우쪽 나무의 가장 작은 노드에는 왼쪽 노드가 없을 것이다). 그리고 지침을 조정한다

Tree Delete(type val, Tree tree){
    if(tree==NULL){
        exit(0);
    }
    Tree cur_node=Find(val,tree);
    Tree prev_node=Find_prev(val,tree);

    if(cur_node->left==NULL && cur_node->right==NULL){
        Tree tmp=cur_node;
        (cur_node->val < prev_node->val)?(prev_node->left=NULL):(prev_node->right=NULL);
        free(tmp);
    }
    else if(cur_node->left&&cur_node->right){
        Tree tmp=cur_node;
        Tree min_node=FindMin_1(cur_node->right);
        Tree min_prev=Find_prev(min_node->val,cur_node->right);
        if(min_node->right==NULL){
            cur_node->val=min_node->val;
            min_prev->left=NULL;
        }
        else{
             cur_node->val=min_node->val;
             min_prev->left=min_node->right;
             min_node->left=NULL;
        }
        free(tmp);
    }
    else{
        Tree tmp=cur_node;
        if(cur_node->left==NULL){
            cur_node=cur_node->right;
        }
        else if(cur_node->right==NULL){
            cur_node=cur_node->left;
        }
        free(tmp);
    }
}

두루 다니다

차례로 두루 다니다

// 
void pre_Traverse_1(const Tree tree) {
	if (tree != NULL) {
		printf("%-2d", tree->val);
		pre_Traverse_1(tree->left);
		pre_Traverse_1(tree->right);
	}
}

// 
void in_Traverse_1(const Tree tree) {
	if (tree != NULL) {
		in_Traverse_1(tree->left);
		printf("%-2d", tree->val);
		in_Traverse_1(tree->right);
	}
}

// 
void post_Traverse_1(const Tree tree) {
	if (tree != NULL) {
		post_Traverse_1(tree->left);
		post_Traverse_1(tree->right);
		printf("%-2d", tree->val);
	}
}

역행

void pre_Traverse_2(const Tree tree, stack P) {
	Tree temp = (Tree)malloc(sizeof(struct TreeNode));
	temp = tree;
	if (temp == NULL) {
		return;
	}
	while (!isEmpty(P) || temp)
	{
		if (temp) {
			printf("%-2d", temp->val);
			push(P, temp);
			temp = temp->left;
		}
		else
		{
			temp = top(P);
			pop(P);
			temp = temp->right;
		}
	}
}

void in_Traverse_2(Tree tree, stack P) {
	Tree temp = (Tree)malloc(sizeof(struct TreeNode));
	temp = tree;
	while (!isEmpty(P) || temp)
	{
		if (temp) {
			push(P, temp);
			temp = temp->left;
		}
		else
		{
			temp = top(P);
			pop(P);
			printf("%-2d", temp->val);
			temp = temp->right;
		}
	}
}

비귀속 반복, 그리고 두 갈래 검색 트리에 대한 내용은 다음 블로그에서 제공합니다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.