Day.25 Binary Search Tree III

Binary Search Tree III

树主要有三种走访的方式，分别是InOrder、PreOrder、PostOrder，主要差别在於走访的顺序

InOrder

走访的顺序为: [1,3,4,5,8,9,12]
它会按照值的大小走访，如果你想知道树有什麽值，用InOrder可以一目了然

PreOrder

走访的顺序为: [5,3,1,4,9,8,12]
它是从上到下的走访，根节点开始，左节点走到底，再走右节点
当你要复制一颗树，用PreOrder很适合，只要你照它输出的顺序去insert，就可以产生一样的树

PostOrder

走访的顺序为: [1,4,3,8,12,9,5]
它是从下到上的走访，从左边最底下的节点开始上去，再到右边，最後才回到根节点

三种走访的实作方式基本上是一样～

程序:

func (t *BinarySearchTree) InOrder() {
	t.inOrderDFS(t.root)
}

func (t *BinarySearchTree) inOrderDFS(node *Node) {
	if node == nil {
		return
	}

	t.inOrderDFS(node.Left)
	fmt.Println(node.Val)
	t.inOrderDFS(node.Right)
}

func (t *BinarySearchTree) PreOrder() {
	t.preOrderDFS(t.root)
}

func (t *BinarySearchTree) preOrderDFS(node *Node) {
	if node == nil {
		return
	}

	fmt.Println(node.Val)
	t.preOrderDFS(node.Left)
	t.preOrderDFS(node.Right)
}

func (t *BinarySearchTree) PostOrder() {
	t.postOrderDFS(t.root)
}

func (t *BinarySearchTree) postOrderDFS(node *Node) {
	if node == nil {
		return
	}

	t.postOrderDFS(node.Left)
	t.postOrderDFS(node.Right)
	fmt.Println(node.Val)
}

func main() {
	tree := &BinarySearchTree{}
	tree.Insert(5)
	tree.Insert(3)
	tree.Insert(1)
	tree.Insert(4)
	tree.Insert(9)
	tree.Insert(8)
	tree.Insert(12)

	fmt.Println("InOrder:")
	tree.InOrder()
	fmt.Println("--------")

	fmt.Println("PreOrder:")
	tree.PreOrder()
	fmt.Println("--------")

	fmt.Println("PostOrder:")
	tree.PostOrder()
	fmt.Println("--------")
}

output:

InOrder:
1
3
4
5
8
9
12
--------
PreOrder:
5
3
1
4
9
8
12
--------
PostOrder:
1
4
3
8
12
9
5
--------

明天会讲二元树的删除～