Day.24 Binary Search Tree II

今天来实作二元树～

首先来定义一下资料结构

type Node struct {
	Left  *Node
	Right *Node
	Val   int
}

type BinarySearchTree struct {
	root *Node
}

我们需要来insert新的节点，还记得比较小的要放在左边，比较大的放在右边吗？
insert的时候就是要一个一个node做判断，去找到适合放的位置，如果插入值比目前node的值小，就看它左边的节点是不是空的，如果是就可以放，否则再往左边的node继续找。
如上图，假设我们现在要insert一个5的值，那走访的顺序为: 10->3->4 放在右边节点

新增:

func (t *BinarySearchTree) Insert(val int) {
	newNode := &Node{
		Val: val,
	}

	if t.root == nil {
		t.root = newNode
		return
	}

	node := t.root
	for {
		if val == node.Val {
			return
		}

		if val < node.Val {
			// 左边刚好是空的
			if node.Left == nil {
				node.Left = newNode
				return
			}

			// 继续往左找
			node = node.Left
		} else {
			// 右边刚好是空的
			if node.Right == nil {
				node.Right = newNode
				return
			}

			// 继续往右找
			node = node.Right
		}
	}
}

搜寻:

func (t *BinarySearchTree) Find(val int) bool {
	node := t.root

	for {
		if node == nil {
			return false
		}

		if node.Val == val {
			return true
		}

		if val < node.Val {
			node = node.Left
		} else {
			node = node.Right
		}
	}
}

今天先到这边，明天再继续会讲树～