Хоёртын мод

Компьютерийн ухаанд хоёртын моднь өргөн хэрэглэгддэг өгөгдлийн бүтэц юм. Мод нь зангилаатай байдаг бөгөөд ихдээ 2 хүүхэд зангилаатай байдаг (баруун хүүхэд ба зүүн хүүхэд ).Үндэс (root node) нь модны бүх зангилааны өвөг дээдэс нь болох ба модны аль ч зангилаа толгой зангилаанаас хамааралтай байна. Мод нь толгой зангилаанаас өөр зангилаагүй бол хоосон мод болно. Хоёртын мод-онд бүх зангилааны түвшин нь ихэвчлэн хоёр байдаг. n зангилаатай мод байвал n-1 нь мөчир эсвэл түвшин болно. Хоёртын мод нь binarySearchTrees эсвэл binaryHeaps- ийн хэрэгжүүлдэг. Энэ нь хайх болон эрэмблэх гэсэн давуу талуудыг зэрэг тусгасан.
Хоёртын модны онцгой хэрэглээ нь K-ary tree юм.
Хоёртын мод нь модны онцгой нэг тохиолдол бөгөөд зангилаа бүр нь хоёроос илүүгүй дэд зангилаатай байдаг. Хэрэв нэг ч зангилаа агуулаагүй бол хоосон мод буюу null мод/зангилаа гэж нэрлэнэ. Зангилааны хоёр дэд зангилааг зүүн дэд загилаа ба баруун дэд зангилаа гэж ялгадаг. Хоёртын модны зангилаа нь нэг эсвэл хоёр хүүхэд зангилаа агуулж болно.
Модны хамгийн сүүлчийн түвшингээс бусад түвшинд дотоод загилаагаар гүйцэд дүүргэсэн бол түүнийг дүүрэн хоёртын мод гэнэ. Дүүрэн хоёртын модны хамгийн сүүлчийн түвшинд зөвхөн гадаад зангилааг агуулна. Харин дотоод зангилааг агуулах хамгийн сүүлчийн түвшингийн зөвхөн баруун талд зарим гадаад зангилаа байвал түүнийг гүйцэд мод гэнэ.
Хоёртын модны өөр нэг онцгой хэлбэр бол ташуу хоёртын мод юм. Ташуу хоёртын модыг зүүн ба баруун ташуу гэж үзэж болно. Хэрэв бүх зангилаа зүүн дэд модгүй бол баруун ташуу, хэрэв бүх зангилаа баруун дэд модгүй бол зүүн ташуу гэнэ. Мөн хөрөөний шүд хэлбэртэй байж болно. Өөрөөр хэлбэл зангилаа бүр зөвхөн зүүн эсвэл баруун дэд модтой байна гэсэн үг юм. Хоёртын мод нь компьютерийн хэрэглээнд маш өргөн ашиглагдах ба тэрээр дүүрэн эсвэл гүйцэд хоёртын мод байх үед хамгийн үр ашигтай юм.
Модны ямар нэг хоёр буюу гурав аа бас дөрөв зангилааг холбох ганц зам байна. Аль ч хоёр зангилааг авч үзэхэд ядаж нэр ерөнхий өвөг зангилаа олдоно. Ийм ерөнхий эх зангилаанаас уг хоёр зангилаанд хүрэх зам нь давтагдашгүй бөгөөд эдгээрийг нийлүүлснээр зөвхөн ганц зам олдоно.
N зангилаа бүхий мод N-1 холбоостой байна. Энэ чанар нь үндсэн зангилаанаас бусад бүх зангилаа нь зөвхөн ганц эх зангилаанд шууд холбогдоно гэдгээс мөрдөн гарна.
N дотоод зангилаа бүхий хоёртын мод нь N+1 гадаад зангилаатай байна.
N дотоод зангилаа бүхий хоёртын модны гадаад замын урт нь дотоод замын уртаас 2N-ээр илүү байдаг.
Хоёртын модны i дүгээр түвшинд хамгийн ихдээ 2 i зэрэг байна.
n өндөртэй хоёртын модны максиум зангилааны тоо нь 2-ийн n зэргээс хасдаг нь 1 тэй тэнцүү байна.
N дотоод зангилаа бүхий дүүрэн хоёртын модны өндөр нь ойролцоогоор Log хоёр суурьтай И байна.
Хоёртын модонд нэвтрэх 4 арга байдаг
Түвшин түвшингээр нь нэвтэрнэ.
Хоёртыг модыг нэвтрүүлэх нэг арга бол түүний зангилааг өгөгдсөн болон хоёр (зүүн/баруун) холбоос агуулах өгөгдлийн хийсвэр төрлөөр тодорхойлдог.
сонгосон алгоритмаасаа хамаарч Preorder, Inorder, Postorder, Levelorder гэсэн 4 төрөлд хуваагддаг. Java кодоор харуулбал:
{
}
public static void inOrder(BinaryTreeNode t) {
}
public static void postOrder(BinaryTreeNode t) {
}
public static void postOrder(BinaryTreeNode t) {
}
Pre-order preorder(node)
iterativePreorder(node)
In-order inorder(node)
iterativeInorder(node)
Post-order postorder(node)
iterativePostorder(node)