2019.01.27 - For(;;);

生活总是充满了无穷无尽的困难，以及希望。

最近越发地清楚地意识到了自己换工作是多么迫切的一件事情（虽然18年的3月份就有此打算但是不知道为何精力不够或者说自控力不够强导致一直延期延期或者得过且过，一直没能下定决心）。通过又是一年的工作，平时的工作内容，考虑到薪资待遇以及自己能力的成长，越发觉得上海某地方银行的信用卡中心是个不宜久留的地方，不然自己的人生都得搭进去。简单分析有以下几个原因：

管理和“大”公司病。只注重文档和管理形式而非真的管理，管理异常混乱，各个团队各自为政，有能力的人得不到话语权反而是小丑一样只会装逼的人混的各种风生水起，排资论辈，各种规章流程规范满天飞，极度拖慢了各种事项的进展，同时也给开发人员带来了无穷无尽的杂活，常常忙了一天也不知道自己一天究竟做了什么，这是对生命的浪费。
薪资。当然，这个是我自己不够努力，在该学习的时候不学习没有一个好的学历和出身，所以显得非常廉价。但是我知道自己不只这个价钱，告诫自己：千里马拉习惯了磨，也就觉得自己是骡子。我相信自己的价值和能力。
团度氛围。本来刚入职的时候觉得整个项目组还是比较像一个大家庭的，但是莫名其妙的矛盾冲突越来越对，跟自己的项目组是这样，跟业务也是，跟测试也是，脾气越来越差，管理对自己的剥削越来越对，各种铁面制度或是瞎指挥，越来越让我觉得这边已经没有啥值得我留恋的。
技术成长。感觉自己技术的成长空间已经基本没有了（虽然浩哥~@404notfound还有很多很多值得我学的，但是目前为止我并不想走单纯后台java业务开发的线路），所以是时候走了。
还是要多看看别人的公司和氛围以及别人在做的事情的，总是重复一件事情慢慢地都忽视了自己一直没有进步。

今天（本篇文章也是拖延症晚期系列的产出）刷微博的时候发现离职根本不需要这么多理由（请原谅我加戏了。。）：

因此，下文将记录一些我在准备面试或者说各种自己以前欠下的债的弥补内容。

Tree(s)

treesort

参考： GOPL Page 101 ch4/treesort

代码实现如：

package treesort

type Tree struct {
	val         int
	left, right *Tree
}

func Add(root *Tree, val int) *Tree {
	if root == nil {
		t := new(Tree)
		t.val = val
		return t
	}
	if val < root.val {
		root.left = Add(root.left, val)
	} else {
		root.right = Add(root.right, val)
	}
	return root
}

func AppendValues(root *Tree, values []int) []int {
	if root != nil {
		values = AppendValues(root.left, values)
		values = append(values, root.val)
		values = AppendValues(root.right, values)
	}
	return values
}

func Sort(values []int) []int {
	var root *Tree
	for _, v := range values {
		root = Add(root, v)
	}
	values = AppendValues(root, values[:0])
	return values
}

Binary search tree

参考： 多动态图详细讲解二叉搜索树
 二叉查找树（BST）

代码实现如：

package bst

/**
二叉查找树的go实现，参考 https://lufficc.com/blog/binary-search-tree 及 http://songlee24.github.io/2015/01/13/binary-search-tree/
完成编写
 */
import (
	"fmt"
	"math"
	"math/rand"
	"strconv"
	"time"
)


type Node struct {
	key    int
	left   *Node
	right  *Node
	parent *Node
}
type Tree struct {
	root *Node
}
type ITree interface {
	New() ITree
	Insert(k int)
	Search(k int) *Node
	Delete(n *Node)
	Min() *Node
	Max() *Node
	TraversePreorder()
	TraverseInorder()
	TraversePostorder()
	String() string
}

func (t *Tree) String() string {
	return walk(t.root, 0)
}

func walk(n *Node, nos int) string {
	var s string
	if n == nil {
		return ""
	}
	//	fmt.Printf("%d\t%+v\t%+v\t%+v\n", nos, n, n.left, n.right)
	if n.parent == nil {
		s += strconv.Itoa(n.key) + "\n"
	}
	if n.left != nil {
		if nos != 0 {
			s += fmt.Sprintf("%*c", nos, ' ')
		}
		s += strconv.Itoa(n.left.key)
	}
	if n.right != nil {
		s += fmt.Sprintf("%*c", 4+nos, ' ')
		s += strconv.Itoa(n.right.key)
	}
	s += "\n"
	s += walk(n.left, nos)
	bon := 0
	if n.left != nil {
		bon = int(math.Log10(float64(n.left.key))) + 1
	}
	s += walk(n.right, nos+4+bon)

	return s
}

func (t *Tree) Delete(n *Node) {
	if n == nil {
		return
	}
	if n.left == nil && n.right == nil {
		if n.parent != nil {
			if n.parent.left == n {
				n.parent.left = nil
			} else {
				n.parent.right = nil
			}
		} else {
			t = nil
		}
	} else if n.left != nil && n.right == nil {
		n.left.parent = n.parent
		if n.parent != nil {
			if n.parent.left == n {
				n.parent.left = n.left
			} else {
				n.parent.right = n.left
			}
		} else {
			t = &Tree{n.left}
		}

	} else if n.left == nil && n.right != nil {
		n.right.parent = n.parent
		if n.parent != nil {
			if n.parent.left == n {
				n.parent.left = n.right
			} else {
				n.parent.right = n.right
			}
		} else {
			t = &Tree{n.right}
		}

	} else {
		suc := successor(n)
		n.key = suc.key
		t.Delete(suc)
	}

}

func successor(n *Node) *Node {
	if n == nil {
		return n
	}
	if n.right != nil {
		return min(n.right)
	} else {
		p := n.parent
		for p != nil && p.right == n {
			n = p
			p = n.parent
		}
		return p
	}
}

func predecessor(n *Node) *Node {
	if n == nil {
		return n
	}
	if n.left != nil {
		return max(n.left)
	} else {
		p := n.parent
		for p != nil && p.left == n {
			n = p
			p = n.parent
		}
		return p
	}
}

func (t *Tree) Min() *Node {
	return min(t.root)
}

func min(n *Node) *Node {
	if n.left == nil {
		return n
	}
	return min(n.left)
}

func (t *Tree) Max() *Node {
	return max(t.root)
}

func max(n *Node) *Node {
	if n.right == nil {
		return n
	}
	return max(n.right)
}

func createTree() *Tree {
	t := new(Tree)
	var _ ITree = t
	return t
}

func (t *Tree) New() ITree {
	return createTree()
}

func (t *Tree) Search(k int) *Node {
	return search(t.root, k)
}

func search(n *Node, k int) *Node {
	if n == nil || n.key == k {
		return n
	}
	if n.key > k {
		return search(n.left, k)
	} else {
		return search(n.right, k)
	}
}

func (t *Tree) Insert(k int) {
	if t.root == nil {
		t.root = Insert(k, t.root)
	} else {
		Insert(k, t.root)
	}
}
func Insert(k int, n *Node) *Node {
	if n == nil {
		return &Node{k, nil, nil, n}
	}
	if k == n.key {
		return nil
	} else if k > n.key {
		if n.right == nil {
			n.right = &Node{k, nil, nil, n}
		} else {
			Insert(k, n.right)
		}
	} else {
		if n.left == nil {
			n.left = &Node{k, nil, nil, n}
		} else {
			Insert(k, n.left)
		}
	}
	return nil
}

func (t *Tree) TraversePreorder() {
	fmt.Print("Pre order: ")
	traversePreorder(t.root)
	fmt.Println()
}

func traversePreorder(n *Node) {
	if n == nil {
		return
	}
	fmt.Print(n.key, " ")
	traversePreorder(n.left)
	traversePreorder(n.right)
}

func (t *Tree) TraverseInorder() {
	fmt.Print("In order: ")
	traverseInorder(t.root)
	fmt.Println()
}

func traverseInorder(t *Node) {
	if t == nil {
		return
	}
	traverseInorder(t.left)
	fmt.Print(t.key, " ")
	traverseInorder(t.right)
}

func (t *Tree) TraversePostorder() {
	fmt.Print("Post order: ")
	traversePostorder(t.root)
	fmt.Println()
}

func traversePostorder(n *Node) {
	if n == nil {
		return
	}
	traversePostorder(n.left)
	traversePostorder(n.right)
	fmt.Print(n.key, " ")
}
func genRandomNums(n int) []int {
	var array []int
	for i := 0; i < n; i++ {
		array = append(array, i+1)
	}
	r := rand.New(rand.NewSource(time.Now().Unix()))
	for i := n - 1; i > -1; i-- {
		j := r.Int() % (i + 1)
		array[i], array[j] = array[j], array[i]
	}
	return array
}

Contents

Tree(s)