이 진 트 리 (BST) 재 귀적 및 비 재 귀적 삽입, 삭제, 검색 의 실현

어제 이 진 트 리 (BST) 라 는 데이터 구 조 를 만 나 아예 자세히 배 웠 다.
BST 의 정의: 만약 에 한 나무의 왼쪽 나무 가 비어 있 지 않 으 면 모든 노드 의 값 은 그 뿌리 노드 의 값 보다 작 습 니 다. 만약 에 오른쪽 나무 가 비어 있 지 않 으 면 모든 노드 의 값 은 그 뿌리 노드 의 값 보다 크 고 그의 좌우 나무 도 상기 성질 을 만족 시 킵 니 다.빈 나무 도 BST.
나의 BST 의 실현 은 중복 요소 가 없 는 것 을 전제 로 하 는데 사실은 중복 요소 가 있어 도 큰 문제 가 없 으 며 실현 과정 에서 관련 된 것 일 뿐이다.
노드 구조 정의:

class Node{
public:
    int val;
    Node *left, *right;
    Node() {}
    Node(int val) : val(val), left(NULL), right(NULL) {}
};

BST 구조 정의 및 구현 방법:

class BST{
private:
    Node *root;
    void Recursion_Insert_Node(Node *&node, int x);//      
    void Non_Recursion_Insert_Node(Node **node, int x);//       
    Node *Recursion_Find_Node(Node *node, int x);//      
    Node *Non_Recursion_Find_Node(Node *root, int x);//       
    void Delete_Node(Node **root, int x);//    
    void preOrder_Traverse(Node *root);//    
    void inOrder_Traverse(Node *root);//    
    void postOrder_Traversal(Node *root);//    
    void Delete_BST(Node *node);//    
public:
    BST();
    ~BST();
    void Create_BST(int *num, int n);//  BST
    Node *Find_Node(int x);
    void Delete_Node(int x);
    void preOrder_Traverse();
    void inOrder_Traverse();
    void postOrder_Traversal();
};

먼저 삽입 결점 이 어떻게 실현 되 는 지 살 펴 보 자. 첫 번 째 로 저장 할 값 에 대해 우 리 는 그것 을 뿌리 결점 으로 설정 한 다음 에 뿌리 결점 보다 작은 값 에 대해 우 리 는 이 를 왼쪽 나무 로 이동 시 킨 다음 에 비교 하고 잎 노드 가 될 때 까지 이동 하면 뿌리 결점 보다 큰 값 이 같다.
구체 적 인 실현:
귀속:

void BST::Recursion_Insert_Node(Node *&node, int x){
    if(node == NULL){
        node = new Node(x);
    }
    else if(node->val > x){
        Recursion_Insert_Node(node->left, x);
    }
    else if(node->val < x){
        Recursion_Insert_Node(node->right, x);
    }
}

비 귀속:

void BST::Non_Recursion_Insert_Node(Node **root, int x){
    Node *p = *root;
    Node *fa = *root;
    while(p){
        if(p->val == x){
            printf("%d is already exist!
", x);
            return;
        }
        fa = p;
        if(p->val > x){
            p = p->left;
        }
        else{
            p = p->right;
        }
    }
    if(fa == NULL){
        *root = new Node(x);
    }
    else if(fa->val > x){
        fa->left = new Node(x);
    }
    else{
        fa->right = new Node(x);
    }
}

재 귀적 이지 않 은 경우 Node 의 유형 은 지침 을 가리 키 는 지침 입 니 다. 지침 만 전달 할 수 없습니다. 지침 만 전달 하고 지침 값 의 복사 가 되면 루트 가 NULL 을 가리 킬 때 함수 내부 new 노드 가 실제 지침 에 의 해 가리 키 지 않 기 때 문 입 니 다.또한 지침 의 인용 도 있어 서 는 안 된다. 왜냐하면 뿌리 결점 을 가리 키 는 지침 이 하위 노드 를 가리 키 기 때문이다.
결점 찾기 의 실현: 사상 은 삽 입 된 것 과 마찬가지 로 지침 을 사용 할 수 있 을 뿐 지침 을 가리 키 는 지침 을 사용 하지 않 습 니 다. 우 리 는 찾 는 요소 의 주소 만 찾 아야 하기 때문에 조작 할 필요 가 없습니다. 지침 을 사용 하면 쉽게 작업 을 완성 할 수 있 습 니 다.
귀속:

Node *BST::Recursion_Find_Node(Node *node, int x){
    if(node == NULL)
        return NULL;
    if(node->val == x)
        return node;
    if(node->val > x)
        return Recursion_Find_Node(node->left, x);
    else
        return Recursion_Find_Node(node->right, x);
}

비 귀속:

Node *BST::Non_Recursion_Find_Node(Node *node, int x){
    if(node == NULL)
        return NULL;
    while(node){
        if(node->val == x)
            return node;
        else if(node->val > x)
            node = node->left;
        else
            node = node->right;
    }
    return node;
}

마지막 으로 삭제 작업 입 니 다:
삭제 작업 은 재 귀적 인 쓰기 가 생각 나 지 않 습 니 다...
BST 삭제 작업 에 대해 세 가지 상황 이 있 습 니 다.
1: 노드 를 삭제 하 는 것 이 잎 노드 인 경우 에 가장 좋 습 니 다. 부모 노드 를 비 운 다음 에 이 노드 를 삭제 하면 됩 니 다.
2: 노드 를 삭제 하 는 데 마침 한 가지 가 있 습 니 다. 우 리 는 아버지 노드 를 아들 노드 에 가리 키 기만 하면 됩 니 다. 그리고 delete 를 하면 비교적 간단 합 니 다.
3: 노드 를 삭제 하 는 데 마침 두 개의 갈래 가 있 는데 이런 상황 이 비교적 번 거 롭 고 두 가지 처리 방법 이 있다. 이 두 가지 방법 을 말 하기 전에 우 리 는 먼저 두 가지 개념 을 알 아야 한다. 노드 의 전구: 이 노드 의 최대 노드 보다 작고 전구 에는 오른쪽 서브 트 리 노드 의 후계 가 없다. 이 노드 의 최소 노드 보다 크다.그 다음 에 왼쪽 트 리 가 알 지 못 한 후에 우 리 는 방법 을 논술 할 수 있다. 첫 번 째 방법 은 이 노드 의 앞 구 를 찾 은 다음 에 그의 값 을 삭제 할 노드 에 부여 하고 마지막 으로 이 앞 구 를 삭제 하면 된다.두 번 째 방법 은 첫 번 째 와 유사 하 다. 바로 이 노드 의 후계 자 를 찾 은 다음 에 삭제 할 노드 에 값 을 부여 하고 마지막 으로 이 후계 자 를 삭제 하면 된다.여기 에는 전구 에 오른쪽 트 리 가 없고, 후계 에 왼쪽 트 리 의 특성 이 없 으 니, 구체 적 으로 코드 를 보 세 요.

void BST::Delete_Node(Node **root, int x){
    Node *p = *root;
    Node *fa = *root;
    while(p){
        if(p->val == x){
            break;
        }
        fa = p;
        if(p->val > x){
            p = p->left;
        }
        else{
            p = p->right;
        }
    }
    if(p == NULL){
        printf("%d is not found!
", x);
        return;
    }
    if(p->left == NULL && p->right == NULL){// p     
        if(p == *root){//p    
            *root = NULL;
        }
        else if(fa->left == p){
            fa->left = NULL;
        }
        else{
            fa->right = NULL;
        }
        delete p;
    }
    else if(p->left == NULL || p->right == NULL){// p     
        if(p == *root){
            if(p->left != NULL){
                *root = p->left;
            }
            else{
                *root = p->right;
            }
        }
        else{
            if(fa->left == p){
                if(p->left != NULL){
                    fa->left = p->left;
                }
                else{
                    fa->left = p->right;
                }
            }
            else{
                if(p->left != NULL){
                    fa->right = p->left;
                }
                else{
                    fa->right = p->right;
                }
            }
        }
        delete p;
    }
    else{// p     
        Node *parent = p;
        Node *child = p->right;
        while(child->left){
            parent = child;
            child = child->left;
        }
        p->val = child->val;
        if(parent == p){
            p->right = child->right;
        }
        else{
            parent->left = child->right;
        }
        delete child;
    }
}

프로그램 총람:

#include 
using namespace std;

class Node{
public:
    int val;
    Node *left, *right;
    Node() {}
    Node(int val) : val(val), left(NULL), right(NULL) {}
};

class BST{
private:
    Node *root;
    void Recursion_Insert_Node(Node *&node, int x);//      
    void Non_Recursion_Insert_Node(Node **node, int x);//       
    Node *Recursion_Find_Node(Node *node, int x);//      
    Node *Non_Recursion_Find_Node(Node *root, int x);//       
    void Delete_Node(Node **root, int x);//    
    void preOrder_Traverse(Node *root);//    
    void inOrder_Traverse(Node *root);//    
    void postOrder_Traversal(Node *root);//    
    void Delete_BST(Node *node);//    
public:
    BST();
    ~BST();
    void Create_BST(int *num, int n);//  BST
    Node *Find_Node(int x);
    void Delete_Node(int x);
    void preOrder_Traverse();
    void inOrder_Traverse();
    void postOrder_Traversal();
};

BST::BST(){
    this->root = NULL;
}

void BST::Create_BST(int *num, int n){
    for(int i = 0; i < n; i++){
        // Recursion_Insert_Node(this->root, num[i]);
        Non_Recursion_Insert_Node(&this->root, num[i]);
    }
}

void BST::Recursion_Insert_Node(Node *&node, int x){
    if(node == NULL){
        node = new Node(x);
    }
    else if(node->val > x){
        Recursion_Insert_Node(node->left, x);
    }
    else if(node->val < x){
        Recursion_Insert_Node(node->right, x);
    }
}

void BST::Non_Recursion_Insert_Node(Node **root, int x){
    Node *p = *root;
    Node *fa = *root;
    while(p){
        if(p->val == x){
            printf("%d is already exist!
", x);
            return;
        }
        fa = p;
        if(p->val > x){
            p = p->left;
        }
        else{
            p = p->right;
        }
    }
    if(fa == NULL){
        *root = new Node(x);
    }
    else if(fa->val > x){
        fa->left = new Node(x);
    }
    else{
        fa->right = new Node(x);
    }
}

void BST::Delete_Node(int x){
    Delete_Node(&this->root, x);
}

void BST::Delete_Node(Node **root, int x){
    Node *p = *root;
    Node *fa = *root;
    while(p){
        if(p->val == x){
            break;
        }
        fa = p;
        if(p->val > x){
            p = p->left;
        }
        else{
            p = p->right;
        }
    }
    if(p == NULL){
        printf("%d is not found!
", x);
        return;
    }
    if(p->left == NULL && p->right == NULL){// p     
        if(p == *root){//p    
            *root = NULL;
        }
        else if(fa->left == p){
            fa->left = NULL;
        }
        else{
            fa->right = NULL;
        }
        delete p;
    }
    else if(p->left == NULL || p->right == NULL){// p     
        if(p == *root){
            if(p->left != NULL){
                *root = p->left;
            }
            else{
                *root = p->right;
            }
        }
        else{
            if(fa->left == p){
                if(p->left != NULL){
                    fa->left = p->left;
                }
                else{
                    fa->left = p->right;
                }
            }
            else{
                if(p->left != NULL){
                    fa->right = p->left;
                }
                else{
                    fa->right = p->right;
                }
            }
        }
        delete p;
    }
    else{// p     
        Node *parent = p;
        Node *child = p->right;
        while(child->left){
            parent = child;
            child = child->left;
        }
        p->val = child->val;
        if(parent == p){
            p->right = child->right;
        }
        else{
            parent->left = child->right;
        }
        delete child;
    }
}

Node *BST::Find_Node(int x){
    // return Recursion_Find_Node(this->root, x);
    return Non_Recursion_Find_Node(this->root, x);
}

void BST::preOrder_Traverse(){
    preOrder_Traverse(this->root);
}

void BST::inOrder_Traverse(){
    inOrder_Traverse(this->root);
}

void BST::postOrder_Traversal(){
    postOrder_Traversal(this->root);
}

Node *BST::Recursion_Find_Node(Node *node, int x){
    if(node == NULL)
        return NULL;
    if(node->val == x)
        return node;
    if(node->val > x)
        return Recursion_Find_Node(node->left, x);
    else
        return Recursion_Find_Node(node->right, x);
}

Node *BST::Non_Recursion_Find_Node(Node *node, int x){
    if(node == NULL)
        return NULL;
    while(node){
        if(node->val == x)
            return node;
        else if(node->val > x)
            node = node->left;
        else
            node = node->right;
    }
    return node;
}

void BST::preOrder_Traverse(Node *root){
    if(root != NULL){
        printf("%d ", root->val);
        preOrder_Traverse(root->left);
        preOrder_Traverse(root->right);
    }
}

void BST::inOrder_Traverse(Node *root){
    if(root != NULL){
        inOrder_Traverse(root->left);
        printf("%d ", root->val);
        inOrder_Traverse(root->right);
    }
}

void BST::postOrder_Traversal(Node *root){
    if(root != NULL){
        postOrder_Traversal(root->left);
        postOrder_Traversal(root->right);
        printf("%d ", root->val);
    }
}

void BST::Delete_BST(Node *node){
    if(node == NULL)
        return;
    if(node->left != NULL)
        Delete_BST(node->left);
    if(node->right != NULL)
        Delete_BST(node->right);
    delete node;
}

BST::~BST(){
    Delete_BST(this->root);
}

int main()
{
    return 0;
}

코드 같은 거 말 하지 마 세 요. T.