Last active
April 20, 2022 06:34
-
-
Save yoloroy/136137b7a87afdd141bb12faef3883e6 to your computer and use it in GitHub Desktop.
solution for task of printing binary tree in all orders
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package dates2.mar11.binaryTreeTraversal | |
| fun main() { | |
| val size = readLine()!!.toInt() | |
| val pointers = Array(size) { | |
| val (value, firstChildIndex, secondChildIndex) = readLine()!! | |
| .split(" ") | |
| .map(String::toInt) | |
| Triple(value, firstChildIndex, secondChildIndex) | |
| } | |
| val root = BinaryTreeNode.fromPointers(pointers) | |
| val itemPrint: (BinaryTreeNode<Int>) -> Unit = { print("${it.value} ") } | |
| root.inOrderForEach(itemPrint); println() | |
| root.preOrderForEach(itemPrint); println() | |
| root.postOrderForEach(itemPrint); println() | |
| } | |
| interface BinaryTreeNode<V> { | |
| val value: V | |
| val firstChild: BinaryTreeNode<V>? | |
| val secondChild: BinaryTreeNode<V>? | |
| companion object { | |
| fun <V> fromPointers(pointers: Array<Triple<V, Int, Int>>): BinaryTreeNode<V> { | |
| val source = mutableListOf<PointerBinaryTreeNode<V>>() | |
| pointers.forEach { (value, firstChildIndex, secondChildIndex) -> | |
| source += PointerBinaryTreeNode(value, firstChildIndex, secondChildIndex, source) | |
| } | |
| return source[0] | |
| } | |
| } | |
| private class PointerBinaryTreeNode<V>( | |
| override val value: V, | |
| private val firstChildIndex: Int, | |
| private val secondChildIndex: Int, | |
| private val source: List<PointerBinaryTreeNode<V>> | |
| ) : BinaryTreeNode<V> { | |
| override val firstChild get() = source.getOrNull(firstChildIndex) | |
| override val secondChild get() = source.getOrNull(secondChildIndex) | |
| } | |
| } | |
| fun <V> BinaryTreeNode<V>.inOrderForEach(action: (BinaryTreeNode<V>) -> Unit) { | |
| firstChild?.inOrderForEach(action) | |
| action(this) | |
| secondChild?.inOrderForEach(action) | |
| } | |
| fun <V> BinaryTreeNode<V>.preOrderForEach(action: (BinaryTreeNode<V>) -> Unit) { | |
| action(this) | |
| firstChild?.preOrderForEach(action) | |
| secondChild?.preOrderForEach(action) | |
| } | |
| fun <V> BinaryTreeNode<V>.postOrderForEach(action: (BinaryTreeNode<V>) -> Unit) { | |
| firstChild?.postOrderForEach(action) | |
| secondChild?.postOrderForEach(action) | |
| action(this) | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "fmt" | |
| ) | |
| //goland:noinspection GoUnhandledErrorResult | |
| func main() { | |
| var size int | |
| var nodes []PointerTreeNode | |
| fmt.Scanln(&size) | |
| nodes = make([]PointerTreeNode, size) | |
| var firstPointer *PointerTreeNode | |
| var secondPointer *PointerTreeNode | |
| var name int | |
| var leftIndex int | |
| var rightIndex int | |
| for i := 0; i < size; i++ { | |
| fmt.Scanln(&name, &leftIndex, &rightIndex) | |
| if leftIndex == -1 { | |
| firstPointer = nil | |
| } else { | |
| firstPointer = &nodes[leftIndex] | |
| } | |
| if rightIndex == -1 { | |
| secondPointer = nil | |
| } else { | |
| secondPointer = &nodes[rightIndex] | |
| } | |
| nodes[i] = PointerTreeNode{name, firstPointer, secondPointer} | |
| } | |
| root := nodes[0] | |
| root.PrintInOrder() | |
| fmt.Println() | |
| root.PrintPreOrder() | |
| fmt.Println() | |
| root.PrintPostOrder() | |
| fmt.Println() | |
| nodes = nil | |
| } | |
| type PointerTreeNode struct { | |
| Name int | |
| LeftChild *PointerTreeNode | |
| RightChild *PointerTreeNode | |
| } | |
| func (node *PointerTreeNode) PrintInOrder() { | |
| if node == nil { | |
| return | |
| } | |
| node.LeftChild.PrintInOrder() | |
| fmt.Print(node.Name, " ") | |
| node.RightChild.PrintInOrder() | |
| } | |
| func (node *PointerTreeNode) PrintPreOrder() { | |
| if node == nil { | |
| return | |
| } | |
| fmt.Print(node.Name, " ") | |
| node.LeftChild.PrintPreOrder() | |
| node.RightChild.PrintPreOrder() | |
| } | |
| func (node *PointerTreeNode) PrintPostOrder() { | |
| if node == nil { | |
| return | |
| } | |
| node.LeftChild.PrintPostOrder() | |
| node.RightChild.PrintPostOrder() | |
| fmt.Print(node.Name, " ") | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def main(): | |
| size = int(input()) | |
| pointer_nodes = [ | |
| tuple(map(int, input().split())) | |
| for _ in range(size) | |
| ] | |
| # noinspection PyTypeChecker | |
| pointer_nodes.append(None) # -1 element | |
| root = pointer_nodes[0] | |
| def in_order_for_each(node, action): | |
| if node is None: | |
| return | |
| in_order_for_each(pointer_nodes[node[1]], action) | |
| action(node[0]) | |
| in_order_for_each(pointer_nodes[node[2]], action) | |
| def pre_order_for_each(node, action): | |
| if node is None: | |
| return | |
| action(node[0]) | |
| pre_order_for_each(pointer_nodes[node[1]], action) | |
| pre_order_for_each(pointer_nodes[node[2]], action) | |
| def post_order_for_each(node, action): | |
| if node is None: | |
| return | |
| post_order_for_each(pointer_nodes[node[1]], action) | |
| post_order_for_each(pointer_nodes[node[2]], action) | |
| action(node[0]) | |
| def print_tree_in_line(algorithm, node=root): | |
| algorithm(node, lambda item: print(item, end=" ")) | |
| print() | |
| for algorithm in [in_order_for_each, pre_order_for_each, post_order_for_each]: | |
| print_tree_in_line(algorithm) | |
| if __name__ == '__main__': | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment