предположим, что дерево двоичных выражений и как на него действуют обходы порядка, порядка и пост-порядка:
inorder: левое поддерево, текущий корень, правое поддерево preorder: текущий корень, левое поддерево, правое поддерево postorder: левое поддерево, правое поддерево, текущий корень
теперь текущий код, сначала идентифицирующийлевое и правое поддеревья.как мы знаем, первый элемент массива preorder это наш корень, и мы могли бы найти наш соответствующий корень в массиве inorder.поскольку мы знаем, что все элементы до корня являются элементами левого поддерева, а все элементы после него являются элементами правого поддерева.
мы хотим произвести обход по порядку, поэтому рекурсивно продолжаем работу с левым поддеревом:
postorder(preorder, prestart+1, inorder, inostart, i-inostart);
- prestart + 1: , поскольку корень левого поддерева находится сразу после текущего корня в обходе предварительного заказа
- i-inostart: , поскольку i является индексом нашего корня в массиве inorder, поэтому i-inostart будет размером левого поддерева
затемправое поддерево:
postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1);
- предварительный запуск + i-inostart + 1: , как я уже говорил выше i-inostart - размер левогоподдерево, а также мы знаем, что в массиве предварительного заказа корень правого поддерева будет идти после текущего корня и всего поддерева, поэтому его индекс будет prestart + i-inostart + 1
- i + 1: , поскольку в массиве inorder индекс корня был i , а элементпосле этого должно быть начало правого поддерева в массиве перестановок
- length-i + inostart-1: , поскольку размер правого поддерева будет длина минус размер левого поддерева и минус 1 (корень)
, а затем выведите наш текущий корень:
cout<<preorder[prestart]<<" ";
рекурсивное выполнение приведет кв обход заказа дерева.