À̺Р³ª¹«¿Í »¡°­ °ËÁ¤ ³ª¹« + ¿ë¾î »öÀÎ »ý¼º ÇÁ·Î±×·¥

tree´Â ¹ü¿ëÀûÀ¸·Î´Â Á·º¸³ª µð·ºÅ丮 ±¸Á¶Ã³·³ ¹º°¡ °èÃþÀ̶ó´Â ¼Ó¼ºÀ» Áö´Ñ ü°è¸¦ ±â¼úÇϱâ À§ÇØ »ç¿ëµÇ´Â °³³äÀÌÁö¸¸, Àü»êÇп¡¼­´Â tree¿¡ Ư¼öÇÑ Á¶°ÇÀ» µÎ¾î À̸¦ ¹ü¿ëÀûÀÎ ÀڷᱸÁ¶ ¸ðµ¨·Î »ç¿ëÇϱ⵵ ÇÕ´Ï´Ù. ³ª¹« Áß¿¡¼­ »ç¶÷ÀÇ ¾ç ÆÈó·³ ÇÑ ³ëµå ¾Æ·¡¿¡ °¡Áö°¡ ÃÖ´ë µÎ °³±îÁö¸¸ Á¸ÀçÇÏ´Â ³ª¹«¸¦ À̺Р³ª¹«¶ó°í Çϸç, ¿ÞÂÊ °¡Áö¿¡´Â ¾ðÁ¦³ª ºÎ¸ðº¸´Ù ÀÛÀº °ª¸¸ Á¸ÀçÇÏ°í ¿À¸¥ÂÊ °¡Áö¿¡´Â ¾ðÁ¦³ª ºÎ¸ðº¸´Ù Å« °ª¸¸ Á¸ÀçÇÏ´Â ³ª¹«¸¦ À̺Р°Ë»ö ³ª¹«(binary search tree)¶ó°í ÇÕ´Ï´Ù.

tree´Â ¹è¿­À̳ª ¿¬°á ¸®½ºÆ®Ã³·³ ¼±ÇüÀûÀÎ ÀڷᱸÁ¶°¡ ¾Æ´Ï¾î¼­ ÀÓÀÇÀÇ ¡®À妽º¡¯¿¡ ´ëÇÑ random access°¡ °ï¶õÇÏ°í ´Ù·ç±â°¡ ±î´Ù·Î¿ö º¸ÀÌÁö¸¸, »ðÀÔ°ú »èÁ¦°¡ ºó¹øÇÏ°Ô ¹ß»ýÇϸ鼭µµ ÀÏ°üµÈ Á¤·Ä ¼ø¼­ À¯Áö¿Í ºü¸¥ °Ë»ö ¼Óµµ°¡ ¿ä±¸µÇ´Â »óȲ¿¡¼­ ¸Å¿ì ÁÁÀº ¼º´ÉÀ» ¹ßÈÖÇÕ´Ï´Ù. dynamic setÀ» ±¸ÇöÇϴµ¥ ÃÖÀûÀÇ ÀÚ·áÇüÀÔ´Ï´Ù.

ÀÌ ÇÁ·Î±×·¥¿¡¼­´Â ´Ü¼øÇÑ À̺Р°Ë»ö ³ª¹«¸¦ CTree¶ó´Â ÅÛÇø´ Ŭ·¡½º·Î ¸ÕÀú ±¸ÇöÇß½À´Ï´Ù. ÀÌ°É ±¸ÇöÇÏ´Â °ÍÀº ±×¸® ¾î·ÆÁö ¾Ê½À´Ï´Ù. ÄÁÅ×ÀÌ³Ê ´ë»óÀÌ µÇ´Â ŸÀÔÀº ==(µ¿µî), <(ºñ±³) ¿¬»ê¸¸ »óÈ£ Á¤ÀǵǾî ÀÖÀ¸¸é µË´Ï´Ù.

ÇÏÁö¸¸ ¾Æ¹«·± ÀÚü Á¦¾î°¡ ¾ø´Â À̺Р³ª¹«´Â °°Àº ÀÚ·á¶ó°í Çصµ ÀÚ·á°¡ ÀÔ·ÂµÈ ¼ø¼­¿¡ µû¶ó ³ª¹«ÀÇ ¸ð¾çÀÌ Å©°Ô ´Þ¶óÁö¸ç, ƯÈ÷ Å©±â°¡ ¼øÂ÷ÀûÀ¸·Î Ä¿Áö°Å³ª ÀÛ¾ÆÁö±â¸¸ ÇÏ´Â ÀÚ·á°¡ ÀÔ·ÂµÇ¸é ³ª¹«ÀÇ ±íÀÌ°¡ ÇÑÂÊ ³ëµå·Î¸¸ ½ò¸®¸é¼­ ¿¬°á ¸®½ºÆ®¿Í Á¶±Ýµµ ´Ù¸¦ ¹Ù ¾ø´Â ºñÈ¿À²ÀûÀÎ ÇüÅ°¡ µË´Ï´Ù. Äü Á¤·ÄÀÌ ÃÖ¾ÇÀÇ »óȲ¿¡ ½Ã°£ º¹Àâµµ O(n2)¿Í ¸Þ¸ð¸® º¹Àâµµ O(n)ÀÌ µÉ ¼ö ÀÖ´Â °Í°ú °°Àº ÀÌÄ¡ÀÔ´Ï´Ù.

½º½º·Î ±ÕÇü Àâ´Â ³ª¹«

ÀÌ ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇØ ÀڷᱸÁ¶ ±³ÀçÀÇ ÇÑ⠵޺κп¡ ³ª¿À´Â °ÍÀÌ ¹Ù·Î ½º½º·Î ±ÕÇü Àâ´Â(self-balancing) ³ª¹«ÀÔ´Ï´Ù. °¢ ³ëµå¸¶´Ù º»µð µ¥ÀÌÅÍ ¿Ü¿¡ ³»ºÎÀûÀ¸·Î »ç¿ëÇÏ´Â ºÎ°¡Á¤º¸¸¦ Ãß°¡ÇÏ°í, ±×¿¡ ¸ÂÃç ÀÚ·áÀÇ »ðÀÔ/»èÁ¦ ½Ã¿¡ ÃÖ´ëÇÑ °¢ ³ëµåµéÀÇ ÁÂ¿ì ³ëµå°¡ ±ÕÇü ÀÖ°Ô »ç¿ëµÇ°í ³ª¹«ÀÇ Àüü ±íÀÌ°¡ nÀÌ ¾Æ´Ñ log n¿¡ ºñ·ÊÇϵµ·Ï ºÎ°¡ÀÛ¾÷À» ÇÏ´Â °ÍÀÔ´Ï´Ù. ±×·¡¼­ ¾Æ±î¿Í °°Àº ÃÖ¾ÇÀÇ ¼ø¼­·Î µ¥ÀÌÅÍ°¡ µé¾î¿À´õ¶óµµ »ðÀÔ, »èÁ¦, °Ë»öÀÌ ¸ðµÎ ¾ðÁ¦³ª log nÀÇ ½Ã°£ º¹Àâµµ°¡ º¸ÀåµÇµµ·Ï ÇÑ °ÍÀÌ ½º½º·Î ±ÕÇü Àâ´Â ³ª¹«ÀÇ Æ¯Â¡ÀÔ´Ï´Ù. ±×¾ß¸»·Î ¸¸´É ÀڷᱸÁ¶°¡ ¾Æ´Ò ¼ö ¾ø½À´Ï´Ù.

ÀÌ·± ÀڷᱸÁ¶¿¡ ´ëÇÑ ¼Ò°³°¡ µÞºÎºÐ¿¡ ³ª¿À´Â ÀÌÀ¯´Â ±× ºÎ°¡ÀÛ¾÷À̶õ °ÍÀÌ º¹ÀâÇÏ°í ÀÌÇØÇÏ±â ²Ï ¾î·Æ±â ¶§¹®ÀÔ´Ï´Ù. À̺Р°Ë»ö ³ª¹«ÀÇ ±âº»ÀûÀΠƯ¡À» ±×´ë·Î À¯ÁöÇϸ鼭 ÀÚ°¡±ÕÇüÀÌ ±¸ÇöµÈ ³ª¹«ÀÇ ´ëÇ¥ÀûÀÎ ¿¹´Â AVL ³ª¹«¿Í »¡°­-°ËÁ¤ ³ª¹«ÀÔ´Ï´Ù. ¿©±â¼­´Â »¡°­-°ËÁ¤ ³ª¹«¸¦ CTree¿¡ À̾î CTreeEx¶ó´Â ÅÛÇø´ Ŭ·¡½º·Î ±¸ÇöÇß½À´Ï´Ù. µÎ Ŭ·¡½º´Â »ó¼Ó °ü°è´Â ¾Æ´ÏÁö¸¸ »ç¿ë¹ýÀº ¿ÏÀüÈ÷ °°½À´Ï´Ù. Insert, Delete, Lookup, GetCount, ResetContent Á¤µµ¸¸ ¾Ë¸é µÇ°í °¢ ÇÔ¼öµéÀÌ ÇÏ´Â ÀÏ¿¡ ´ëÇؼ­´Â º°µµÀÇ ¼³¸íÀÌ ÇÊ¿ä ¾øÀ» °ÍÀÔ´Ï´Ù.

»¡°­-°ËÁ¤ ³ª¹«´Â ÀÚ°¡±ÕÇüÀ» À¯ÁöÇϱâ À§ÇØ °¢ ³ëµå¸¶´Ù µ¡ºÙÀÌ´Â Ãß°¡ Á¤º¸·®ÀÌ »¡°­-°ËÁ¤À̶ó´Â 1ºñÆ®¿¡ ºÒ°úÇϸç, AVL ³ª¹«º¸´Ù ±¸ÇöÇϱ⠽±°í »ðÀÔ/»èÁ¦ ½ÃÀÇ ºÎ´ãµµ ´õ Àû½À´Ï´Ù. AVL ³ª¹«¸¸Ä¡ öÀúÇÏ°Ô ±ÕÇüÀ» Àâ¾Æ ÁÖÁö´Â ¸øÇÏÁö¸¸, ÀÌ´Â ºñ·Ê»ó¼ö ¼öÁØÀÇ Â÷ÀÌÀÏ »Ó ³ª¹«ÀÇ Æò±Õ ±íÀÌ°¡ log n¿¡ ºñ·ÊÇÑ´Ù´Â °ÍÀº º¯ÇÔ¾øÀÌ º¸ÀåµË´Ï´Ù. STL¿¡¼­ map, set µîÀÇ ÄÁÅ×À̳ʵµ ³»ºÎÀûÀ¸·Î´Â ´ëºÎºÐ »¡°­-°ËÁ¤ ³ª¹«¸¦ »ç¿ëÇÏ¿© ±¸ÇöµÇ¾î ÀÖ½À´Ï´Ù.

»¡°­-°ËÁ¤ ³ª¹«ÀÇ »ðÀÔ, »èÁ¦ °úÁ¤À» ±³°ú¼­ÀûÀ¸·Î ¾Æ·¡¿¡¼­ À§·Î(bottom-up) ±¸ÇöÇßÀ» °æ¿ì Àç±ÍÈ£ÃâÀÌ ÀϾ°Å³ª º°µµÀÇ ½ºÅà ¹è¿­, ¾Æ´Ï¸é ½ÉÁö¾î ³ëµå ±¸Á¶Ã¼¸¶´Ù ºÎ¸ð ³ëµå Æ÷ÀÎÅÍ°¡ ÇÊ¿äÇØÁý´Ï´Ù. ½ÇÁ¦·Î STLÀÌ »ç¿ëÇÏ´Â »¡°­-°ËÁ¤ ³ª¹«ÀÇ ³ëµå ±¸Á¶Ã¼¿¡´Â ºÎ¸ð ³ëµå¿¡ ´ëÇÑ Æ÷ÀÎÅÍ°¡ ÀÖ½À´Ï´Ù. STLÀÇ ½ºÆå¿¡ µû¶ó iterator·Î ³ª¹« ¾ÈÀÇ °¢ ¿ø¼ÒµéÀ» º°µµÀÇ ½ºÅà ¾øÀÌ ¼øȸÇÏ·Á¸é ±×°Ô ¹Ýµå½Ã ÇÊ¿äÇϱ⠶§¹®ÀÔ´Ï´Ù. ÇÏÁö¸¸ ÀÌ ÇÁ·Î±×·¥Àº Àç±ÍÈ£Ãâ ¾øÀÌ ´Ü¼ø À̺Р³ª¹«¿¡¼­ »ðÀÔ, »èÁ¦¸¦ ÇϵíÀÌ top-down ¹æ½ÄÀ¸·Î ¿ø¼Ò¸¦ ó¸®ÇÏ¸ç ºÎ¸ð ³ëµå Æ÷ÀÎÅ͵µ »ç¿ëÇÏÁö ¾Ê½À´Ï´Ù. ´Ü¼ø À̺Р³ª¹«ÀÇ °£°áÇÔ°ú »¡°­-°ËÁ¤ ³ª¹«ÀÇ ¼º´É¸¸À» ÃëÇß½À´Ï´Ù.

CTreeEx´Â CTree¿Í´Â ´Þ¸®, ¿ø¼Ò¸¦ »èÁ¦ÇÒ ¶§ ÄÁÅ×ÀÌ³Ê ´ë»ó ŸÀÔ¿¡ ´ëÇØ =(´ëÀÔ) ¿¬»êÀ» Ãß°¡·Î »ç¿ëÇÕ´Ï´Ù. ±×·¸±â ¶§¹®¿¡ Delete ÇÔ¼ö±îÁö »ç¿ëÇÏ´Â °æ¿ì ¿©±â¿¡ ´ëÇÑ ÀûÀýÇÑ Ã³¸®°¡ Ãß°¡·Î ÇÊ¿äÇÕ´Ï´Ù.

¿¹Á¦ ÇÁ·Î±×·¥

ÀÌ Å¬·¡½º¸¦ »ç¿ëÇÏ¿© ¿ë¾î »öÀÎ »ý¼º ÇÁ·Î±×·¥À» ¸¸µé¾ú½À´Ï´Ù. ÅؽºÆ® ÆÄÀÏÀ» Âß ÀоîµéÀÎ ÈÄ, ±× ÆÄÀÏ¿¡ µé¾îÀÖ´Â ´Ü¾îµéÀ» ¸ðµÎ ºÐ¸®ÇÏ¿© ¾ËÆĺª ¼øÀ¸·Î Á¤·ÄÇϵÇ, ±× ´Ü¾î°¡ µîÀåÇÑ ÁÙ¹øÈ£¸¦ °°ÀÌ ³ª¿­ÇØ ÁÝ´Ï´Ù. ´Ü¾î´Â Æ®¸® ±¸Á¶ÀÌ°í µîÀå ÁÙ ¹øÈ£´Â °£´ÜÇÑ ´ÜÀÏ ¿¬°á ¸®½ºÆ®·Î ÀúÀåÇÕ´Ï´Ù. Æ®¸®¸¦ »ç¿ëÇÑ ÀÀ¿ë ÇÁ·Î±×·¥À¸·Î À̺¸´Ù ´õ ÀûÀýÇÑ ¿¹´Â ¾ø´Â °Í °°½À´Ï´Ù.

CTree´Â ±¸Çö¸¸ ÇØ ³õ¾Ò°í, ½ÇÁ¦ ÀڷᱸÁ¶´Â À̺¸´Ù ´õ È¿À²ÀûÀÎ ÀÚ°¡±ÕÇü ³ª¹«ÀÎ CTreeEx¸¦ »ç¿ëÇß½À´Ï´Ù.

¼Ò½º ÄÚµå, ½ÇÇà ÆÄÀÏ, ¿¹Á¦ µ¥ÀÌÅÍ ¹Þ±â (src18_tree.zip, 9K)

input.txtÀÇ ÀϺÎ

# Paul, a prisoner of Jesus Christ, and Timothy our brother, unto Philemon our dearly beloved, and fellowlabourer,
And to our beloved Apphia, and Archippus our fellowsoldier, and to the church in thy house:
Grace to you, and peace, from God our Father and the Lord Jesus Christ.
# I thank my God, making mention of thee always in my prayers,
Hearing of thy love and faith, which thou hast toward the Lord Jesus, and toward all saints;

(½Å¾à¼º°æ ºô·¹¸ó¼­ÀÇ ³»¿ëÀÔ´Ï´Ù. ÈÄ·«)

±×¶§ Ãâ·Â °á°úÀÇ ÀϺÎ

a (9): 1 9 15 16 17 22 25
above (1): 16
account (1): 18
acknowledging (1): 6
again (1): 12
aged (1): 9
albeit (1): 19
all (1): 5
also (3): 9 21 22
always (1): 4
Amen (1): 25
an (1): 9
And (1): 2

(ÈÄ·«)


³ª¹« °¢ ¿ø¼Òµé¿¡ ´ëÇÑ ¼øȸ (iteration)

¾Õ¼­ ¸»¾¸µå·ÈµíÀÌ ³ª¹«´Â ¼±ÇüÀûÀÎ ÀڷᱸÁ¶°¡ ¾Æ´Ï±â ¶§¹®¿¡ ¸ðµç ÀڷḦ óÀ½ºÎÅÍ ³¡±îÁö ¼øÂ÷ÀûÀ¸·Î Ž»öÇϱⰡ ±î´Ù·Î¿î ÆíÀÔ´Ï´Ù.

³ª¹«´Â ¼øȸ¸¦ ¾î¶² ¹æ½ÄÀ¸·Î ÇϳĿ¡ µû¶ó¼­ ¿ø¼Ò°¡ ³ª¿­µÇ´Â ¼ø¼­°¡ ´Þ¶óÁø´Ù´Â °ÍÀÌ ¸Å¿ì Èï¹Ì·Ó½À´Ï´Ù. Àڱ⠳ëµåºÎÅÍ ¸ÕÀú Ãâ·ÂÇÑ µÚ ÀÚ½Ä ³ëµå·Î µé¾î°¡´Â °ÍÀ» ÀüÀ§(preorder) ¼øȸ¶ó°í ÇÏ°í, Àڱ⠿ÞÂÊÀÇ ÀÚ½ÄÀ» ¸ÕÀú Ãâ·ÂÇÑ µÚ ³» ¿ø¼Ò¸¦ Ãâ·ÂÇÏ°í ¿À¸¥ÂÊÀ¸·Î Á¦¾î¸¦ ³Ñ±â´Â °ÍÀ» ÁßÀ§(inorder) ¼øȸ, ³¡À¸·Î ÀÚ½ÅÀÇ ¸ðµç ÀڽĺÎÅÍ ¸ÕÀú Ãâ·ÂÇÑ µÚ ÀÚ½ÅÀÌ °¡Áø ¿ø¼Ò¸¦ Ãâ·ÂÇÏ´Â °ÍÀ» ÈÄÀ§(postorder) ¼øȸ¶ó°í ÇÕ´Ï´Ù.

CTree¿¡´Â Àç±ÍÀûÀ¸·Î Äݹé ÇÔ¼ö¸¦ È£ÃâÇÏ´Â InOrder, PreOrder, PostOrder ÇÔ¼ö°¡ Á¤ÀǵǾî ÀÖ½À´Ï´Ù. ±× ¹Ý¸é CTreeEx´Â ÀÚüÀûÀÎ ½ºÅÃÀ» °®Ãá enumerator Ŭ·¡½º°¡ µû·Î Á¤ÀǵǾî À־ while, for¹® ¾È¿¡¼­ ·çÇÁ µ¹µíÀÌ °£´ÜÇÏ°Ô ³ª¹« ¾ÈÀÇ ¿ø¼ÒµéÀ» ¼Â Áß ¾î´À ¼ø¼­´ë·Î³ª ¼øȸÇÒ ¼ö ÀÖ½À´Ï´Ù. ±× ¾²ÀÓ»õ´Â ¾Æ·¡¿Í °°½À´Ï´Ù.

CTree<int> tr; //´Ü¼ø À̺Р°Ë»ö ³ª¹« + Äݹé ÇÔ¼ö ±â¹Ý ¼øȸ
CTreeEx<int> trex; //»¡°­ °ËÁ¤ ³ª¹« + ÀÚü ½ºÅà ±â¹Ý ¼øȸ

const int idd[]={ 11, 5, 16, 2, 9, 13, 20, 1, 3, 8, 10, 12, 14, 17, 23, 0 };
//const int idd[]={ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, 0 };
for(const int *p=idd; *p; p++) { tr.Insert(*p); trex.Insert(*p); }

puts("Àç±ÍÈ£Ãâ¿¡ ÀÇÇÑ ¼øȸ");
puts("PreOrder:");
tr.PreOrder(CallbackFunc, NULL); puts("");

puts("InOrder:");
tr.InOrder(CallbackFunc, NULL); puts("");

puts("Postorder:");
tr.PostOrder(CallbackFunc, NULL); puts(""); puts("");

puts("ºñÀç±Í ¹æ½Ä¿¡ ÀÇÇÑ ¼øȸ");
CTreeEx<int>::CEnumerator en;

puts("PreOrder:");
en.Init(trex, CTreeEx<int>::MIDDLE);
while(en.CanFetch()) printf("%d ", en.GetNextPreOrder()); puts("");

puts("InOrder:");
en.Init(trex, CTreeEx<int>::LEFT_END);
while(en.CanFetch()) printf("%d ", en.GetNextInOrder()); puts("");
en.Init(trex, CTreeEx<int>::RIGHT_END);
while(en.CanFetch()) printf("%d ", en.GetNextInOrder(CTreeEx<int>::RIGHT_END)); puts("");

puts("PostOrder:");
en.Init(trex, CTreeEx<int>::LEFT_END);
while(en.CanFetch()) printf("%d ", en.GetNextPostOrder()); puts("");

Äݹé ÇÔ¼ö´Â,

void CALLBACK CallbaclFunc(int& typ, PVOID context)
{
	printf("%d ", typ);
}

ÇÁ·Î±×·¥ÀÇ ½ÇÇà °á°ú´Â ´ÙÀ½°ú °°½À´Ï´Ù.

Àç±ÍÈ£Ãâ¿¡ ÀÇÇÑ ¼øȸ
PreOrder:
11 5 2 1 3 9 8 10 16 13 12 14 20 17 23
InOrder:
1 2 3 5 8 9 10 11 12 13 14 16 17 20 23
Postorder:
1 3 2 8 10 9 5 12 14 13 17 23 20 16 11

ºñÀç±Í ¹æ½Ä¿¡ ÀÇÇÑ ¼øȸ
PreOrder:
11 5 2 1 3 9 8 10 16 13 12 14 20 17 23
InOrder:
1 2 3 5 8 9 10 11 12 13 14 16 17 20 23
23 20 17 16 14 13 12 11 10 9 8 5 3 2 1
PostOrder:
1 3 2 8 10 9 5 12 14 13 17 23 20 16 11

µ¥ÀÌÅÍ°¡ Äݹé ÇÔ¼ö¸¦ ÅëÇØ ³Ñ¾î¿ÔÀ» ¶§¿¡ ¸ÂÃç¼­ 󸮸¦ ÇØ¾ß ÇÏ´Â Àç±Í ¹öÀüº¸´Ù, ³»°¡ ¿øÇÏ´Â ¶§¿¡ ¾ó¸¶µçÁö ¹Ýº¹¹® ¾È¿¡¼­ µ¥ÀÌÅ͸¦ ²¨³»¿Ã ¼ö ÀÖ´Â ºñÀç±Í ¹öÀüÀÌ »ç¿ëÇϱ⠴õ Æí¸®ÇÒ °ÍÀÔ´Ï´Ù. Init´Â CEnumerator ¿ÀºêÁ§Æ®ÀÇ ³»ºÎ »óŸ¦ °Ë»ö ´ë»óÀÎ CTreeEx¿¡ ¸Â°Ô ÃʱâÈ­ÇÏ´Â ¿ªÇÒÀ» ÇÕ´Ï´Ù. ÁßÀ§³ª ÇÏÀ§ ¼øȸ¸¦ Çϱâ À§Çؼ­´Â Ãʱ⿡ ³ª¹«ÀÇ °¡Àå ÀÛÀº ¿ø¼Ò¿¡ °¡ ÀÖ¾î¾ß ÇÏ°í(¿À¸§Â÷¼ø ±âÁØ), ÀüÀ§ ¼øȸ¸¦ Çϱâ À§Çؼ­´Â ±×³É ³ª¹«ÀÇ root¿¡ ¸ÂÃç ³õÀ¸¸é µË´Ï´Ù. ÀÌ°ÍÀÌ MIDDLE ¶Ç´Â LEFT/RIGHT_END »ó¼öÀÇ ÀǹÌÀÔ´Ï´Ù.

Àç±Í ¹öÀüÀº ¾ðÁ¦³ª ¿À¸§Â÷¼øÀ¸·Î¸¸ ¼øȸÇÒ ¼ö ÀÖ´Â ¹Ý¸é ºñÀç±Í ¹öÀüÀº ¹æÇâÀ» ÁöÁ¤Çؼ­ º¸´Ù½ÃÇÇ ³»¸²Â÷¼ø ¼øȸµµ °¡´ÉÇÕ´Ï´Ù. ±×¸®°í ¼øȸ µµÁß¿¡¶óµµ ¾ó¸¶µçÁö ¼øȸ ¹æ½Ä(Àü/Áß/ÈÄÀ§)°ú ¼øȸ ¹æÇâÀ» ¹Ù²Ü ¼ö ÀÖ½À´Ï´Ù.

À§ÀÇ ¿¹¿¡¼­´Â ³ª¹«°¡ ¿ÏÀüÈ÷ ±ÕÇüÀâÈú ¼ö ÀÖ´Â ¼ø¼­´ë·Î ÀÚ·á°¡ ÀԷµǾú±â ¶§¹®¿¡ µÎ ³ª¹«ÀÇ ¼øȸ °á°ú°¡ ¿ÏÀüÈ÷ °°½À´Ï´Ù. ÇÏÁö¸¸ ÀÚ·á°¡ 1ºÎÅÍ 15±îÁö ¿À¸§Â÷¼øÀ¸·Î ÀÔ·ÂµÈ °æ¿ì ÀÏ¹Ý ³ª¹«¿Í ÀÚ°¡±ÕÇü ³ª¹«´Â ³»ºÎ ±¸Á¶¿¡ Â÷ÀÌ°¡ »ý±â°Ô µË´Ï´Ù.

Àç±ÍÈ£Ãâ¿¡ ÀÇÇÑ ¼øȸ
PreOrder:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
InOrder:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Postorder:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

ºñÀç±Í ¹æ½Ä¿¡ ÀÇÇÑ ¼øȸ
PreOrder:
4 2 1 3 8 6 5 7 10 9 12 11 14 13 15
InOrder:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
PostOrder:
1 3 2 5 7 6 9 11 13 15 14 12 10 8 4

CTree´Â ±íÀÌ°¡ 15ÀÎ ºÒ±ÕÇü ³ª¹«(¿¬°á ¸®½ºÆ®¿Í µ¿ÀÏ)°¡ µÈ ¹Ý¸é, CTreeEx´Â ÃÖ´ë ±íÀÌ°¡ 6ÀÔ´Ï´Ù. ¿ø¼Ò°¡ 15°³ÀÌ´Ï ÀÌ»óÀûÀÎ ÃÖ´ë ±íÀÌÀÇ ÃÖ¼Ò°ªÀº 4ÀÌÁö¿ä.