{"id":6902,"date":"2019-08-28T14:06:06","date_gmt":"2019-08-28T13:06:06","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6902"},"modified":"2022-12-03T22:58:59","modified_gmt":"2022-12-03T21:58:59","slug":"searching-in-a-tree-data-structure","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/searching-in-a-tree-data-structure\/","title":{"rendered":"Searching in a tree (data structure)"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6902\" class=\"elementor elementor-6902\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-808d0aa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"808d0aa\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-faa8292\" data-id=\"faa8292\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fe6340f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"fe6340f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Graph Theory<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-4424ce8\" data-id=\"4424ce8\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7c28035 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"7c28035\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-1440737\" data-id=\"1440737\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fb19eb7 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"fb19eb7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Depth-first_search\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6e1c5c22 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6e1c5c22\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-677be6c6\" data-id=\"677be6c6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3a2b549e elementor-widget elementor-widget-text-editor\" data-id=\"3a2b549e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>To search in a graph, we first build a tree covering the graph.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:heading --><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/searching-in-a-tree-data-structure\/#Breadth-first-search\" >Breadth first search<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/searching-in-a-tree-data-structure\/#In-depth-search-pre-order\" >In-depth search: pre-order<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/searching-in-a-tree-data-structure\/#In-depth-search-in-order\" >In-depth search: in-order<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/searching-in-a-tree-data-structure\/#In-depth-search-out-order\" >In-depth search: out-order<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Breadth-first-search\"><\/span>Breadth first search<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><!-- \/wp:heading --><!-- wp:paragraph --><\/p>\n<p>BFS browse by increasing depth to the root.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"align\":\"center\",\"id\":2574} --><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-2574 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre5.png\" alt=\"Breadth first search\" width=\"291\" height=\"189\" title=\"\"><\/figure>\n<\/div>\n<p><!-- \/wp:image --><!-- wp:html --><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre><b>BFS<\/b>(Graph G, Node s): {f = CreateQueue (); f.stack (s); mark (s);\n  <strong>while<\/strong> no f.empty () s = f.pop (); print (s);\n     <strong> for<\/strong> each children t of s in G\n           <strong>yew<\/strong> t unmarked DO f.stack (t); mark (t);\n           <strong>end if<\/strong>\n     <strong> end for<\/strong>\n  <strong>end while<\/strong>       \n }<\/pre>\n<\/div>\n<p><!-- \/wp:html --><!-- wp:heading --><\/p>\n<p><!-- \/wp:heading --><!-- wp:heading --><\/p>\n<h2><span class=\"ez-toc-section\" id=\"In-depth-search-pre-order\"><\/span>In-depth search: pre-order<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><!-- \/wp:heading --><!-- wp:paragraph --><\/p>\n<p>In-depth algorithms are recursive. In the prefix path, we always browse the left subtree before processing the right subtree.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"align\":\"center\",\"id\":2579} --><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"aligncenter wp-image-2579 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre6.png\" alt=\"In-depth search: pre-order\" width=\"198\" height=\"187\" title=\"\"><\/figure>\n<\/div>\n<p><!-- \/wp:image --><!-- wp:html --><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>Check if the current node is empty or null.<\/li>\n<li>Display the data part of the root (or current node).<\/li>\n<li>Traverse the left subtree by recursively calling the pre-order function.<\/li>\n<li>Traverse the right subtree by recursively calling the pre-order function.<\/li>\n<\/ol>\n<\/div>\n<p><!-- \/wp:html --><!-- wp:heading --><\/p>\n<p><!-- \/wp:heading --><!-- wp:heading --><\/p>\n<h2><span class=\"ez-toc-section\" id=\"In-depth-search-in-order\"><\/span>In-depth search: in-order<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><!-- \/wp:heading --><!-- wp:paragraph --><\/p>\n<p>The LNR browse as far left as possible, and display the branches from left to right. This algorithm display the diagonals from bottom to top.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"align\":\"center\",\"id\":2585} --><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"aligncenter wp-image-2585 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre7.png\" alt=\"In-depth search: in-order\" width=\"193\" height=\"196\" title=\"\"><\/figure>\n<\/div>\n<p><!-- \/wp:image --><!-- wp:html --><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>Check if the current node is empty or null.<\/li>\n<li>Traverse the left subtree by recursively calling the in-order function.<\/li>\n<li>Display the data part of the root (or current node).<\/li>\n<li>Traverse the right subtree by recursively calling the in-order function.<\/li>\n<\/ol>\n<\/div>\n<p><!-- \/wp:html --><!-- wp:heading --><\/p>\n<p><!-- \/wp:heading --><!-- wp:heading --><\/p>\n<h2><span class=\"ez-toc-section\" id=\"In-depth-search-out-order\"><\/span>In-depth search: out-order<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><!-- \/wp:heading --><!-- wp:paragraph --><\/p>\n<p>This is a diagonal browsing from top to bottom.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"align\":\"center\",\"id\":2592} --><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-2592 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre8.png\" alt=\"In-depth search: out-order\" width=\"209\" height=\"190\" title=\"\"><\/figure>\n<\/div>\n<p><!-- \/wp:image --><!-- wp:html --><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>Check if the current node is empty or null.<\/li>\n<li>Traverse the left subtree by recursively calling the post-order function.<\/li>\n<li>Traverse the right subtree by recursively calling the post-order function.<\/li>\n<li>Display the data part of the root (or current node).<\/li>\n<\/ol>\n<\/div>\n<p><!-- \/wp:html --><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Graph Theory Wiki Home Page To search in a graph, we first build a tree covering the graph. Breadth first search BFS browse by \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-6902","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6902","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=6902"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6902\/revisions"}],"predecessor-version":[{"id":18410,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6902\/revisions\/18410"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=6902"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}