Двоично дърво е подредено дърво, в което всеки възел има най-много две деца. Децата са подредени така, че ляво дете да идва преди дясно дете. Ще разгледаме как да изградим двоично дърво и как да внедрим най-важните алгоритми за обхождане на дървото: предварителна поръчка, след поръчка и по поръчка.
Нека започнем със създаването на клас, който да представлява единичен възел в нашето двоично дърво, BinaryNode
. Ще приемем, че стойностите на нашите възли на нашето двоично дърво са от един и същи тип.
Сега създайте файл Main.kt
и добавете следния код, за да създадете нашето примерно двоично дърво. Не е необходимо да указваме типа като Int
, тъй като Kotlin има извод за тип.
Обхождане на предварителна поръчка
При обхождане на дърво с предварителна поръчка първо се посещава коренът, след което поддърветата, вкоренени в неговите деца, се обхождат рекурсивно.
Псевдокодът ще изглежда така:
Algorithm preorderTraversal(T, v)
perform the action on the node v
preorderTraversal(T, T.leftChild(v))
preorderTraversal(T, T.rightChild(v))
Сега добавете следния preorderTraversal
метод към BinaryNode
. В този пример ще зададем нашия метод за действие просто да отпечата стойността на възела, който сме посетили.
Сега, ако извикате tree.preorderTraversal()
, след като сте настроили вашето двоично дърво в Main.kt
, трябва да видите следния изход.
Visited node with value: 3
Visited node with value: 4
Visited node with value: 0
Visited node with value: 1
Visited node with value: 5
Visited node with value: 2
Преминаване след поръчка
При обхождане след поръчка поддърветата, вкоренени в децата на корена, се посещават първо, преди да се посети самият корен.
Псевдокодът ще изглежда така:
Algorithm postorderTraversal(T, v)
postorderTraversal(T, T.leftChild(v))
postorderTraversal(T, T.rightChild(v))
perform the action on the node v
Можем да приложим метода postorderTraversal
към BinaryNode
по следния начин.
По същия начин извикването на tree.postorderTraversal()
трябва да доведе до следния резултат.
Visited node with value: 0
Visited node with value: 1
Visited node with value: 4
Visited node with value: 2
Visited node with value: 5
Visited node with value: 3
Обхождане по ред
При обхождане по ред, действието върху възел се извършва между рекурсивните обхождания на неговите ляво и дясно поддървета. Можете да видите това като посещение на възлите отляво надясно.
Псевдокодът ще изглежда така:
Algorithm inorderTraversal(T, v)
inorderTraversal(T, T.leftChild(v))
perform the action on the node v
inorderTraversal(T, T.rightChild(v))
В Котлин:
По същия начин извикването на tree.inorderTraversal()
трябва да доведе до следния резултат.
Visited node with value: 0
Visited node with value: 4
Visited node with value: 1
Visited node with value: 3
Visited node with value: 2
Visited node with value: 5
Благодаря за четенето.