fork download
copy 
  1. package main
  2. import "fmt"
  3.  
  4. func main(){
  5. 	tree := NewBinaryTree()
  6. 	test(!tree.Contains(0), "not contains 0")
  7.  
  8. 	test(!tree.Contains(42), "not contains 42")
  9. 	fmt.Println("# adding 42")
  10. 	tree.Add(42)
  11. 	test(tree.Contains(42), "contains 42")
  12.  
  13. 	test(!tree.Contains(17), "not contains 17")
  14. 	fmt.Println("# adding 17")
  15. 	tree.Add(17)
  16. 	test(tree.Contains(17), "contains 17")
  17. 	test(tree.Contains(42), "contains 42")
  18. }
  19.  
  20. func test(expr bool, text string) {
  21. 	if expr {
  22. 		fmt.Println("OK   -- " + text)
  23. 	} else {
  24. 		fmt.Println("FAIL -- " + text)
  25. 	}
  26. }
  27.  
  28. // everything below would typically be in a separate package
  29.  
  30. type BinaryTree struct {
  31. 	root *node
  32. }
  33.  
  34. func NewBinaryTree() *BinaryTree {
  35. 	return &BinaryTree { nil }
  36. }
  37.  
  38. type node struct {
  39.     value int
  40.     left, right *node
  41. }
  42.  
  43. func (node *node) getNode(i int) **node {
  44.     if node.value < i {
  45.         if node.left == nil {
  46.             return &node.left
  47.         }
  48.         return node.left.getNode(i)
  49.     } else if i < node.value {
  50.         if node.right == nil {
  51.             return &node.right
  52.         }
  53.         return node.right.getNode(i)
  54.     }
  55.     return &node // not nil, not writable
  56. }
  57.  
  58. func (tree *BinaryTree) Contains(n int) bool {
  59. 	root := tree.root
  60. 	if root == nil {
  61. 		return false
  62. 	}
  63.     return *(root.getNode(n)) != nil
  64. }
  65.  
  66. // returns true if the tree was mutated as a result,
  67. // and false if the number was already present
  68. func (tree *BinaryTree) Add(n int) bool {
  69. 	if tree.root == nil {
  70. 		tree.root = &node{n, nil, nil}
  71. 		return true
  72. 	}
  73.     target := tree.root.getNode(n)
  74.     if *target == nil {
  75.         *target = &node{n, nil, nil}
  76.         return true
  77.     }
  78.     return false
  79. }
  80.  
Success #stdin #stdout 0s 420608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
OK   -- not contains 0
OK   -- not contains 42
# adding 42
OK   -- contains 42
OK   -- not contains 17
# adding 17
OK   -- contains 17
OK   -- contains 42
https://ideone.com/GKPiRF
language:
Go (go 1.12.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!