Хэрэглэгч:Эгиймаа

Хоёртын мод

Мод

Байгаль дээр үндэс, мөчир, навч бүхий ургамлыг мод гэдэг. Компьютерын ухаанд модтой бүтцийн хувьд төстэй өгөгдлийн бүтцийг мөн мод гэдэг. Гэхдээ компьютерын ухаанд модыг уруу харуулж зурдаг. Мод гэдэг бүтцийн хувьд үндэс бол хагийн чухал элемент бөгөөд нэг модонд цорын ганц үндэс байна. Үндсээс мөчир, мөчрөөс навч гардаг. Салаалж ургасан модны хэсгийг дэд мод гэнэ. Нэг зангилаанаас хэдэн элемент – мөчир/навч салаалсан гэдгээс нь хамааруулж хоёртын, N –тын мод гэж ялгаж болдог. Тэдэн дотор хоёрын мод онцгой байр эзэлдэг бөгөөд хоёртын модонд суурилсан олон хэрэглээ байдаг. Модны тухай ярихад өвөг эцэг, эцэг, хүүхэд, ахан дүүс гэсэн ухагдахуунуудыг бас хэрэглэдэг. Модыг ингэж сурах нь байгаль дээрхтэй адилтгаж ойлгоход хэрэгтэй ч компьютерын ухаанд дараах байдлаар зурдаг.

Амьдрал дээр мод бүтцээр илэрхийлж болох, илүү тохиромжтой олон тооны өгөгдлийг нэрлэж болно. Жишээ нь хүмүүсийн ургийн бичиг, байгуулгын зохион байгуулалтын бүтэц, Байгаль, техникийн нийлмэл системийн бүтэц г.м. Өгөгдлийн мод бүтэц дээр боловсруулалт хийнэ гэдэг үнэн чанартаа модны үндсээс навч хүртэл дээшээ, доошоо салаа мөчрөөр дамжин нэвтрэлт хийнэ гэсэн үг yum tegehdee ene ni goomoo sdanart zoriulsan gaj vildel ym

Хоёртын мод

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

Чанар 1:

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

Чанар 2:

N зангилаа бүхий мод N-1 холбоостой байна. Энэ чанар нь үндсэн зангилаанаас бусад бүх зангилаа нь зөвхөн ганц эх 
зангилаанд шууд холбогдоно гэдгээс мөрдөн гарна. 

Чанар 3:

N  дотоод зангилаа бүхий хоёртын мод нь N+1 гадаад зангилаатай байна.

Чанар 4:

N дотоод зангилаа бүхий хоёртын модны гадаад замын урт нь дотоод замын уртаас 2N-ээр илүү байдаг.

Чанар 5:

Хоёртын модны i дүгээр түвшинд хамгийн ихдээ 2 i зэрэг байна.

Чанар 6:

n өндөртэй хоёртын модны максиум зангилааны тоо нь 2-ийн n зэргээс хасдаг нь 1 тэй тэнцүү байна.  

Чанар 7:

N дотоод зангилаа бүхий дүүрэн хоёртын модны өндөр нь ойролцоогоор Log хоёр суурьтай И байна.

Хоёртын мод байгуулах

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

Pre-order: F, B, A, D, C, E, G, I, H

In-order: A, B, C, D, E, F, G, H, I

Post-order: A, C, E, D, B, H, I, G, F

Level-order: F, B, G, A, D, I, C, E, H

Хоёртын модонд нэвтрэлт

сонгосон алгоритмаасаа хамаарч 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