Хоёртын мод

• Чиглэлтэй холбоос нь эцэгээс хүүрүү чиглэж холбоно.
• Толгой зангилаа нь эцэггүй байна. Модонд ганц л толгой зангилаа байна.
• Навчин зангилаа нь хүүхэдгүй байна.
• Толгой зангилаанаас хамгийн доод талын зангилаа хүртэлх замын урт нь модны урт болно.
• Нэг эцэгтэй зангилаанууд нь ах дүүс болно.
• Хэрвээ 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 хоёр суурьтай И байна.

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

• Төгс хоёртын модны 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

1. Үндэсдээ нэвтрэнэ.
2. Зүүн хүүхэддээ нэвтрэнэ.
3. Баруун хүүхэддээ нэвтрэнэ.

In-order

1. Зүүн хүүхэддээ нэвтрэнэ.
2. Үндэсдээ нэвтрэнэ.
3. Баруун хүүхэддээ нэвтрэнэ.

Post-order

1. Зүүн хүүхэддээ нэвтрэнэ.
2. Баруун хүүхэддээ нэвтрэнэ.
3. Үндэсдээ нэвтрэнэ.

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-orderpreorder(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-orderinorder(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-orderpostorder(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