[C++] BST 구현

코드

- 노드 생성

typedef struct node
{
    int i;
    struct node *left;
    struct node* right;
}node;

- BST에 삽입

void add(int n)
{
    node* newnode = (node*)malloc(sizeof(node)); //노드 생성
    newnode->i=n;
    newnode->left=newnode->right=0;

    if(root = 0) //BST가 비어있는 경우
    {
        root= newnode;
        return;
    }
    node*cur = root;
    while(1) //BST가 비어있지 않은 경우
    {
        if(newnode->i<cur->i) //넣으려고 하는 노드가 현재 가리키는 노드의 값보다 작다면
        {
            if(cur->left==0) //왼쪽에 들어가야 하므로 왼쪽으로 이동
            {
                cur->left=newnode;
                return;
            }
            else cur=cur->left;
        }
        else //넣으려고 하는 노드가 현재 가리키는 노드의 값보다 크다면
        {
            if(cur->right==0) //오른쪽에 들어가야 하므로 오른쪽으로 이동
            {
                cur->right=newnode;
                return;
            }
            else cur=cur->right;
        }
    }
}

 

- BST에서 제거

node* removenode(node*no,int key)
{
    if(no==0)
    {
        return 0;
    }
    if(key==no->i)
    {
        if(no->left==0 && no->right==0)
        {
            free(no);
            return 0;
        }
        else if(no->left==0) //오른쪽 자식만
        {
            node*tmp = no->right;
            free(no);
            return tmp;
        }
        else if(no->right==0) //왼쪽 자식만
        {
            node*tmp = no->left;
            free(no);
            return tmp;
        }
        else
        {
            node*toreplace = findLeast(no->right);
            no->i=toreplace->i;
            no->right=removenode(no->right, toreplace->i);
            return no;
        }
    }
    else if(key<no->i)
    {
        //왼쪽으로
        no->left=removenode(no->left,key);
        return no;
    }
    else
    {
        no->right=removenode(no->right,key);
        return no;
    }
}

 

- 작은 수 찾기

node* findLeast(node *n)
{
    node *cur = n;
    while(cur->left!=0)
    {
    	cur=cur->left;
    }
    return cur;
}

 

- 전위 순회

void preorder(node *n) //부모->왼쪽->오른쪽 순서로 순회
{
    if(n==0) return;
    cout<<n->i<<endl;
    preorder(n->left);
    preorder(n->right);
}

- 중위 순회

void inorder(node *n) //왼쪽->부모->오른쪽 순서로 순회
{
    if(n==0) return;
    inorder(n->left);
    cout<<n->i<<endl;
    inorder(n->right);
}

- 후위 순회

void postorder(node *n) //왼쪽->오른쪽->부모 순서로 순회
{
    if(n==0) return;
    postorder(n->left);
    postorder(n->right);
    cout<<n->i<<endl;
}