Quand utiliser les stratégies de parcours d'arbre de recherche binaire préordonnée, postordonnée et inordonnée ?

Question

J'ai réalisé récemment que, bien qu'ayant utilisé les BST à de nombreuses reprises dans ma vie, je n'ai jamais envisagé d'utiliser autre chose que la traversée d'ordre (bien que je sois conscient et sache à quel point il est facile d'adapter un programme pour utiliser la traversée de pré/post-ordre).

Lorsque je m'en suis rendu compte, j'ai ressorti mes vieux manuels sur les structures de données et j'ai cherché le raisonnement qui sous-tend l'utilité des traversées avant et après l'ordre - ils ne disaient pas grand-chose cependant.

Quels sont les exemples de cas où il convient d'utiliser pratiquement la précommande ou la post-commande ? Quand est-ce plus logique que l'ordre interne ?

Answer 1

• Inorder Traversal imprime les nœuds dans l'ordre trié si l'arbre binaire donné est un arbre de recherche binaire. Un exemple serait de trouver le kième plus petit élément dans un arbre de recherche binaire :

    class Solution:
      def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
          res=None
          def inorder(node):
              if not node:
                  return
              # in bst this is the smallest value
              inorder(node.left)
              # python determines the scope at creation time of the function
              nonlocal k
              k-=1
              if k==0:
                  nonlocal res
                  res=node.val
                  return
              inorder(node.right)
          inorder(root)
          return res

• Dans Postorder, nous visitons le sous-arbre de gauche et le sous-arbre de droite avant de visiter le nœud actuel dans la récursion. Par exemple, si l'arbre binaire donné est équilibré en hauteur, c'est-à-dire un arbre binaire dans lequel les sous-arbres gauche et droit de chaque nœud ne diffèrent pas en hauteur de plus de 1. Dans ce cas, nous devons obtenir la hauteur du sous-arbre gauche et la hauteur du sous-arbre, puis transmettre le résultat au nœud parent.

    class Solution:
      def isBalanced(self, root: Optional[TreeNode]) -> bool:
          def post_order(root):
              # leaf node is balanced
              if not root:
                  # we carry the height of each subtree
                  return [True,0]
              # with recursion, we start from bottom, so we do not have repetitive work
              left,right=post_order(root.left),post_order(root.right)
              # if any of the subtree return false, then we know entire tree is not balanced
              balanced=left[0] and right[0] and abs(left[1]-right[1])<=1
              # 1+max(left[1],right[1]) is the height of the each subtree. 1 is the root of the subtree
              return [balanced,1+max(left[1],right[1])]
          return post_order(root)[0]

• Dans l'ordre préalable, nous visitons d'abord le nœud actuel, puis nous passons au sous-arbre de gauche. Après avoir touché tous les nœuds du sous-arbre de gauche, nous nous déplaçons vers le sous-arbre de droite et le visitons de la même manière. Un exemple serait la construction d'un arbre binaire à partir d'un ordre préalable et d'un ordre inverse. Pour construire un arbre, nous devons d'abord traiter le nœud, puis construire ses sous-arbres gauche et droit.

    class Solution:
      def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
          if not preorder or not inorder:
              return None
          # first element of preorder is root
          root=TreeNode(preorder[0])
          # mid value in inorder gives us root. left values of root will be the left subtree, right values will be the right subtree
          # mid tells us how many elements we want from left subtree and howmany for right subtree
          mid = inorder.index(preorder[0])
          # we took 1 out of each array. preorder will not include the first, inorder will not include the mid value
          root.left=self.buildTree(preorder[1:mid+1],inorder[:mid])
          root.right=self.buildTree(preorder[mid+1:],inorder[mid+1:])
          return root

Answer 2

En commande : Pour obtenir la chaîne d'entrée originale à partir de n'importe quel arbre d'analyse, parce que l'arbre d'analyse suit la préséance des opérateurs. Le sous-arbre le plus profond est parcouru en premier. Ainsi, l'opérateur dans le nœud parent a moins de priorité que l'opérateur dans le sous-arbre.