Хоёртын мод

Компьютерийн ухаанд **хоёртын мод**нь өргөн хэрэглэгддэг өгөгдлийн бүтэц юм. Мод нь зангилаатай байдаг бөгөөд ихдээ 2 хүүхэд зангилаатай байдаг (баруун хүүхэд ба зүүн хүүхэд ).Үндэс (root node) нь модны бүх зангилааны өвөг дээдэс нь болох ба модны аль ч зангилаа толгой зангилаанаас хамааралтай байна. Мод нь толгой зангилаанаас өөр зангилаагүй бол хоосон мод болно.** Хоёртын мод**-онд бүх зангилааны түвшин нь ихэвчлэн хоёр байдаг. n зангилаатай мод байвал n-1 нь мөчир эсвэл түвшин болно. **Хоёртын мод** нь binarySearchTrees эсвэл binaryHeaps- ийн хэрэгжүүлдэг. Энэ нь хайх болон эрэмблэх гэсэн давуу талуудыг зэрэг тусгасан. 

**Хоёртын модны** онцгой хэрэглээ нь K-ary tree юм.

Хоёртын мод нь модны онцгой нэг тохиолдол бөгөөд зангилаа бүр нь хоёроос илүүгүй дэд зангилаатай байдаг. Хэрэв нэг ч зангилаа агуулаагүй бол хоосон мод буюу null мод/зангилаа гэж нэрлэнэ. Зангилааны хоёр дэд зангилааг зүүн дэд загилаа ба баруун дэд зангилаа гэж ялгадаг. Хоёртын модны зангилаа нь нэг эсвэл хоёр хүүхэд зангилаа агуулж болно.

Модны хамгийн сүүлчийн түвшингээс бусад түвшинд дотоод загилаагаар гүйцэд дүүргэсэн бол түүнийг дүүрэн хоёртын мод гэнэ. Дүүрэн хоёртын модны хамгийн сүүлчийн түвшинд зөвхөн гадаад зангилааг агуулна. Харин дотоод зангилааг агуулах хамгийн сүүлчийн түвшингийн зөвхөн баруун талд зарим гадаад зангилаа байвал түүнийг гүйцэд мод гэнэ.

Хоёртын модны өөр нэг онцгой хэлбэр бол ташуу хоёртын мод юм. Ташуу хоёртын модыг зүүн ба баруун ташуу гэж үзэж болно. Хэрэв бүх зангилаа зүүн дэд модгүй бол баруун ташуу, хэрэв бүх зангилаа баруун дэд модгүй бол зүүн ташуу гэнэ. Мөн хөрөөний  шүд хэлбэртэй байж болно. Өөрөөр хэлбэл зангилаа бүр зөвхөн зүүн эсвэл баруун дэд модтой байна гэсэн үг юм. Хоёртын мод нь компьютерийн хэрэглээнд маш өргөн ашиглагдах ба тэрээр дүүрэн эсвэл гүйцэд хоёртын мод байх үед хамгийн үр ашигтай юм.

## Модны үндэс(Definitions for rooted trees)
*Чиглэлтэй холбоос нь эцэгээс хүүрүү чиглэж холбоно.
*Толгой зангилаа нь эцэггүй байна. Модонд ганц л толгой зангилаа байна.
*Навчин зангилаа нь хүүхэдгүй байна.
*Толгой зангилаанаас хамгийн доод талын зангилаа хүртэлх замын урт нь модны урт болно.
*Нэг эцэгтэй зангилаанууд нь ах дүүс болно.
*Хэрвээ p зангилаа нь толгой зангилаанаас q зангилаа хүртэлх зам дээр байвал p зангилаа нь q зангилааны эцэг болно.

## Чанар
### Чанар 1: 
Модны ямар нэг хоёр буюу гурав аа бас дөрөв зангилааг холбох ганц зам байна. Аль ч хоёр зангилааг авч үзэхэд ядаж нэр ерөнхий өвөг зангилаа олдоно. Ийм ерөнхий эх зангилаанаас  уг хоёр зангилаанд хүрэх зам нь давтагдашгүй бөгөөд эдгээрийг нийлүүлснээр зөвхөн ганц зам олдоно.

### Чанар 2: 
N зангилаа бүхий мод N-1 холбоостой байна. Энэ чанар нь үндсэн зангилаанаас бусад бүх зангилаа нь зөвхөн ганц эх зангилаанд шууд холбогдоно гэдгээс мөрдөн гарна. 
### Чанар 3: 
N  дотоод зангилаа бүхий хоёртын мод нь N+1 гадаад зангилаатай байна.
### Чанар 4: 
N дотоод зангилаа бүхий хоёртын модны гадаад замын урт нь дотоод замын уртаас 2N-ээр илүү байдаг.
### Чанар 5: 
Хоёртын модны i дүгээр түвшинд хамгийн ихдээ 2 i зэрэг байна.
### Чанар 6: 
n өндөртэй хоёртын модны максиум зангилааны тоо нь 2-ийн n зэргээс хасдаг нь 1 тэй тэнцүү байна.  
### Чанар 7: 
N дотоод зангилаа бүхий дүүрэн хоёртын модны өндөр нь ойролцоогоор  Log хоёр суурьтай И байна.

## Хоёртын модны төрөл(Types of binary tree)
*Үндэстэй **хоёртын мод** бол хамгийн дээд талдаа 2 хүүг агуулсан толгой зангилаатай мод юм.
*Зөв **хоёртын мод** гэдэг нь зангилаа бүрээс биш, навч бүртээ 2 хүүтэй модыг хэлнэ. Эсвэл **хоёртын модны** зангилаа бүр нь яг 0 юмуу 2 хүүтэй байж болно. 
*Төгс **хоёртын мод** нь эцэг болгон 2 хүүтэй, бүх навчнууд нь ижил түвшинд байрлах мод юм.Төгс **хоёртын модны** жишээ бол ургын мод - хүн бүр 2 эцэгтэй (нэг нь аав, нэг нь ээж); 
*Бүрэн **хоёртын мод** аль ч түвшинд сүүлийнхийг хасах боломжтой, бүгд дүүрсэн, мөн бүх зангилаанууд зүүн хүүтэй байх боломжтой. ........... сүүлийн түвшин дүүрээгүй. Энэ төрөл бол мэргэшсэн өгөгдлийн бүтцэд хэрэглэгддэг гэгддэг.
*Хязгааргүй **хоёртын мод** зангилаа бүр 2 хүүтэй түвшингийн тоо хязгааргүйгээр тоологдох. Хязгааргүй тоологдох бүх зангилаануудын олонлог, гэвч бүх хязгааргүй замын олонлог толгой тоологдохгүй.
*Тэнцвэртэй **хоёртын мод**. Ерөнхийдөө хоёртын модны түвшний зүүн болон баруун дэд моднууд зангилаа бүрээсээ 1 юмуу нэлээд багаар ялгаатай байна гэж тодорхойлсон.

## Хоёртын модны шинж чанарууд(Properties of binary trees)
*Төгс **хоёртын модны** n зангилааны тоог олохдоо дараах томъёог ашиглана. n = 2^h+1-1 (h нь модны түвшин)
***Хоёртын модны** n зангилааны тоог олохдоо өндөр h багадаа  n = h + 1 ихдээ n = 2^h+1-1 (h нь модны түвшин)
*Төгс **хоёртын модны** навчит зангилаануудын тоог олохдоо дараах томъёог ашиглана. l = 2^h
*Төгс **хоёртын модны** n зангилааны тоог олохдоо дараах томъёог ашиглана.  n = 2l-1 (l нь модны навчит зангилаануудын тоо)
*Бүрэн төгс **хоёртын модны** Null холбоосын тоог олохдоо (хүүхэдгүй зангилаанууд)  (n+1).
*Бүрэн төгс **хоёртын модны** дотоод зангилааны тоо (навчгүй зангилаа)  ⌊ n/2 ⌋.
## Хоёртын модонд нэвтрэх аргууд
Хоёртын модонд нэвтрэх 4 арга байдаг
### Pre-order
#Үндэсдээ нэвтрэнэ.
#Зүүн хүүхэддээ нэвтрэнэ.
#Баруун хүүхэддээ нэвтрэнэ.

### In-order
#Зүүн хүүхэддээ нэвтрэнэ.
#Үндэсдээ нэвтрэнэ.
#Баруун хүүхэддээ нэвтрэнэ.

### Post-order
#Зүүн хүүхэддээ нэвтрэнэ.
#Баруун хүүхэддээ нэвтрэнэ.
#Үндэсдээ нэвтрэнэ.

### Level-order
Түвшин түвшингээр нь нэвтэрнэ.

## Хоёртын мод байгуулах 
Хоёртыг модыг нэвтрүүлэх нэг арга бол түүний зангилааг өгөгдсөн болон хоёр (зүүн/баруун) холбоос агуулах өгөгдлийн хийсвэр төрлөөр тодорхойлдог. 

### Хоёртын модонд нэвтрэлт 
сонгосон алгоритмаасаа хамаарч Preorder, Inorder, Postorder, Levelorder гэсэн 4 төрөлд хуваагддаг. 
Java кодоор харуулбал:

  public static void preOrder(BinaryTreeNode t)
{
   if (t != null)
  {
      visit(t);
      preOrder(t.leftChild);
      preOrder(t.rightChild);
   }
}

public static void inOrder(BinaryTreeNode t)
{
   if (t != null)
   {
      inOrder(t.leftChild);
      visit(t);
      inOrder(t.rightChild);
   }
}

public static void postOrder(BinaryTreeNode t)
{
   if (t != null)
   { 
      postOrder(t.leftChild);
      postOrder(t.rightChild);
      visit(t);
   }
}

public static void postOrder(BinaryTreeNode t)
{
   while (t != null)
  {
      t –д зочлоод хүүхдүүдийг нь FIFO дараалалд хийнэ;
      зангилааг FIFO дарааллаас устгаж, дуудна t;
     // дараалал хоосон бол устгал null –г буцаана
   }
}

Pre-order
preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)
	iterativePreorder(node)
  parentStack = empty stack
  while not parentStack.isEmpty() or node ≠ null
    if node ≠ null then
      visit(node)
      if node.right ≠ null then
        parentStack.push(node.right)
      node = node.left
    else
      node = parentStack.pop()

In-order
inorder(node)
  if node == null then return
  inorder(node.left)
  visit(node)
  inorder(node.right)
	iterativeInorder(node)
  parentStack = empty stack
    while not parentStack.isEmpty() or node ≠ null
     if node ≠ null then
       parentStack.push(node)
       node = node.left
     else
       node = parentStack.pop()
       visit(node)
       node = node.right

Post-order
postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)
	iterativePostorder(node)
   stack = empty stack  
   lastnodeprinted = NULL 
   WHILE [NOT stack.isEmpty() OR node ≠ NULL]
       IF (node)
           stack.push(node)
           node = node->left
       ELSE
           peeknode = stack.peek()
           IF (peeknode->right AND lastnodeprinted ≠ peeknode->right) 
               /* if visiting node from left child AND right child exists, move right */
               node = peeknode->right
           ELSE
               stack.pop() 
               visit(peeknode)
               lastnodeprinted = peeknode

Ангилал:Өгөгдлийн бүтэц