두 갈래 정렬 트리(BST) 기본 작업

두 갈래 정렬 트리(BST) 기본 작업

  • 두 갈래 나무의 구조 정의
  • 두 갈래 정렬 트리의 삽입
  • 두 갈래 정렬 트리를 만든다
  • 나무 하나가 BST인지 아닌지를 판단한다

  • 두 갈래 나무의 구조 정의

    typedef struct BiTNode
    {
        char data;
        struct BiTNode *lchild, *rchild, *parent;
    }BiTNode, *BiTree;
    

    두 갈래 정렬 트리 삽입

    int BST_Insert(BiTree &T, int key)      // 
    {
        if(T == NULL)
        {
            T = (BiTree)malloc(sizeof(BiTNode));
            T->data = key;
            T->lchild = NULL;
            T->rchild = NULL;
            return 1;           // 
        }
        else if(key == T->data)
        {
            return 0;           // , 
        }
        else
        {
            if(key < T->data)   // 
            {
                return BST_Insert(T->lchild, key);
            }
            else                // 
            {
                return BST_Insert(T->rchild, key);
            }
        }
    }
    

    두 갈래 정렬 트리 만들기

    void Create_BST(BiTree &T, int str[], int n)   // 
    {
        T = NULL;
    
        int i = 0;
    
        while(i<n)
        {
            BST_Insert(T, str[i]);
            i++;
        }
    }
    

    트리가 BST인지 여부를 판단합니다.

    int pred = -32767;              //pre 
    int JudgeBST(BiTree T)          // BST
    {
        int b1, b2;
        if(!T)
        {
            return 1;
        }
        else
        {
            b1 = JudgeBST(T->lchild);  // BST
            if(b1 == 0 || pred>T->data)
            {
                return 0;
            }
            pred = T->data;           // 
            b2 = JudgeBST(T->rchild);  // 
            return b2;
        }
    }
    

    좋은 웹페이지 즐겨찾기