Ағаштарды кесіп өту - Tree traversal

«Ағаштарды іздеу» осында бағытталады. Мұны шатастыруға болмайды Іздеу ағашы.
График және ағаш
іздеу алгоритмдері
Тізімдер
Байланысты тақырыптар

Жылы Информатика, ағаштарды кесіп өту (сонымен бірге ағаш іздеу және ағашты серуендеу) формасы болып табылады графикалық жүру а тармағындағы әрбір түйінге бару (тексеру және / немесе жаңарту) процесін білдіреді ағаштар құрылымы, дәл бір рет. Мұндай өтулер түйіндерге бару реті бойынша жіктеледі. A үшін келесі алгоритмдер сипатталған екілік ағаш, бірақ олар басқа ағаштарға да жалпылануы мүмкін.

Түрлері

Айырмашылығы жоқ байланыстырылған тізімдер, бір өлшемді массивтер және басқа да сызықтық мәліметтер құрылымы, сызықтық тәртіп бойынша канонды түрде өтетін ағаштар бірнеше жолмен өтуі мүмкін. Олар өтуі мүмкін бірінші-тереңдік немесе ені - бірінші тапсырыс. Оларды тереңдіктен бірінші рет өтудің үш жалпы әдісі бар: тәртіпте, алдын-ала тапсырыс және кейінгі тапсырыс.[1] Осы негізгі өтулерден тыс әртүрлі күрделі немесе гибридтік схемалар болуы мүмкін, мысалы тереңдігі шектеулі іздеулер сияқты тереңдетуді тереңдету - бірінші іздеу. Соңғысы, сондай-ақ бірінші іздеу, шексіз ағаштарды айналып өту үшін де қолданыла алады, қараңыз төменде.

Ағаштарды кесіп өтуге арналған деректер құрылымдары

Ағашты айналып өту барлық түйіндер бойынша белгілі бір түрде қайталануды қамтиды. Берілген түйіннен бірнеше келесі түйін болуы мүмкін болғандықтан (бұл деректердің сызықтық құрылымы емес), сондықтан дәйекті есептеуді (параллель емес) болжай отырып, кейбір түйіндерді кейінге қалдыру үшін кейінге қалдыру керек. Бұл көбінесе a арқылы жасалады стек (LIFO) немесе кезек (ФИФО). Ағаш дербес анықтамалық (рекурсивті анықталған) мәліметтер құрылымы болғандықтан, өтпелі жолды анықтауға болады рекурсия немесе, неғұрлым нәзік, корекурсия, өте табиғи және айқын түрде; бұл жағдайда кейінге қалдырылған түйіндер жанама түрде сақталады шақыру стегі.

Тереңдіктен бірінші іздеу стек арқылы, оның ішінде рекурсивті түрде (қоңырау шоғыры арқылы) оңай жүзеге асырылады, ал кеңдіктен бірінші іздеу кезек арқылы, оның ішінде коррекуралық түрде де оңай жүзеге асырылады.

Мысал ағашының тереңдігі-бірінші өтуі:
алдын-ала тапсырыс (қызыл): F, B, A, D, C, E, G, I, H;
ретімен (сары): A, B, C, D, E, F, G, H, I;
кейінгі тапсырыс (жасыл): A, C, E, D, B, H, I, G, F

Екілік ағаштың тереңдігін бірінші іздеу

Бұл іздеулер деп аталады бірінші тереңдік (DFS), өйткені іздеу ағашы келесі бауырласқа барар алдында әр балаға мүмкіндігінше тереңдетіледі. Екілік ағаш үшін олар алгоритмі келесідей болатын ағымдағы түйіннен басталатын әр түйіндегі қатынас операциялары ретінде анықталады:[2][3]

Екілік ағашты айналып өтудің жалпы рекурсивтік үлгісі:

Рекурсивті аргументке бір деңгейге түсіңіз N. Егер N бар (бос емес) келесі үш операцияны белгілі бір тәртіпте орындайды:
(L)Рекурсивті жүру Nсол жақ ағаш.
(R)Рекурсивті жүру Nоң жақ ағаш.
(N)Ағымдағы түйінді өңдеңіз N өзі.
Бір деңгейге көтеріліп, ата-аналық түйінге келіп оралу N.

Мысалдарда (L) негізінен (R) дейін орындалады. Бірақ (L) дейін (L) мүмкін, (RNL) қараңыз.

Алдын ала тапсырыс (NLR)

  1. Ағымдағы түйіннің деректер бөлігіне қол жеткізіңіз.
  2. Алдын ала тапсырыс беру функциясын рекурсивті шақыру арқылы сол жақ ағаштан өтіңіз.
  3. Алдын-ала тапсырыс беру функциясын рекурсивті шақыру арқылы оң жақ субтраммен жүріңіз.
Алдын ала тапсырыс беру а топологиялық сұрыпталған бірі, себебі ата-аналық түйін оның кез-келген еншілес түйіні жасалмас бұрын өңделеді.

Тапсырыста (LNR)

  1. Реттелген функцияны рекурсивті шақыру арқылы сол жақ ағаштан өтіңіз.
  2. Ағымдағы түйіннің деректер бөлігіне қол жеткізіңіз.
  3. Реттелген функцияны рекурсивті шақыру арқылы оң жақ ағаштан өтіңіз.
Ішінде екілік іздеу ағашы әр түйінде кілт сол жақ кіші ағаштағы барлық кілттерден үлкен және оң жақ кіші ағаштағы барлық кілттерден кіші болатындай етіп бұйрық берілсе, пернелер тіркесімі пернелерді алады көтерілу сұрыпталған тәртіп[4]

Кері тәртіпте (RNL)

  1. Кері тәртіптегі функцияны рекурсивті шақыру арқылы оң жақ ағаштан өтіңіз.
  2. Ағымдағы түйіннің деректер бөлігіне қол жеткізіңіз.
  3. Кері тәртіптегі функцияны рекурсивті шақыру арқылы сол жақ ағаштан өтіңіз.
Ішінде екілік іздеу ағашы, кері ретпен өту пернелерді шығарады төмендеу сұрыпталған тәртіп

Тапсырыстан кейінгі (LRN)

  1. Тапсырыстан кейінгі функцияны рекурсивті шақыру арқылы сол жақ ағаштан өтіңіз.
  2. Тапсырыстан кейінгі функцияны рекурсивті шақыру арқылы оң жақ ағаштан өтіңіз.
  3. Ағымдағы түйіннің деректер бөлігіне қол жеткізіңіз.

Траверсалдың ізі ағаштың дәйектілігі деп аталады. Траверсаль трасс - бұл әрбір кірген түбірдің тізімі. Алдын ала, кейінгі немесе кейінгі тәртіпке сәйкес бірізділікке бөлу түпнұсқа ағашты ерекше сипаттайды. Элементтері ерекше ағашты ескере отырып, алдын-ала тапсырыс беру немесе тапсырыс бойынша тапсырыспен жұптастыру ағашты ерекше сипаттау үшін жеткілікті. Алайда, алдын-ала тапсырыстан кейінгі тапсырыс ағаш құрылымында түсініксіздікті қалдырады.[5]

Жалпы ағаш

Кез-келген ағашты тереңдіктен іздеу арқылы өту үшін әр түйінде рекурсивті түрде келесі әрекеттерді орындаңыз:

  1. Алдын ала тапсырыс беру әрекетін орындаңыз.
  2. Әрқайсысы үшін мен 1-ден балалар санына дейін:
    1. Сапар мен- егер бар болса.
    2. Тапсырыстық операцияны орындаңыз.
  3. Тапсырыстан кейінгі әрекетті орындаңыз.

Қарастырылып отырған мәселеге байланысты алдын-ала тапсырыс беру, тапсырыс беру немесе тапсырыстан кейінгі операциялар жарамсыз болуы мүмкін немесе сіз тек белгілі бір балаға барғыңыз келуі мүмкін, сондықтан бұл операциялар міндетті емес. Сондай-ақ, іс жүзінде алдын-ала тапсырыс беру, тапсырыс беру және тапсырыс беру операцияларының бірнешеуі қажет болуы мүмкін. Мысалы, үштік ағашқа енгізу кезінде заттарды салыстыру арқылы алдын-ала тапсырыс беру операциясы орындалады. Ағашты қайта теңдестіру үшін кейін тапсырыстан кейінгі операция қажет болуы мүмкін.

Іздеудің бірінші деңгей / деңгейі

Деңгей тәртібі: F, B, G, A, D, I, C, E, H
Негізгі мақала: Бірінші ену

Ағаштарды да кесіп өтуге болады деңгей-тәртіп, біз төменгі деңгейге көтерілмес бұрын деңгейдегі барлық түйіндерге барамыз. Бұл іздеу деп аталады бірінші-іздеу (BFS), өйткені келесі тереңдікке барар алдында іздеу ағашы әр тереңдікте мүмкіндігінше кеңейтіледі.

Басқа түрлері

Сондай-ақ, ағашты кесіп өту алгоритмдері бар, олар тереңдікті бірінші іздеу де, кеңдікті де бірінші іздеу емес. Осындай алгоритмдердің бірі болып табылады Монте-Карло ағаштарын іздеу кеңейтуді негізге ала отырып, ең перспективалы қадамдарды талдауға бағытталған іздеу ағашы қосулы кездейсоқ іріктеу іздеу кеңістігінің.

Қолданбалар

Арифметикалық өрнекті көрсететін ағаш A * (B − C) + (Д. + E)

Алдын ала тапсырыс беруді префикс өрнегі жасау үшін пайдалануға болады (Поляк жазбасы ) бастап ағаштар: өрнек ағашын алдын-ала реттеп өту. Мысалы, алдын ала тапсырыс бойынша кірістілікте бейнеленген арифметикалық өрнекті кесіп өту «+ * A − B C + Д. E".

Тапсырыстан кейінгі траверс постфиксті ұсынуы мүмкін (Кері поляк жазбасы ) екілік ағаш. Тапсырыстан кейінгі кірістілікте бейнеленген арифметикалық өрнекті жүргізу »A B C − * Д. E + + «; соңғысын оңай түрлендіруге болады машина коды өрнекті а арқылы бағалау стек машинасы.

Тапсырыс бойынша жүру өте жиі қолданылады екілік іздеу ағаштары өйткені ол базалық жиынтықтан мәндерді ретімен қайтарады, екілік іздеу ағашын орнатқан компараторға сәйкес.

Түйіндер мен мәндерді жою немесе босату кезіндегі тапсырыстан кейінгі траверс бүкіл екілік ағашты жоя алады немесе босатады. Осылайша түйін балаларын босатқаннан кейін босатылады.

Сондай-ақ, екілік ағаштың қайталануы әрекеттерден кейін реттілікке әкеледі, өйткені көрсеткіш көшірме түйіннің көшірмесіне сәйкес өріске тағайындалады N.child ата-анасының көшірмесінде N бірден кейін қайтукөшірме рекурсивті процедурада. Демек, ата-ананы барлық балалар аяқтамай тұрып аяқтауға болмайды.

Іске асыру

Тереңдіктен бірінші іздеу

Алдын ала берілетін тапсырыс

алдын ала берілетін тапсырыс(түйін) егер (түйін == нөл)        қайту    бару (түйін) алдын-ала тапсырыс беру (түйін. сол жақ) алдын-ала тапсырыс беру (түйін. құқық)
итеративті алдын-ала тапсырыс беру(түйін) егер (түйін == нөл)    қайту  s ← бос стек  итеру (түйін) уақыт (емес s.isEmpty ()) түйін ← s.pop () бару (түйін) // алдымен оң жақ бала итеріліп, сол жақ алдымен өңделеді егер node.right ≠ нөл      s.push (node.right) егер node.left ≠ нөл      s.push (node.left)

Қалпында

қалпында(түйін) егер (түйін == нөл)        қайту    inorder (node.left) кіру (node) inorder (node.right)
iterativeInorder(түйін) s ← бос стек  уақыт (емес s.isEmpty () немесе түйін ≠ нөл)    егер (түйін ≠ нөлs.push (түйін) түйіні ← түйін.left басқа      түйін ← s.pop () кіру (түйін) түйін ← түйін.right

Тапсырыс

почта(түйін) егер (түйін == нөл)        қайту    пошта тапсырысы (node.left) postorder (node.right) сапар (түйін)
iterativePostorder(түйін) s ← бос стек  lastNodeVisited ← нөл  уақыт (емес s.isEmpty () немесе түйін ≠ нөл)    егер (түйін ≠ нөлs.push (түйін) түйіні ← түйін.left басқа      peekNode ← s.peek () // егер оң жақта бала болса және сол жақта орналасқан түйінді айналдырса, оңға жылжытыңыз егер (peekNode.right right нөл және lastNodeVisited ≠ peekNode.right) түйін ← peekNode.right басқа        бару (peekNode) lastNodeVisited ← s.pop ()

Жоғарыда аталған барлық іс-шаралар ағаштың биіктігіне пропорционалды стек кеңістігін қажет етеді, ол а шақыру стегі рекурсивті үшін және итеративті үшін ата-аналық стек. Нашар теңдестірілген ағашта бұл айтарлықтай болуы мүмкін. Итеративті іске асырулар арқылы біз әр түйінде ата-аналық көрсеткіштерді сақтау арқылы стек қажеттілігін алып тастай аламыз ағашты бұрау (келесі бөлім).

Моррис жіптерді қолданып, тәртіп бойынша жүреді

Негізгі мақала: Бұрандалы екілік ағаш

Екілік ағаш әрбір сол жақ меңзерді (егер ол нөл болса) түйіннің алдыңғы предшественнигіне (егер ол бар болса), ал оң жақтағы әр бала көрсеткішіне (әйтпесе нөл болады) ин- түйіннің ізбасары (егер ол бар болса).

Артықшылықтары:

  1. Қоңырау стегін қолданатын және жады мен уақытты жұмсайтын рекурсияны болдырмайды.
  2. Түйін ата-анасының жазбасын сақтайды.

Кемшіліктері:

  1. Ағаш неғұрлым күрделі.
  2. Біз бір уақытта тек бір ғана траверсаль жасай аламыз.
  3. Екі бала болмаған кезде және түйіндердің екі мәні де олардың ата-бабаларына бағытталса, қателіктерге көбірек ұшырайды.

Моррис травералы - бұл жіптерді қолданатын тәртіптегі траверсті жүзеге асыру:[6]

  1. Реттелген мұрагерге сілтемелер жасаңыз.
  2. Осы сілтемелер арқылы деректерді басып шығарыңыз.
  3. Түпнұсқа ағашты қалпына келтіру үшін өзгертулерді қайтарыңыз.

Бірінші ену

Төменде қарапайым үшін жалған код көрсетілген кезек деңгей деңгейінің өтуіне негізделген және берілген тереңдіктегі түйіндердің максималды санына пропорционалды кеңістікті қажет етеді. Бұл түйіндердің жалпы санына тең болуы мүмкін / 2. Бұл өтпелі қозғалыс үшін кеңістікті тиімді тәсіл тереңдетуді тереңдету - бірінші іздеу.

деңгей реттегіш(түбір) q ← бос кезек    q.энук (түбір) уақыт емес q.isEmpty () істеу        түйін ← q.dequeue () кіру (түйін) егер node.left ≠ нөл содан кейін            q.enqueue (node.left) егер node.right ≠ нөл содан кейін            q.enqueue (node.right)

Шексіз ағаштар

Қозғалыс әдетте түйіндердің саны бар ағаштар үшін жасалады (демек, ақырғы тереңдік пен ақырлы) тармақталу факторы ) оны шексіз ағаштар үшін де жасауға болады. Бұл әсіресе қызығушылық тудырады функционалды бағдарламалау (әсіресе жалқау бағалау ), өйткені шексіз деректер құрылымын оңай анықтауға және олармен жұмыс жасауға болады, бірақ олар (қатаң) бағаланбайды, өйткені бұл шексіз уақытты алады. Кейбір ақырғы ағаштар өте үлкен, мысалы, оларды бейнелеуге болмайды ойын ағашы үшін шахмат немесе жүр, сондықтан оларды шексіз сияқты талдау пайдалы.

Қозғалыстың негізгі талабы - әр түйінге бару. Шексіз ағаштар үшін қарапайым алгоритмдер жиі орындалмайды. Мысалы, шексіз тереңдіктегі екілік ағашты ескере отырып, алдымен тереңдік іздеу ағаштың бір жағына (шарт бойынша сол жағына) түседі, қалғандарына ешқашан бармайды, ал тәртіптелген немесе кейінгі тәртіптегі травсаль ешқашан болмайды сапар кез келген түйіндер, өйткені ол жапыраққа жетпеген (және шын мәнінде ешқашан болмайды). Керісінше, бірінші ену (деңгейлік тәртіп) шексіз тереңдіктегі екілік ағашты проблемасыз айналып өтеді және шынымен де тармақталған коэффициенті бар кез келген ағашты айналып өтеді.

Екінші жағынан, тамырдың шексіз көп балалары бар және осы балалардың әрқайсысында екі баладан тұратын 2-ші тереңдіктегі ағашты ескере отырып, бірінші іздеу барлық түйіндерді аралап шығады, өйткені ол немерелерін (балаларының балалары) шаршатады. бір түйін), ол келесіге ауысады (егер ол тапсырыс емес болса, бұл жағдайда ол ешқашан тамырға жетпейді). Керісінше, бірінші кезектегі ізденіс ешқашан немерелеріне жетпейді, өйткені ол алдымен балаларды шаршатады.

Шексіз арқылы жұмыс уақытының анағұрлым күрделі анализін беруге болады реттік сандар; Мысалы, жоғарыдағы 2 ағаштың тереңдігін бірінші іздеу қажет болады ω · 2 қадам: бірінші деңгей үшін ω, содан кейін екінші деңгей үшін тағы бір ω.

Осылайша, бірінші тереңдікті немесе бірінші енін іздеу кез-келген шексіз ағашты айналып өтпейді және өте үлкен ағаштарда тиімді болмайды. Алайда, гибридті әдістер кез-келген (саналы түрде) шексіз ағашты айналып өте алады, негізінен a қиғаш аргумент («диагональ» - тік және көлденең тіркесім - тереңдік пен еннің тіркесіміне сәйкес келеді).

Шексіз тереңдіктегі шексіз тармақталған ағашты ескере отырып, түбірге (), түбірдің балаларына (1), (2),…, немерелеріне (1, 1), (1, 2),…, (2) белгі қойыңыз. , 1), (2, 2),… ​​және т.б. Осылайша түйіндер а бір-біріне санауға болатын және алдымен жазбалар қосындысы бойынша, содан кейін бойынша орналастырылатын оң сандардың шекті (мүмкін бос) тізбектерімен сәйкестік лексикографиялық тәртіп берілген сома шегінде (берілген мәнге тек қана көптеген тізбектер қосылады, сондықтан барлық жазбаларға қол жеткізіледі - формальды түрде шекті саны бар шығармалар берілген натурал санның, атап айтқанда 2n−1 шығармалары n ≥ 1), бұл траверсаль береді. Айқын:

0: ()1: (1)2: (1, 1) (2)3: (1, 1, 1) (1, 2) (2, 1) (3)4: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

т.б.

Мұны шексіз тереңдіктегі екілік ағашты осы ағашқа кескіндеу және содан кейін кеңдікті іздеуді қолдану деп түсінуге болады: ата-аналық түйінді екінші және одан кейінгі балалармен байланыстыратын «төмен» шеттерін бірінші баладан екіншісіне «оң» шеттермен ауыстырыңыз бала, екінші баладан үшінші балаға және т.с.с., осылайша, әр қадамда біреуі төменге (а,, соңына дейін қосыңыз) немесе оңға қарай (біреуін соңғы санға қосыңыз) (түбірден басқа) қосымша болып табылады және тек төмен түсе алады), бұл шексіз екілік ағаш пен жоғарыдағы нөмірлеу арасындағы сәйкестікті көрсетеді; жазбалардың қосындысы (минус бір) түбірден қашықтыққа сәйкес келеді, ол 2-ге сәйкес келедіn−1 тереңдіктегі түйіндер n − 1 шексіз екілік ағашта (2 екілікке сәйкес келеді).

Әдебиеттер тізімі

  1. ^ «Дәріс 8, Ағаштарды кесіп өту». Алынған 2 мамыр 2015.
  2. ^ [1]
  3. ^ «Алдын ала тапсырыс беру траверсалгоритмі». Алынған 2 мамыр 2015.
  4. ^ Виттман, Тодд. «Ағаштарды кесіп өту» (PDF). UCLA Математика. Архивтелген түпнұсқа (PDF) 2015 жылғы 13 ақпанда. Алынған 2 қаңтар, 2016.
  5. ^ «Алгоритмдер, алдын-ала, кейінгі және кезекпен реттіліктің қандай тіркесімдері ерекше ?, Computer Science Stack Exchange». Алынған 2 мамыр 2015.
  6. ^ Моррис, Джозеф М. (1979). «Екілік ағаштарды қарапайым және арзан бағдарлау». Ақпаратты өңдеу хаттары. 9 (5). дои:10.1016/0020-0190(79)90068-1.
Жалпы
  • Дейл, Нелл. Лилли, Сюзан Д. «Паскаль Плюс Деректер құрылымы». D. C. Heath and Company. Лексингтон, MA. 1995. Төртінші басылым.
  • Дроздек, Адам. «С ++ тіліндегі мәліметтер құрылымы мен алгоритмдері». Брук / Коул. Pacific Grove, Калифорния. 2001. Екінші басылым.
  • [2]

Сыртқы сілтемелер