Tree traversal (original) (raw)
في علم الحاسوب، يُمثل مسح (اجتياز) الشجرة (المعروف أيضًا باسم البحث في الشجرة وبالإنجليزية tree traversal) شكلًا من أشكال مسح الرسم البياني ويشير إلى عملية زيارة (فحص و / أو تحديث) كل عقدة في هيكلة الشجرة للبايانات، مرة واحدة بالضبط. تختلف أنواع المسح حسب ترتيب زيارة رؤوس الشجرة. الخوارزميات التالية خاصة ببنية الشجرة الثنائية، ولكن قد تُعمم على هياكل الأشجار الأخرى أيضًا.
| Property | Value |
|---|---|
| dbo:abstract | في علم الحاسوب، يُمثل مسح (اجتياز) الشجرة (المعروف أيضًا باسم البحث في الشجرة وبالإنجليزية tree traversal) شكلًا من أشكال مسح الرسم البياني ويشير إلى عملية زيارة (فحص و / أو تحديث) كل عقدة في هيكلة الشجرة للبايانات، مرة واحدة بالضبط. تختلف أنواع المسح حسب ترتيب زيارة رؤوس الشجرة. الخوارزميات التالية خاصة ببنية الشجرة الثنائية، ولكن قد تُعمم على هياكل الأشجار الأخرى أيضًا. (ar) Procházení stromu (také prohledávání stromu) je úloha z oblasti algoritmů, jejíž podstatou je postupné „navštívení“ všech položek datového stromu. Protože na tento strom může být nahlíženo jako na graf, jedná se zároveň o úlohu z teorie grafů. Různé přístupy k procházení stromu jsou obvykle ilustrovány na binárních stromech, neboť rozšíření na další stromy bývá poměrně přímočaré. Dva základní přístupy k procházení stromu jsou prohledávání do hloubky a prohledávání do šířky, přičemž oba mají různé podvarianty (zleva, zprava, …). Kromě pořadí, v kterém jsou vrcholy navštíveny, se také liší použitím různých pomocných datových struktur. Prohledávání do hloubky je přirozeně rekurzivní proces, při kterém je přirozené použití zásobníku, ať už definovaném v programu explicitně, nebo implicitním využitím zásobníku volání. Naopak při prohledávání do šířky je typicky využívána fronta. Pokud není cílem projít celý strom, ale jen najít určitou hodnotu, může být strom předem sestaven speciálním způsobem jako (nejčastěji ) – v něm se pak jako efektivní uplatňují speciální varianty algoritmů. Jiné speciální varianty algoritmů se uplatňují při prohledávání stavového prostoru (stavový prostor mívá rovněž charakter stromu). V oblasti umělé inteligence v počítačových hrách jsou úspěšné heuristické algoritmy, například odvozené od obecné myšlenky metody Monte Carlo. (cs) Das aus der lateinischen Sprache stammende Wort Traversierung (Verbum französisch traverser, englisch to traverse) wird verschiedentlich im Sinn von ‚etwas durchschreiten‘, ‚überqueren‘ gebraucht. (de) En ciencias de la computación, el recorrido de árboles se refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles. (es) 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. (fr) In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well. (en) 전산학에서 트리 순회(Tree traversal)는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이는 노드를 방문하는 순서에 따라 분류된다. 여기서 설명하는 알고리즘은 이진 트리에 대해서 작성되었지만, 다른 모든 트리에서도 일반화될 수 있다. (ko) Przechodzenie drzewa (pot. przechodzenie po drzewie) – proces odwiedzania wszystkich węzłów drzewa. (pl) Traversering är en operation som kan göras på datastrukturen träd. Djupet-först traversering: * Vid postordertraversering gås alla nodens barn igenom innan noden själv gås igenom. * Vid preordertraversering gås noden själv igenom innan barnen gås igenom. * Vid inordertraversering gås vänster delträd igenom därefter noden själv och slutligen det högra delträdet. Om inordertraversering genomförs på ett sorterat träd, så besöks noderna i ordning. (sv) Обход дерева (известный также как поиск по дереву) — вид , обусловливающий процесс посещения (проверки и/или обновления) каждого узла структуры дерева данных ровно один раз. Такие обходы классифицируются по порядку, в котором узлы посещаются. Алгоритмы в статье относятся к двоичным деревьям, но могут быть обобщены и для других деревьев. (ru) 在计算机科学裡，树的遍历（也称为树的走訪或树的搜索）是一种圖的遍歷，指的是按照某种规则，不重复地访问某种樹的所有节点的过程。具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式，其访问节点的顺序是不一样的。以下虽然描述的是二叉树的遍历算法，但它们也适用于其他树形结构。 (zh) Обхід бінарного дерева або пошук по дереву є одним з видів обходу графу, який передбачає відвідування (перевірку або модифікацію) кожної вершини дерева рівно один раз. Такі обходи класифікуються за порядком відвідування вершин. Хоч далі наведені алгоритми для двійкового дерева, але їх можна узагальнити для інших дерев. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Sorted_binary_tree_ALL_RGB.svg?width=300 |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20110606032941/http:/dev.mysql.com/tech-resources/articles/hierarchical-data.html http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html https://favtutor.com/blogs/tree-traversal-python-with-recursion http://www.perlmonks.org/%3Fnode_id=600456 http://www.math.northwestern.edu/~mlerma/courses/cs310-05s/notes/dm-treetran http://rosettacode.org/wiki/Tree_traversal http://www.sitepoint.com/hierarchical-data-database/ |
| dbo:wikiPageID | 597584 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Binärbaum dbpedia-ja:木構造_(データ構造) |
| dbo:wikiPageLength | 25425 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1118847664 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Queue_(abstract_data_type) dbr:Rosetta_Code dbr:List_of_data_structures dbr:Binary_search_tree dbr:Binary_tree dbc:Recursion dbr:Depth-first_search dbr:Go_(game) dbr:Branching_factor dbr:Monte_Carlo_method dbr:Monte_Carlo_tree_search dbr:Corecursion dbr:Lexicographic_order dbr:Call_stack dbr:Stack_(abstract_data_type) dbr:Stack_machine dbr:Computer_science dbr:Functional_programming dbr:Polish_notation dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbr:Topological_sorting dbr:Tree_(data_structure) dbr:Game_tree dbr:Heap_(data_structure) dbr:Lazy_evaluation dbr:Linked_list dbr:Amortized_analysis dbr:Breadth-first_search dbr:Graph_traversal dbr:Machine_code dbr:Depth-limited_search dbr:Recursion dbr:Reverse_Polish_notation dbr:Iterative_deepening_depth-first_search dbc:Trees_(data_structures) dbr:Chess dbr:Bijection dbr:Binary_expression_tree dbr:Parse_tree dbr:Ordinal_number dbc:Iteration_in_programming dbr:Diagonal_argument_(disambiguation) dbr:Search_tree dbr:One-dimensional_array dbr:Queue_(data_structure) dbr:Composition_(number_theory) dbr:File:Sorted_binary_tree_ALL_RGB.svg dbr:File:Sorted_binary_tree_breadth-first_traversal.svg dbr:File:AST_binary_tree_arith_variables.svg |
| dbp:date | November 2021 (en) |
| dbp:reason | Explicitly mention the restrictions on trees in order to be handled by this algorithm. Since there is no isLeaf test, it seems that all leaves must be on maximal depth or one level above it, like in a heap (data structure). (en) |
| dbp:wikiPageUsesTemplate | dbt:Graph_search_algorithm dbt:Anchor dbt:Br dbt:Clarify dbt:Font_color dbt:Main dbt:Redirect-distinguish dbt:Refimprove dbt:Reflist dbt:Rp dbt:Short_description dbt:Ubl dbt:Unreferenced_section dbt:Colorbull |
| dct:subject | dbc:Recursion dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbc:Trees_(data_structures) dbc:Iteration_in_programming |
| gold:hypernym | dbr:Form |
| rdf:type | owl:Thing yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | في علم الحاسوب، يُمثل مسح (اجتياز) الشجرة (المعروف أيضًا باسم البحث في الشجرة وبالإنجليزية tree traversal) شكلًا من أشكال مسح الرسم البياني ويشير إلى عملية زيارة (فحص و / أو تحديث) كل عقدة في هيكلة الشجرة للبايانات، مرة واحدة بالضبط. تختلف أنواع المسح حسب ترتيب زيارة رؤوس الشجرة. الخوارزميات التالية خاصة ببنية الشجرة الثنائية، ولكن قد تُعمم على هياكل الأشجار الأخرى أيضًا. (ar) Das aus der lateinischen Sprache stammende Wort Traversierung (Verbum französisch traverser, englisch to traverse) wird verschiedentlich im Sinn von ‚etwas durchschreiten‘, ‚überqueren‘ gebraucht. (de) En ciencias de la computación, el recorrido de árboles se refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles. (es) 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. (fr) In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well. (en) 전산학에서 트리 순회(Tree traversal)는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이는 노드를 방문하는 순서에 따라 분류된다. 여기서 설명하는 알고리즘은 이진 트리에 대해서 작성되었지만, 다른 모든 트리에서도 일반화될 수 있다. (ko) Przechodzenie drzewa (pot. przechodzenie po drzewie) – proces odwiedzania wszystkich węzłów drzewa. (pl) Traversering är en operation som kan göras på datastrukturen träd. Djupet-först traversering: * Vid postordertraversering gås alla nodens barn igenom innan noden själv gås igenom. * Vid preordertraversering gås noden själv igenom innan barnen gås igenom. * Vid inordertraversering gås vänster delträd igenom därefter noden själv och slutligen det högra delträdet. Om inordertraversering genomförs på ett sorterat träd, så besöks noderna i ordning. (sv) Обход дерева (известный также как поиск по дереву) — вид , обусловливающий процесс посещения (проверки и/или обновления) каждого узла структуры дерева данных ровно один раз. Такие обходы классифицируются по порядку, в котором узлы посещаются. Алгоритмы в статье относятся к двоичным деревьям, но могут быть обобщены и для других деревьев. (ru) 在计算机科学裡，树的遍历（也称为树的走訪或树的搜索）是一种圖的遍歷，指的是按照某种规则，不重复地访问某种樹的所有节点的过程。具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式，其访问节点的顺序是不一样的。以下虽然描述的是二叉树的遍历算法，但它们也适用于其他树形结构。 (zh) Обхід бінарного дерева або пошук по дереву є одним з видів обходу графу, який передбачає відвідування (перевірку або модифікацію) кожної вершини дерева рівно один раз. Такі обходи класифікуються за порядком відвідування вершин. Хоч далі наведені алгоритми для двійкового дерева, але їх можна узагальнити для інших дерев. (uk) Procházení stromu (také prohledávání stromu) je úloha z oblasti algoritmů, jejíž podstatou je postupné „navštívení“ všech položek datového stromu. Protože na tento strom může být nahlíženo jako na graf, jedná se zároveň o úlohu z teorie grafů. Různé přístupy k procházení stromu jsou obvykle ilustrovány na binárních stromech, neboť rozšíření na další stromy bývá poměrně přímočaré. (cs) |
| rdfs:label | مسح هيكلة الشجرة (ar) Procházení stromu (cs) Traversierung (de) Recorrido de árboles (es) Parcours d'arbre (fr) 트리 순회 (ko) Przechodzenie drzewa (pl) Tree traversal (en) Обход дерева (ru) Traversering (sv) Обхід дерева (uk) 树的遍历 (zh) |
| owl:differentFrom | dbr:Search_tree |
| owl:sameAs | freebase:Tree traversal yago-res:Tree traversal http://sw.cyc.com/concept/Mx4rbpQOvi1YEdaAAAABAxv-7A wikidata:Tree traversal dbpedia-ar:Tree traversal dbpedia-cs:Tree traversal dbpedia-de:Tree traversal dbpedia-es:Tree traversal dbpedia-fa:Tree traversal dbpedia-fr:Tree traversal dbpedia-hu:Tree traversal dbpedia-ko:Tree traversal dbpedia-pl:Tree traversal dbpedia-ru:Tree traversal dbpedia-sh:Tree traversal dbpedia-sr:Tree traversal dbpedia-sv:Tree traversal dbpedia-uk:Tree traversal dbpedia-vi:Tree traversal dbpedia-zh:Tree traversal https://global.dbpedia.org/id/FzuZ |
| prov:wasDerivedFrom | wikipedia-en:Tree_traversal?oldid=1118847664&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/AST_binary_tree_arith_variables.svg wiki-commons:Special:FilePath/Sorted_binary_tree_ALL_RGB.svg wiki-commons:Special:FilePath/Sorted_binary_tree_breadth-first_traversal.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Tree_traversal |
| is dbo:wikiPageDisambiguates of | dbr:Traversal |
| is dbo:wikiPageRedirects of | dbr:Converse_Postorder dbr:Morris_tree_traversal dbr:Applications_of_tree_search_algorithms dbr:Endorder dbr:In-order_traversal dbr:Inorder_traversal dbr:Backward_Inorder_traversal dbr:Backward_inorder_traversal dbr:Morris_traversal dbr:Postfix_traversal dbr:Tree-search_algorithm dbr:Tree_search dbr:Tree_search_algorithm dbr:Tree_traversals dbr:Tree_walk dbr:Level_order dbr:In-order_iteration dbr:In-order_walk dbr:Infix_traversal dbr:Inorder dbr:Inorder_tree_walk dbr:Inorder_walk dbr:Post-order_traversal dbr:Post-order_walk dbr:Postorder dbr:Postorder_iteration dbr:Postorder_traversal dbr:Postorder_tree_walk dbr:Postorder_walk dbr:Walking_the_tree dbr:Pre-order_traversal dbr:Pre-order_walk dbr:Prefix_traversal dbr:Preorder_iteration dbr:Preorder_traversal dbr:Preorder_tree_walk dbr:Preorder_walk |
| is dbo:wikiPageWikiLink of | dbr:Beam_search dbr:List_of_algorithms dbr:Converse_Postorder dbr:Morris_tree_traversal dbr:Binary_search_tree dbr:Descendants_of_Simon_Willard dbr:Algorithmic_technique dbr:List_of_graph_theory_topics dbr:Perl dbr:Depth-first_search dbr:Infix dbr:Infix_notation dbr:Motorola_68060 dbr:Ancestral_reconstruction dbr:Range_tree dbr:Queap dbr:Quadtree dbr:Free_variables_and_bound_variables dbr:Glossary_of_artificial_intelligence dbr:Monoid dbr:Consistent_hashing dbr:Contrast_set_learning dbr:Corecursion dbr:Applications_of_tree_search_algorithms dbr:Smoothsort dbr:Prefix_sum dbr:Maze-solving_algorithm dbr:Micromouse dbr:Ahnentafel dbr:Threaded_binary_tree dbr:Tree_(data_structure) dbr:Tree_sort dbr:Treefinder dbr:Trie dbr:Two-tree_broadcast dbr:Data-flow_analysis dbr:Distributed_tree_search dbr:Join-based_tree_algorithms dbr:MiniKanren dbr:AlphaGo dbr:And–or_tree dbr:Bridge_(graph_theory) dbr:Goal_node_(computer_science) dbr:Graph_traversal dbr:Iterator dbr:Real-time_operating_system dbr:Higher-order_function dbr:Irony_(framework) dbr:Chkrootkit dbr:JetPAG dbr:John_M._Scholes dbr:LCP_array dbr:Binary_expression_tree dbr:Binary_space_partitioning dbr:Traversal dbr:Direct_function dbr:Endorder dbr:Kosaraju's_algorithm dbr:Cartesian_tree dbr:Radix_sort dbr:Range_minimum_query dbr:Recursion_(computer_science) dbr:Search_algorithm dbr:Rope_(data_structure) dbr:Simplified_molecular-input_line-entry_system dbr:In-order_traversal dbr:Nested_set_model dbr:ID3_algorithm dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Planted_motif_search dbr:Unparser dbr:Scene_graph dbr:Terminal_yield dbr:Inorder_traversal dbr:Panos_Kalnis dbr:Random_surfing_model dbr:Pommerman_Challenge dbr:Backward_Inorder_traversal dbr:Backward_inorder_traversal dbr:Morris_traversal dbr:Postfix_traversal dbr:Tree-search_algorithm dbr:Tree_search dbr:Tree_search_algorithm dbr:Tree_traversals dbr:Tree_walk dbr:Level_order dbr:In-order_iteration dbr:In-order_walk dbr:Infix_traversal dbr:Inorder dbr:Inorder_tree_walk dbr:Inorder_walk dbr:Post-order_traversal dbr:Post-order_walk dbr:Postorder dbr:Postorder_iteration dbr:Postorder_traversal dbr:Postorder_tree_walk dbr:Postorder_walk dbr:Walking_the_tree dbr:Pre-order_traversal dbr:Pre-order_walk dbr:Prefix_traversal dbr:Preorder_iteration dbr:Preorder_traversal dbr:Preorder_tree_walk dbr:Preorder_walk |
| is foaf:primaryTopic of | wikipedia-en:Tree_traversal |
