Parcours d'arbre

En algorithmique, un parcours d'arbre est type d'algorithme effectué sur un arbre (au sens mathématique). C'est un cas particulier de parcours de graphe, c'est-à-dire un processus de visite des sommets du graphe, qui est ici un arbre. C'est un concept fondamental en algorithmique.

Définition

Étant donné un arbre, un parcours est un processus qui part d'un nœud, et visite tous les nœuds du graphe une seule fois, avec la contrainte qu'un nœud ne peut être visité que si l'un de ses voisins a été visité. Dans le cas des arbres, le nœud de départ est souvent la racine, et le parcours passe donc des parents aux enfants. On peut désigner par parcours une numérotation des sommets calculée à partir de ce processus (et qui ne suit pas toujours la propriété)^[1].

Types

Les principaux types de parcours d'arbre sont les parcours en profondeur et les parcours en largeur^[1]. Un autre type, utilisé en apprentissage automatique est la recherche arborescente Monte-Carlo.

Applications

Les parcours permettent notamment de générer des représentations linéaires des arbres et d'effectuer une recherche dans une structure arborescente^[2].

Notes et références

↑ ^{a et b} Olivier Carton, « Parcours d'arbres », sur Université Paris Diderot.
↑ Olivier Bournez, « Cours 3: Arbres. Parcours. », sur École polytechnique (France)

Portail de l'informatique théorique

Read other articles:

Hyōken no Majutsushi ga Sekai o Suberu

Hyōken no Majutsushi ga Sekai o SuberuSampul novel ringan volume pertama冰剣の魔術師が世界を統べる〜世界最強の魔術師である少年は、魔術学院に入学する〜(Hyōken no Majutsushi ga Sekai o Suberu: Sekai Saikyō no Majutsushi de Aru Shōnen wa, Majutsu Gakuin ga Nyūgaku Suru)GenrePetualangan, fantasi[1] Seri novelPengarangNana MikoshibaPenerbitShōsetsuka ni NarōTerbit25 Oktober 2019 – sekarang Novel ringanPengarangNana MikoshibaIlustratorRiko Kor...

قرية كانيستو (نيويورك)

قرية كانيستو الإحداثيات 42°16′13″N 77°36′21″W / 42.27035°N 77.60582°W / 42.27035; -77.60582 [1] تاريخ التأسيس 1789 تقسيم إداري البلد الولايات المتحدة[2] التقسيم الأعلى مقاطعة ستوبين خصائص جغرافية المساحة 2.418195 كيلومتر مربع2.418196 كيلومتر مربع (1 أبريل 2010) ار�...

Phosphatidylcholine

Class of phospholipids 1-Oleoyl-2-palmitoyl-phosphatidylcholine Phosphatidylcholines (PC) are a class of phospholipids that incorporate choline as a headgroup. They are a major component of biological membranes and can be easily obtained from a variety of readily available sources, such as egg yolk or soybeans, from which they are mechanically or chemically extracted using hexane. They are also a member of the lecithin group of yellow-brownish fatty substances occurring in animal and plant ti...

Arrondissement of Commercy

Arrondissement in Grand Est, FranceCommercyArrondissementLocation within the region Grand EstCountryFranceRegionGrand EstDepartmentMeuseNo. of communes135SubprefectureCommercyArea1,932.2 km2 (746.0 sq mi)Population (2021)[1]42,088 • Density22/km2 (60/sq mi)INSEE code552 Part of a series onLorraineFlag of Lorraine since the 13th century History Mediomatrici & Leuci Gallia Belgica Lotharingia Duchy of Lorraine Duchy of Bar Three Bishopr...

USS S-40

Submarine of the United States USS S-40 in the 1930s, probably in the East Asia. History United States NameUSS S-40 BuilderBethlehem Shipbuilding Corporation, San Francisco, California Laid down5 March 1919 Launched5 January 1921 Sponsored byMrs. John H. Rosseter Commissioned20 November 1923 Decommissioned29 October 1945 Stricken13 November 1945 Fate Sold November 1946 Scrapped July 1947 General characteristics Class and typeS-class submarine Displacement 854 long tons (868 t) surfaced 1...

R. L. Bhatia

Indian politician (1920–2021) Raghunandan Lal BhatiaBhatia in 200523rd Governor of BiharIn office10 July 2008 – 28 June 2009Chief MinisterNitish KumarPreceded byR. S. GavaiSucceeded byDevanand Konwar16th Governor of KeralaIn office23 June 2004 – 10 July 2008Chief MinisterA. K. AntonyOommen ChandyV. S. AchuthanandanPreceded byT. N. Chaturvedi(Additional Charge)Succeeded byR. S. Gavai Personal detailsBorn(1920-07-03)3 July 1920Amritsar, Punjab, British IndiaDied1...

Yahdi Khoir Harahap

Ini adalah nama Batak Angkola/Mandailing, marganya adalah Harahap. Yahdi Khoir Harahap Anggota DPRD Sumatera Utara Fraksi PANPetahanaMulai menjabat 16 September 2019PresidenJoko WidodoGubernurEdy RahmayadiWakil Bupati Asahan ke-1Masa jabatan25 Maret 2000 – 25 Maret 2005PresidenAbdurrahman WahidMegawati SoekarnoputriSusilo Bambang YudhoyonoGubernurTengku Rizal NurdinRudolf PardedeSyamsul ArifinPendahuluTidak ada, Jabatan baruPenggantiTaufan Gama Simatupang Informasi pribadiL...

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 % 获提名人唐納·川普希拉莉·克林頓政党共和黨民主党家鄉州紐約州紐約州竞选搭档迈克·彭斯蒂姆·凱恩选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

City of Chester (circonscription britannique)

Pour les articles homonymes, voir City of Chester. City of ChesterGéographiePays Royaume-UniNation constitutive AngleterreRégion Angleterre du Nord-OuestSuperficie 133,48 km2Coordonnées 53° 10′ 00″ N, 2° 55′ 00″ OFonctionnementStatut Circonscription du Parlement du Royaume-Uni (d)HistoireFondation 24 novembre 1885Remplace City of Chester (d)modifier - modifier le code - modifier Wikidata La circonscription dans le Cheshire. La circonscription ...

Teritori Papua dan Nugini

Teritori Papua dan Nugini1949–1975 Bendera Lambang Lagu kebangsaan: God Save the Queen God Save the KingStatusUnited Nations Trust TerritoryTeritori eksternal AustraliaIbu kotaPort MoresbyBahasa yang umum digunakanInggris (resmi)Bahasa-bahasa AustronesiaBahasa-bahasa PapuaKreol InggrisMonarki(Raja/Ratu) • 1949–1952 George VI• 1952–1975 Elizabeth II AdministratorKomisioner Tinggi • 1949–1952 (pertama) Jack Keith Murray• 1974–1975 (terak...

Rehoboth, Harris County, Georgia

Rehoboth is an unincorporated community in Harris County, in the U.S. state of Georgia.[1] History The community was named after Rehoboth, a place mentioned in the Hebrew Bible.[2] A variant name was Mobley.[1] Rehoboth was once an incorporated municipality; its municipal charter was repealed in 1995.[2] References ^ a b U.S. Geological Survey Geographic Names Information System: Rehoboth ^ a b Krakow, Kenneth K. (1975). Georgia Place-Names: Their History and O...

إيفابرادين

إيفابرادين الاسم النظامي 3-[3-({[(7S)-3,4-dimethoxybicyclo[4.2.0]octa-1,3,5-trien-7-yl]methyl}(methyl)amino)propyl]-7,8-dimethoxy-2,3,4,5-tetrahydro-1H-3-benzazepin-2-one تداخل دوائي أميودارون، وسوتالول، وسلبيريد، وميثادون، وفيراباميل، وأميودارون، وديلتيازيم، وسوتالول، وفينغوليمود، وكريزوتينيب، وب�...

1 Tawarikh 10

1 Tawarikh 10Kitab Tawarikh (Kitab 1 & 2 Tawarikh) lengkap pada Kodeks Leningrad, dibuat tahun 1008.KitabKitab 1 TawarikhKategoriKetuvimBagian Alkitab KristenPerjanjian LamaUrutan dalamKitab Kristen13← pasal 9 pasal 11 → 1 Tawarikh 10 (atau I Tawarikh 10, disingkat 1Taw 10) adalah bagian dari Kitab 1 Tawarikh dalam Alkitab Ibrani dan Perjanjian Lama di Alkitab Kristen. Dalam Alkitab Ibrani termasuk dalam bagian Ketuvim (כְּתוּבִים, tulisan).[1][2] Tek...

USS Nimitz

Supercarrier of the United States Navy USS Nimitz USS Nimitz (CVN-68) off the coast of San Diego in July 2009. History United States NameNimitz NamesakeChester W. Nimitz Ordered31 March 1967 BuilderNewport News Shipbuilding Laid down22 June 1968 Launched13 May 1972 Commissioned3 May 1975 ReclassifiedCVN-68, 30 June 1975 HomeportKitsap Identification MMSI number: 303981000 Callsign: NMTZ Hull number: CVN-68 MottoTeamwork, a Tradition Nickname(s) Old Salt Uncle Chester BOHICA Statusin active se...

San Francisco Film Critics Circle Awards 2010

9th SFFCC Awards December 13, 2010 Best Picture: The Social Network The 9th San Francisco Film Critics Circle Awards, honoring the best in film for 2010, were given on 13 December 2010. Winners Darren Aronofsky, Best Director co-winner David Fincher, Best Director co-winner Colin Firth, Best Actor winner Michelle Williams, Best Actress winner John Hawkes, Best Supporting Actor winner Jacki Weaver, Best Supporting Actress winner Best Picture: The Social Network Best Director (TIE): Darren Aro...

三星Galaxy Note 3 Neo

Samsung Galaxy Note 3 Neo SM-N750 (3G) SM-N7505/7 (LTE) SM-N750K/L/S (韓國版本LTE-A)生產商三星電子系列Samsung Galaxy兼容的網絡列表 2G GSM/GPRS/EDGE 850MHz/900MHz/1800MHz/1900MHz 2G CDMA 1xRTT 800MHz/850MHz/1900MHz 3G WCDMA 850MHz/900MHz/1900MHz/2100MHz 3G CDMA EV-DO rev 0/A/B; 800MHz/850MHz/1900MHz 3G TD-SCDMA 1900MHz/2000Mhz 3G UMTS/HSDPA/HSUPA/HSPA+/DC-HSPA+ 850MHz/900MHz/AWS（1700MHz）/1900MHz/2100MHz 4G LTE Bands 1–5、7、8、11–13、17、20、25 首次發布2...

美

关于与「美」標題相近或相同的条目页，請見「美 (消歧義)」。本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。此條目可参照英語維基百科相應條目来扩充。 (2021年2月19日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或�...

National Register of Historic Places listings in Bracken County, Kentucky

Location of Bracken County in Kentucky This is a list of the National Register of Historic Places listings in Bracken County, Kentucky. This is intended to be a complete list of the properties and districts on the National Register of Historic Places in Bracken County, Kentucky, United States. The locations of National Register properties and districts for which the latitude and longitude coordinates are included below, may be seen in a map.[1] There are 24 properties and districts l...

Communist University of the Toilers of the East

University in Moscow, Russia (1921–c. 1939) You can help expand this article with text translated from the corresponding article in Russian. (June 2016) Click [show] for important translation instructions. View a machine-translated version of the Russian article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting ma...

Нора Фінґшайдт

Нора Фінґшайдтнім. Nora FingscheidtНора Фінґшайдт на Берлінале у 2019 роціДата народження17 лютого 1983(1983-02-17)[1][2] (41 рік)Місце народженняБрауншвейг, Нижня Саксонія, ФРН[1]Громадянство НімеччинаПрофесіякінорежисерка, сценаристка, акторкаРоки активності2011 — д�...