tree.nim

import system,random
discard """二分探索木
参照ノードより小さいノードは左部分木へ、大きいノードは右部分木へ
ノード保持はref
"""
type
  Tree=ref NodeObj
  NodeObj=object
    left,right:Tree
    elem:int

proc `$`(tree:Tree):string=
  result=""
  if tree.left!=nil:
    result&= $(tree.left)
  result&= $(tree.elem)&","
  if tree.right!=nil:
    result&= $(tree.right)
  return result

proc build(arr:seq[int],dist:var Tree):void

var
  root:Tree

var testdata:seq[int]
testdata= @[0,1,2,3,4,5,6,7,8,9,10]
randomize()
for i in 0..10:
  swap(testdata[i],testdata[i+rand(max=10-i)])

echo testdata

new(root)
build(testdata,root)
echo $root.left

proc build(arr:seq[int],dist:var Tree):void=
  var
    refnode:Tree
    ref_old:Tree
    lr:bool=false
  for x in arr:
    refnode=dist.left
    ref_old=dist
#    echo repr(refnode),"/",repr(ref_old)
    while refnode!=nil:
      if x<refnode.elem:
        lr=false
      elif refnode.elem<x:
        lr=true
      ref_old=refnode
      if lr:
        refnode=refnode.right
      else:
        refnode=refnode.left
    if lr:
      new(ref_old.right)
      refnode=ref_old.right
    else:
      new(ref_old.left)
      refnode=ref_old.left
    refnode.elem=x