Learn-Algorithm · houming818 · Jun 11, 2014 · Jun 12, 2014 · Jun 17, 2014 · Jun 21, 2014
diff --git a/1-树/0-二叉树/stduolc/binaryTree.go b/1-树/0-二叉树/stduolc/binaryTree.go
@@ -0,0 +1,56 @@
+package main
+
+import (
+	"fmt"
+)
+
+type Node struct {
+	left  *Node
+	right *Node
+	val   byte
+}
+
+func (this *Node) preOrder() {
+	fmt.Print(string(this.val))
+	if this.left != nil {
+		this.left.preOrder()
+	}
+	if this.right != nil {
+		this.right.preOrder()
+	}
+}
+
+func (this *Node) inOrder() {
+	if this.left != nil {
+		this.left.inOrder()
+	}
+	fmt.Print(string(this.val))
+	if this.right != nil {
+		this.right.inOrder()
+	}
+}
+
+func (this *Node) postOrder() {
+	if this.left != nil {
+		this.left.postOrder()
+	}
+	if this.right != nil {
+		this.right.postOrder()
+	}
+	fmt.Print(string(this.val))
+}
+
+func main() {
+	a := &Node{nil, nil, 'a'}
+	a.left = &Node{nil, nil, 'b'}
+	a.left.left = &Node{nil, nil, 'c'}
+	a.left.right = &Node{nil, nil, 'd'}
+	a.right = &Node{nil, nil, 'e'}
+	a.right.left = &Node{nil, nil, 'f'}
+	a.right.right = &Node{nil, nil, 'g'}
+	a.preOrder()
+	fmt.Println()
+	a.inOrder()
+	fmt.Println()
+	a.postOrder()
+}
diff --git a/1-树/1-二叉查找树BST/stduolc/BinarySearchTree.go b/1-树/1-二叉查找树BST/stduolc/BinarySearchTree.go
@@ -0,0 +1,133 @@
+package main
+
+import (
+	"fmt"
+)
+
+type Node struct {
+	left  *Node
+	right *Node
+	val   byte
+}
+
+func (this *Node) InOrder() {
+	if this.left != nil {
+		this.left.InOrder()
+	}
+	fmt.Println(this)
+	if this.right != nil {
+		this.right.InOrder()
+	}
+}
+
+func Insert(root *Node, target *Node) {
+	if nil == target {
+		return
+	}
+	if root == nil {
+		fmt.Println("OutOfMyMind")
+		return
+	}
+	if root.val < target.val {
+		if root.right != nil {
+			Insert(root.right, target)
+			return
+		} else {
+			root.right = target
+			return
+		}
+	}
+	if root.val > target.val {
+		if root.left != nil {
+			Insert(root.left, target)
+			return
+		} else {
+			root.left = target
+			return
+		}
+	}
+}
+
+// If the Tree have the target node, this function will return the father node of the target node.
+// If the Tree don't have the target node, this function will return nil for nothing.
+func Search(root, target *Node) *Node {
+	if nil == root {
+		return nil
+	}
+	if root.val < target.val {
+		return Search(root.right, target)
+	}
+	if root.val > target.val {
+		return Search(root.left, target)
+	}
+	if root.val == target.val {
+		return root
+	}
+	fmt.Println("Search is OutOfMyMind")
+	return nil
+}
+
+func transform(root *Node) *Node {
+	pos := root.right
+	for pos.left != nil {
+		pos = pos.left
+	}
+	pos.left = root.left
+	return root.right
+}
+
+func Delete(root, target *Node) *Node {
+	if nil == target {
+		return nil
+	}
+	if nil == root {
+		return nil
+	}
+
+	if root.val > target.val {
+		tmp := Delete(root.left, target)
+		if tmp != nil {
+			tmp.left = tmp
+		}
+		return nil
+	} else if root.val < target.val {
+		tmp := Delete(root.right, target)
+		if tmp != nil {
+			root.right = tmp
+		}
+		return nil
+	} else {
+		tmp := transform(root)
+		return tmp
+	}
+	fmt.Println("Delete OutOfMyMind")
+	return nil
+}
+
+func main() {
+	root := &Node{nil, nil, 'a'}
+	Insert(root, &Node{nil, nil, 'd'})
+	Insert(root, &Node{nil, nil, 'e'})
+	Insert(root, &Node{nil, nil, 'f'})
+	Insert(root, &Node{nil, nil, 'g'})
+	Insert(root, &Node{nil, nil, 'h'})
+	Insert(root, &Node{nil, nil, 'i'})
+	Insert(root, &Node{nil, nil, 'c'})
+	Insert(root, &Node{nil, nil, 'b'})
+
+	tmp := Search(root, &Node{nil, nil, 'e'})
+	if tmp != nil {
+		fmt.Println("Test Pass:", tmp)
+	} else {
+		fmt.Println("Test fail")
+	}
+
+	Delete(root, &Node{nil, nil, 'e'})
+
+	tmp = Search(root, &Node{nil, nil, 'e'})
+	if tmp == nil {
+		fmt.Println("Test Pass: Delete success!")
+	} else {
+		fmt.Println("Test fail")
+	}
+}
diff --git a/1-树/2-平衡树AVL/stduolc/avlTree.go b/1-树/2-平衡树AVL/stduolc/avlTree.go
@@ -0,0 +1,155 @@
+/***
+* 参考 http://zh.wikipedia.org/wiki/AVL%E6%A0%91
+**/
+package main
+
+import (
+	"fmt"
+)
+
+type KeyType int
+
+type Avl struct {
+	key    KeyType
+	height int
+	lchild *Avl
+	rchild *Avl
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	} else {
+		return b
+	}
+}
+
+func height(root *Avl) int {
+	if root != nil {
+		return root.height
+	}
+	return -1
+}
+
+// 旋转时，不要忘记改变height
+func LLRotate(root *Avl) *Avl {
+	if root == nil {
+		return nil
+	}
+
+	if root.lchild == nil {
+		return root
+	}
+
+	pivot := root.lchild
+	b := pivot.rchild
+	pivot.rchild = root
+	root.lchild = b
+	pivot.height = pivot.height + 1
+	root.height = root.height - 1
+	return pivot
+}
+
+func RRRotate(root *Avl) *Avl {
+	if root == nil {
+		return nil
+	}
+
+	if root.rchild == nil {
+		return root
+	}
+
+	pivot := root.rchild
+	b := pivot.lchild
+	pivot.lchild = root
+	root.rchild = b
+	pivot.height = pivot.height + 1
+	root.height = root.height - 1
+	return pivot
+}
+
+func LRRotate(root *Avl) *Avl {
+	if root == nil {
+		return nil
+	}
+
+	tmp := RRRotate(root.lchild)
+	root.lchild = tmp
+	ret := LLRotate(root)
+	return ret
+}
+
+func RLRotate(root *Avl) *Avl {
+	if root == nil {
+		return nil
+	}
+	tmp := LLRotate(root.rchild)
+	root.rchild = tmp
+	ret := RRRotate(root)
+	return ret
+}
+
+func Insert(root *Avl, key KeyType) *Avl {
+	if root == nil {
+		root = &Avl{key, 0, nil, nil}
+		return root
+	}
+
+	if root.key == key {
+		return root
+	}
+
+	if key > root.key {
+		root.rchild = Insert(root.rchild, key)
+		if height(root.rchild)-height(root.lchild) == 2 {
+			if key > root.rchild.key {
+				root = RRRotate(root)
+			} else {
+				root = RLRotate(root)
+			}
+		}
+	}
+
+	if key < root.key {
+		root.lchild = Insert(root.lchild, key)
+		if height(root.lchild)-height(root.rchild) == 2 {
+			if key < root.lchild.key {
+				root = LLRotate(root)
+			} else {
+				root = LRRotate(root)
+			}
+		}
+	}
+
+	root.height = max(height(root.rchild), height(root.lchild)) + 1
+	return root
+}
+
+func Delete(root *Avl, key KeyType) *Avl {
+	return nil
+}
+
+// 抄袭的lidashuang，自己觉得，不会这么写，也不会写的这么有意思。
+type action func(node *Avl)
+
+func inOrder(root *Avl, action action) {
+	if root == nil {
+		return
+	}
+
+	inOrder(root.lchild, action)
+	action(root)
+	inOrder(root.rchild, action)
+}
+
+func main() {
+	var root *Avl
+	keys := []KeyType{2, 6, 1, 3, 5, 7, 16, 15, 14, 13, 12, 11, 8, 9, 10}
+	for _, key := range keys {
+		root = Insert(root, key)
+	}
+
+	inOrder(root, func(node *Avl) {
+		fmt.Println(node.key, node.height)
+	})
+}