![\"\"](\"https:\/\/demensdeum.com\/blog\/wp-content\/uploads\/2022\/08\/tree.png\")
<\/p>\nTri par arbre\u00a0: tri \u00e0 l’aide d’un arbre de recherche binaire. Complexit\u00e9 temporelle – O(n\u00b2). Dans un tel arbre, chaque n\u0153ud \u00e0 gauche a des nombres inf\u00e9rieurs au n\u0153ud, \u00e0 droite il y en a plus que le n\u0153ud, en venant de la racine et en imprimant les valeurs de gauche \u00e0 droite, on obtient une liste tri\u00e9e de nombres . Surprenant, non\u00a0?<\/p>\n
Consid\u00e9rez l’arbre de recherche binaire\u00a0:<\/p>\n
<\/p>\n
Derrick Coetzee<\/a> (domaine public)<\/span><\/p>\n Essayez de lire manuellement les nombres en partant de l’avant-dernier n\u0153ud gauche du coin inf\u00e9rieur gauche, pour chaque n\u0153ud \u00e0 gauche – un n\u0153ud – \u00e0 droite.<\/p>\n Cela ressemblera \u00e0 ceci\u00a0:<\/p>\n Pour impl\u00e9menter l’algorithme dans le code, vous aurez besoin de deux fonctions\u00a0:<\/p>\n L’arbre binaire de recherche est assembl\u00e9 de la m\u00eame mani\u00e8re qu’il est lu, un num\u00e9ro est attach\u00e9 \u00e0 chaque n\u0153ud \u00e0 gauche ou \u00e0 droite, selon qu’il est inf\u00e9rieur ou sup\u00e9rieur.<\/p>\n Exemple en Lua\u00a0:<\/p>\n \u0412\u0430\u0436\u043d\u044b\u0439 \u043d\u044e\u0430\u043d\u0441 \u0447\u0442\u043e \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0430\u0432\u043d\u044b \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0445 \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c\u043e\u0432 \u043f\u043e\u0434\u0446\u0435\u043f\u043b\u0435\u043d\u0438\u044f \u043a \u043d\u043e\u0434\u0435, \u044f \u0436\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043a \u043a\u043b\u0430\u0441\u0441\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043f\u0440\u0438 \u0440\u0430\u0441\u043f\u0435\u0447\u0430\u0442\u043a\u0435 \u0447\u0438\u0441\u043b\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0442\u0441\u044f \u043f\u043e \u0441\u0447\u0435\u0442\u0447\u0438\u043a\u0443.<\/p>\n https:\/\/gitlab.com\/demensdeum\/algorithms\/-\/tree\/master\/sortAlgorithms\/treesort<\/a><\/p>\n TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube<\/a><\/p>\n Tree sort – YouTube<\/a><\/p>\n Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube<\/a><\/p>\n Sorting algorithms\/Tree sort on a linked list – Rosetta Code<\/a><\/p>\n Tree Sort – GeeksforGeeks<\/a><\/p>\n Tree sort – Wikipedia<\/a><\/p>\n How to handle duplicates in Binary Search Tree? – GeeksforGeeks<\/a><\/p>\n Tree Sort | GeeksforGeeks – YouTube<\/a><\/p>\n","protected":false},"excerpt":{"rendered":" Tri par arbre\u00a0: tri \u00e0 l’aide d’un arbre de recherche binaire. Complexit\u00e9 temporelle – O(n\u00b2). Dans un tel arbre, chaque n\u0153ud \u00e0 gauche a des nombres inf\u00e9rieurs au n\u0153ud, \u00e0 droite il y en a plus que le n\u0153ud, en venant de la racine et en imprimant les valeurs de gauche \u00e0 droite, on obtientContinue reading “Tri des arbres”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,190,207],"class_list":["post-3409","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-sorting","tag-tree-sort","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"fr","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3409","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=3409"}],"version-history":[{"count":7,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3409\/revisions"}],"predecessor-version":[{"id":3870,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3409\/revisions\/3870"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=3409"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=3409"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=3409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
\n
\n\n\nfunction Node:new(value, lhs, rhs)\n output = {}\n setmetatable(output, self)\n self.__index = self \n output.value = value\n output.lhs = lhs\n output.rhs = rhs\n output.counter = 1\n return output \nend\n\nfunction Node:Increment()\n self.counter = self.counter + 1\nend\n\nfunction Node:Insert(value)\n if self.lhs ~= nil and self.lhs.value > value then\n self.lhs:Insert(value)\n return\n end\n\n if self.rhs ~= nil and self.rhs.value < value then\n self.rhs:Insert(value)\n return\n end\n\n if self.value == value then\n self:Increment()\n return\n elseif self.value > value then\n if self.lhs == nil then\n self.lhs = Node:new(value, nil, nil)\n else\n self.lhs:Insert(value)\n end\n return\n else\n if self.rhs == nil then\n self.rhs = Node:new(value, nil, nil)\n else\n self.rhs:Insert(value)\n end\n return\n end\nend\n\nfunction Node:InOrder(output)\n if self.lhs ~= nil then\n output = self.lhs:InOrder(output)\n end\n output = self:printSelf(output)\n if self.rhs ~= nil then\n output = self.rhs:InOrder(output)\n end\n return output\nend\n\nfunction Node:printSelf(output)\n for i=0,self.counter-1 do\n output = output .. tostring(self.value) .. \" \"\n end\n return output\nend\n\nfunction PrintArray(numbers)\n output = \"\"\n for i=0,#numbers do\n output = output .. tostring(numbers[i]) .. \" \"\n end \n print(output)\nend\n\nfunction Treesort(numbers)\n rootNode = Node:new(numbers[0], nil, nil)\n for i=1,#numbers do\n rootNode:Insert(numbers[i])\n end\n print(rootNode:InOrder(\"\"))\nend\n\n\nnumbersCount = 10\nmaxNumber = 9\n\nnumbers = {}\n\nfor i=0,numbersCount-1 do\n numbers[i] = math.random(0, maxNumber)\nend\n\nPrintArray(numbers)\nTreesort(numbers)<\/code><\/pre>\n<\/div>\n\u0421\u0441\u044b\u043b\u043a\u0438<\/h3>\n
\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438<\/h3>\n