ํฌ๋ํํค ์ ๊ธ WEEK5 Day 38 -BST
๐24.2.14
์ค๋๋ถ๋ก ๊ณผ์ ๋ค ๋๋๋ค
BST ๋ถ๋ถ ์ด๋ ค์์ ๊ฑฐ์ ๋ค ๋ต ๋ณด๊ฑฐ๋ GPT ๋๋ ค์ ํ์๋ค....
๊ณผ์ ๋๋ด๊ณ ํ๋ก๊ทธ๋๋จธ์ค ํ๊ณ ๊ฐ์ ๋ฉ๋ชจ๋ฆฌ ๊ณต๋ถํ๋ .
levelOrderTraversal
๋ ๋ฒจ ์์ผ๋ก ํธ๋ฆฌ๋ฅผ ์ํํ๋ฉด์ ๋ ธ๋์ ๊ฐ์ ์ถ๋ ฅํ๋ค.
void levelOrderTraversal(BSTNode* root)
{
Queue q; //์ํํ๋ฉฐ ๋ฐฉ๋ฌธํ ๋
ธ๋๋ค์ ์์๋ก ์ ์ฅ
q.head = NULL;
q.tail = NULL;
BSTNode *temp;
temp = root;
if(temp == NULL)
return;
else
{
enqueue(&q.head, &q.tail, temp); //๋ฃจํธ ๋
ธ๋๋ฅผ ํ์ ์ฝ์ด
while(!isEmpty(q.head))
{
temp = dequeue(&q.head, &q.tail); //ํ์์ ๋
ธ๋๋ฅผ ๊บผ๋ด ํด๋น ๋
ธ๋์ ๊ฐ ์ถ๋ ฅ
printf("%d ",temp->item);
if(temp->left != NULL)
enqueue(&q.head, &q.tail, temp->left);
if(temp->right != NULL)
enqueue(&q.head, &q.tail, temp->right);
}
}
}
inOrderIternative
์คํ์ ์ฌ์ฉํ์ฌ ์ด์งํ์ ํธ๋ฆฌ๋ฅผ ์ค์ ์ํํ๋ค. ( left -> root -> right)
void inOrderTraversal(BSTNode *root)
{
Stack s;
s.top = NULL;
BSTNode *temp;
temp = root;
if(temp == NULL) return;
while(1)
{
if(temp != NULL)
{
push(&s,temp);
temp = temp->left; //์ผ์ชฝ ์์ ๋
ธ๋ ์ด๋
}
else
{
if(!isEmpty(&s))
{
temp = pop(&s);
printf("%d ", temp->item);
temp= temp->right; //์ด์ ์ค๋ฅธ์ชฝ ํ์ธ
}
else
break;
}
}
}
preOrderIternative
์คํ์ ์ฌ์ฉํ์ฌ ์ ์์ํํ๋ค. (root -> left -> right)
void preOrderIterative(BSTNode *root)
{
Stack s;
s.top = NULL;
BSTNode *temp;
temp = root;
if(temp == NULL) return;
else
{
push(&s, temp);
while(!isEmpty(&s))
{
temp = pop(&s);
printf("%d ", temp->item);
if(temp->right != NULL)
push(&s,temp->right);
if(temp->left != NULL)
push(&s,temp->left);
}
}
}
postOrderIternativeS1
์คํ์ ์ฌ์ฉํด์ ํ์์ํํ๋ค. (left -> right -> root)
์คํ์ top์ ์๋ ๋ ธ๋์ ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๋ฅผ ํ์ธํ๊ณ , ๋ง์ฝ ์ด ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๊ฐ null์ด๊ฑฐ๋ ์ด์ ์ ๋ฐฉ๋ฌธํ๋ ๋ ธ๋์ ๊ฐ๋ค๋ฉด, ์คํ์ top์ ์๋ ๋ ธ๋๋ฅผ popํ๊ณ ๊ทธ ๊ฐ์ ์ถ๋ ฅํ๋ค.
๊ทธ๋ฆฌ๊ณ ์ด ๋ ธ๋๋ฅผ ์ด์ ์ ๋ฐฉ๋ฌธํ๋ ๋ ธ๋๋ก ์ค์ ํ๋ค. ์ด ๊ณผ์ ์ ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ๋ฅผ ์ด๋ฏธ ๋ฐฉ๋ฌธํ ํ์๋ ๋ฃจํธ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๊ธฐ ์ํ ๊ฒ์ด๋ค.
๋ง์ฝ ์คํ์ top์ ์๋ ๋ ธ๋์ ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๊ฐ ์ด์ ์ ๋ฐฉ๋ฌธํ ๋ ธ๋์ ๋ค๋ฅด๋ค๋ฉด, ํ์ฌ ๋ ธ๋๋ฅผ ์ด ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๋ก ์ค์ ํ๋ค. ์ด ๊ณผ์ ์ ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ๋ฅผ ๋ฐฉ๋ฌธํ๊ธฐ ์ํ ๊ฒ์ด๋ค.
void postOrderIterativeS1(BSTNode *root)
{
if (root == NULL)
return;
Stack s;
s.top = NULL;
BSTNode *current = root; //ํ์ฌ ๋ฐฉ๋ฌธ ์ค์ธ ๋
ธ๋
BSTNode *prev = NULL; //์ด์ ์ ๋ฐฉ๋ฌธํ๋ ๋
ธ๋
while (current != NULL || !isEmpty(&s))
{
if (current != NULL)
{
push(&s, current);
current = current->left; //์ผ์ชฝ ์์ ๋
ธ๋๋ก ์ด๋
}
else
{
BSTNode *temp = peek(&s)->right; //์คํ์ top์ ์๋ ๋
ธ๋์ ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋ ํ์ธ
if (temp == NULL || temp == prev)
{
temp = pop(&s);
printf("%d ", temp->item);
prev = temp;
}
else
{
current = temp;
}
}
}
}
postOrderIterativeS2
์คํ 2๊ฐ๋ฅผ ์ฌ์ฉํด์ ํ์ ์ํํ๋ค
์ฒซ ๋ฒ์งธ ์คํ์ด ๋น์ด์์ง ์์ ๋์, ์คํ์ top์ ์๋ ๋ ธ๋๋ฅผ popํ์ฌ ๋๋ฒ์งธ ์คํ(s2)์ pushํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด ๋ ธ๋์ ์ผ์ชฝ ์์ ๋ ธ๋์ ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๊ฐ ์๋ค๋ฉด, ๊ฐ๊ฐ ์ฒซ ๋ฒ์งธ ์คํ์ pushํ๋ค. ์ด ๊ณผ์ ์ s1์ด ๋น ๋๊น์ง ๋ฐ๋ณตํ๋ค. ์ด๋ ๊ฒ ํ๋ฉด s2์๋ ๋ ธ๋๋ค์ด ํ์ ์ํ ์์์ ์ญ์์ผ๋ก ์ ์ฅ๋๋ค.
-> s2๋ ํ์ ์ํ ์์๋๋ก ์ถ๋ ฅ๋๋ค.
void postOrderIterativeS2(BSTNode *root)
{
Stack s1;
Stack s2;
s1.top = NULL;
s2.top = NULL;
BSTNode *temp;
temp = root;
if(temp ==NULL) return;
else
{
push(&s1,temp); //๋ฃจํธ ๋
ธ๋ push
while(!isEmpty(&s1))
{
temp = pop(&s1);
push(&s2, temp);
if(temp->left !=NULL)
push(&s1,temp->left);
if(temp->right!=NULL)
push(&s1,temp->right);
}
while(!isEmpty(&s2))
{
temp = pop(&s2);
printf("%d ", temp->item);
}
}
}