Bài 5. Cây nhị phân

Mô hình

DATA VISUALIZATION

Mô hình tại đây

Lý thuyết

Source Code

treeBST.h

CẤU TRÚC

struct Node{
    int data;
    struct Node *Left;
    struct Node *Right;
};
typedef struct Node *Tree;

KHỞI TẠO RỘNG TREE

void makeNullTree(Tree *root){
    (*root) = NULL;
}

THÊM NODE VÀO TRONG TREE

void insertNode(int x,Tree *root){
    Tree temp = *root;
    if(temp == NULL){
        temp = (struct Node*)malloc(sizeof(struct Node));
        temp->data = x;
        temp->Left = NULL;
        temp->Right = NULL;
        *root = temp;
    }
    else{
        if(temp->data == x){
            return;
        }
        else if(temp->data > x){
            insertNode(x,&temp->Left);
        }
        else{
            insertNode(x,&temp->Right);
        }
    }
}

TẠO TREE

Tree createTree(){
    Tree root;
    int n;
    scanf("%d",&n);
    makeNullTree(&root);
    int x;
    for (int i = 0; i < n; i++){
        scanf("%d",&x);
        insertNode(x,&root);
    }
    return root;
}

3 CÁCH DUYỆT TREE

// duyệt tiền tự
void NLR(Tree root){
    if(root != NULL){
        printf("%d ",root->data);
        NLR(root->Left);
        NLR(root->Right);
    }
}
// duyệt trung tự
void LNR(Tree root){
    if(root != NULL){
        LNR(root->Left);
        printf("%d ",root->data);
        LNR(root->Right);
    }
}
// duyệt hậu tự
void LRN(Tree root){
    if(root != NULL){
        LRN(root->Left);
        LRN(root->Right);
        printf("%d ",root->data);
    }
}

TRẢ VỀ NODE LỚN HOẶC NHỎ NHẤT TRONG TREE

Tree minNode(Tree root){
    while (root->Left != NULL){
        root = root->Left;
    }
    return root;
}
Tree maxNode(Tree root){
    while (root->Right != NULL){
        root = root->Right;
    }
    return root;
}

TIP

TRẢ VỀ NODE PHÍA TRƯỚC VÀ NODE PHÍA SAU NODE X

Tree getPrevious(int x,Tree root){
    Tree prevNode = NULL;
    while (root != NULL){
        if(root->data > x){
            root = root->Left;
        }
        else if(root->data < x){
            prevNode = root;
            root = root->Right;
        }
        else if(root->Left == NULL){
            return prevNode;
        }
        else{
            return maxNode(root->Left);
        }
    }
    return NULL;
}

Tree getNext(int x,Tree root){
    int n = 0;
    int M[50];
    int pos;
    LNRtoArray(&n,M,root);
    for (int i = 0; i < n; i++){
        if(x == M[i]){
            pos = i;
            break;
        }
    }
    Tree result = searchNode(M[pos+1],root);
    return result;
}

XOÁ MỘT NODE TRONG TREE

void searchStandFor(Tree *node1,Tree *node2){
    if((*node2)->Left != NULL){
        searchStandFor(&(*node1),&(*node2)->Left);
    }
    else{
        (*node1)->data = (*node2)->data;
        (*node1) = (*node2);
        (*node2) = (*node2)->Right;
    }
}
int deleteNode(int x,Tree *root){
    Tree temp = *root;
    if(temp == NULL){
        return 0;
    }
    if(temp->data > x){
        return deleteNode(x,&temp->Left);
    }
    else if(temp->data < x){
        return deleteNode(x,&temp->Right);
    }
    else{
        Tree p = *root;
        if(temp->Left == NULL){
            temp = temp->Right;
        }
        else{
            if(temp->Right == NULL){
                temp = temp->Left;
            }
            else{
                searchStandFor(&p,&(*root)->Right);
            }
        }
        p = NULL;
        *root = temp;
    }
    return 1;
}

TRẢ VỀ CHIỀU CAO CỦA TREE

int getHeight(Tree root){
    if(root == NULL){
        return -1;
    }
    else{
        int heightLeft = getHeight(root->Left);
        int heightRight = getHeight(root->Right);
        if(heightLeft > heightRight)
            return heightLeft+1;
        else
            return heightRight+1;
    }
}

HIỂN THỊ ĐƯỜNG ĐI CỦA TREE

void printPath(int x,Tree root){
    while (root != NULL){
        if(root->data > x){
            printf("%d ",root->data);
            root = root->Left;
        }
        else if(root->data < x){
            printf("%d ", root->data);
            root = root->Right;
        }
        else{
            //root->data == x
            printf("%d -> Tim thay",root->data);
            return;
        }
    }
    printf(" -> Khong thay");
}