Двоично дърво е подредено дърво, в което всеки възел има най-много две деца. Децата са подредени така, че ляво дете да идва преди дясно дете. Ще разгледаме как да изградим двоично дърво и как да внедрим най-важните алгоритми за обхождане на дървото: предварителна поръчка, след поръчка и по поръчка.

Нека започнем със създаването на клас, който да представлява единичен възел в нашето двоично дърво, 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

Благодаря за четенето.