本文使用Go语言进行描述
1) 二叉树创建
有如下数列,创建一颗二叉查找树
{50,22,30,16,18,43,56, 112,91,32,71,28}
使用如下的规则进行创建:
0)没有键值相等的结点
1)如果要插入的节点键值比当前节点小,则插入到当前节点的左子树,否则插入到当前节点的右子树
首先,定义二叉树节点的数据结构
type BNode struct{ key int value string lt, rt *BNode }
向二叉树添加新节点的操作如下
func add_node(node *BNode, key int) (*BNode) { if nil == node { var n BNode n.key = key node = &n } else if node.key > key { node.lt = add_node(node.lt, key) } else { node.rt = add_node(node.rt, key) } return node }
所以建立二叉查找树的过程如下
func main(){ list := []int {50,22,30,16,18,43,56, 112,91,32,71,28} var root * BNode = nil for _, v := range list { root = add_node(root, v); } }
其中 BNode 结构中的 value 没有被使用。
2) 二叉树遍历
二叉树建立好了,但是是存在于内存中,怎样才能知道创建的没问题呢?
我们知道,对于一棵二叉树,其(中根遍历 + 先根遍历),或者(中根遍历 + 后根遍历) 可以逆向推导出二叉树的结构。 所以接下来,我们要对二叉树进行一次中根遍历和一次先根遍历,并通过这两组数据验证下二叉树结构。
先根遍历的代码如下:
func pre_list(node *BNode) { if nil == node { return } fmt.Printf("%d ", node.key); pre_list(node.lt) pre_list(node.rt) }
中根遍历的代码如下:
func mid_list(node *BNode) { if nil == node { return } mid_list(node.lt) show_node(node) mid_list(node.rt) }
主函数代码如下:
func main(){ list := []int {50,22,30,16,18,43,56, 112,91,32,71,28} var root * BNode = nil for _, v := range list { root = add_node(root, v); } pre_list(root) fmt.Fprintf(os.Stderr, "\n") mid_list(root); fmt.Fprintf(os.Stderr, "\n") }
执行结果如下:
$ go run make_b_tree.go 50 22 16 18 30 28 43 32 56 112 91 71 16 18 22 28 30 32 43 50 56 71 91 112
我们可以根据上面的结果动手在纸上画一下,看看有没有创建成功。呵呵,开个玩笑。后面会讲如何重建二叉树。
3) 画出二叉树
除了动手画出来,我们还可以借助一些工具把它画出来,比如 Graphviz 。
下面这段代码是使用先根遍历的方法画出二叉树的代码,其作用是输出一段 dot 脚本。
func show_dot_node(node *BNode){ if nil == node { return } fmt.Printf(" %d[label=\"<f0> | <f1> %d | <f2> \"];\n", node.key, node.key) } func show_dot_line(from , to *BNode, tag string) { if nil == from || nil == to { return } fmt.Printf(" %d:%s -> %d:f1;\n", from.key, tag, to.key) } func show_list(node * BNode) { if nil == node { return } show_dot_node(node) show_dot_line(node, node.lt, "f0:sw") show_dot_line(node, node.rt, "f2:se") show_list(node.lt) show_list(node.rt) } func make_dot(root * BNode) { fmt.Printf("digraph G{\n\ node[shape=record,style=filled,color=cadetblue3,fontcolor=white];\n") show_list(root) fmt.Printf("}\n") }
主函数则变更如下:
func main(){ list := []int {50,22,30,16,18,43,56, 112,91,32,71,28} var root * BNode = nil for _, v := range list { root = add_node(root, v); } make_dot(root); }
执行结果如下:
digraph G{ node[shape=record,style=filled,color=cadetblue3,fontcolor=white]; 50[label="<f0> | <f1> 50 | <f2> "]; 50:f0:sw -> 22:f1; 50:f2:se -> 56:f1; 22[label="<f0> | <f1> 22 | <f2> "]; 22:f0:sw -> 16:f1; 22:f2:se -> 30:f1; 16[label="<f0> | <f1> 16 | <f2> "]; 16:f2:se -> 18:f1; 18[label="<f0> | <f1> 18 | <f2> "]; 30[label="<f0> | <f1> 30 | <f2> "]; 30:f0:sw -> 28:f1; 30:f2:se -> 43:f1; 28[label="<f0> | <f1> 28 | <f2> "]; 43[label="<f0> | <f1> 43 | <f2> "]; 43:f0:sw -> 32:f1; 32[label="<f0> | <f1> 32 | <f2> "]; 56[label="<f0> | <f1> 56 | <f2> "]; 56:f2:se -> 112:f1; 112[label="<f0> | <f1> 112 | <f2> "]; 112:f0:sw -> 91:f1; 91[label="<f0> | <f1> 91 | <f2> "]; 91:f0:sw -> 71:f1; 71[label="<f0> | <f1> 71 | <f2> "]; }
我们把这段 dot 代码写入文件,btree.gv ,执行如下命令:
dot -Tpng -obtree.png btree.gv
成功的话,则会生成 btree.png 图片,如下所示:
4) 重建二叉树
下面根据我们得到的(中根遍历)和(先根遍历)来重建二叉树,两组数据如下:
pre : 50 22 16 18 30 28 43 32 56 112 91 71 mid : 16 18 22 28 30 32 43 50 56 71 91 112
重建规则如下:
0)没有重复的数字
1)从(先根遍历)的数组 pre_list 中取开头的第一个数字A=pre_list[0], 这个数 A 就是这个数组所组成的树BT的树根
2)从(中根遍历)的数组 mid_list 中找到第 1)步的数字A。 在mid_list中,所有在 A 左边的数字都属于 BT 的左子树lt, 所有在 A 右边的数字,都属于 BT 的的右子树rt。
3)递归解析lt和rt两组数字
重建二叉树的代码如下:
定义二叉树节点结构和辅助函数:
type BNode struct{ key int value string lt, rt *BNode } func show_node(node * BNode) { if nil == node { return } fmt.Fprintf(os.Stderr, "%d ", node.key) } func pre_list(root *BNode) { if nil == root { return } show_node(root) pre_list(root.lt) pre_list(root.rt) } func mid_list(root *BNode) { if nil == root { return } mid_list(root.lt) show_node(root) mid_list(root.rt) }
重建二叉树
//查找一个数字在数列中的位置: func get_num_pos(list []int, num int) (int) { var pos int = -1 for i, v := range list { if num == v { pos = i break } } return pos; } //递归建树 func rebuild_tree(tree * BNode, pre, mid []int) (* BNode) { if len(pre) <= 0 || len(mid) <= 0 { return tree } //(先根遍历)的第一个数字就是这棵树的树根 root := pre[0] var pos int if pos = get_num_pos(mid, root); pos < 0 { return tree } if nil == tree { var n BNode n.key = root tree = &n } //重建左子树 tree.lt = rebuild_tree(tree.lt, pre[1 : 1 + pos], mid[:pos]) //重建右子树 tree.rt = rebuild_tree(tree.rt, pre[1 + pos :], mid[pos + 1:]) return tree } func main() { pre := []int {50, 22, 16, 18, 30, 28, 43, 32, 56, 112, 91, 71} mid := []int {16, 18, 22, 28, 30, 32, 43, 50, 56, 71, 91, 112} tree := rebuild_tree(nil, pre, mid) //重建后再进行一次(先根遍历)和一次(中根遍历),检查输出结果是否和我们输入的相同。 pre_list(tree) fmt.Fprintf(os.Stderr, "\n") mid_list(tree) fmt.Fprintf(os.Stderr, "\n") }
执行代码如下:
$ go run rbulid_binary_tree.go 50 22 16 18 30 28 43 32 56 112 91 71 16 18 22 28 30 32 43 50 56 71 91 112
看样子结果相同 ~.~
5) 算法复杂度分析
接下来分析下二叉查找树的空间复杂度和时间复杂度。
5.1)空间复杂度
空间复杂度比较好分析。我们在建树的时候,是不是需要对每一个数据申请一次内存呢。 每个数据一次,那就是有多少数据,就要申请多少次,有n个数据就要 申请n次, 所以空间光是申请用于存放数据的内存次数就是n,这个和数据的规模是正相关的, 并且关系是O(x * n),其中x是每个数据占用的内存数量。因为这个x在数据结构不变的情况下是不变的, 是不会随着数据规模而变化的,那就可以忽略,因为x是个常数,与n无关。 所以只是申请存放数据的空间的空间复杂度为O(n)。
那还有什么地方需要空间呢?就是递归的时候,需要栈空间。 树每深一层,就需要递归一次,也就需要保存一次栈空间。 在平均情况下,树的深度是lgN。但是在极端情况下,树的深度可是N啊。请看下面的图。
a树就是最差的树,这哪儿还像是一棵树啊,基本就是链表了;而b树就是一棵好树,深度最优。
所以最坏的递归建树栈空间也是O(n),不过最好的是O(lgN)。
综合来说,空间是[O(n)+O(lgN)] ~ [2 O(n)],这里要取比较大的一个,也就是2O(n),也就是O(n)。
5.2) 时间复杂度
时间复杂度主要是考察增、删、查三个操作所面临的时间复杂度。 无论增加一个节点还是删除一个节点,首先都是查询这个节点的位置。所以我们首先介绍查询一个节点的时间复杂度。
5.2.1)查询一个节点的时间复杂度
还是以上图为代表,如果要查询其中的某一个节点,比如要查询b1,需要比较的节点一次是b4->b2->b1, 所以查询b1节点需要的时间是3。如果查询b4呢,那就只需要和b4比较一次就可以了。 所以查询一个节点所需要的最大时间,是和树的深度成正比的。那么在上图b树上,时间复杂度就是O(lnN)。 那么在a树上查询呢?查a1的话,只需要和a1比较一次就好了,但是如果要查a7呢,那就需要查询7次了。 所以二叉查找树的时间复杂度是O(lgN) ~ O(n),取最坏的情况,那就是O(n)了。
5.2.2)增加一个节点的时间复杂度
增加一个节点,需要查询到该节点需要插入的位置,所以花费时间应该是在查询的基础上在+1,所以是O(n)。
5.2.3)删除一个节点的时间复杂度
二叉查找树删除节点可以分为三种情况:
a)要删除的目标节点是叶子节点。
此时只需要把这个节点删除即可,因为此节点没有子树,直接删除就可以了。如下图,删除节点2。
b)要删除的目标节点有一个子树。
i)如果只有左子树,就让这个节点的父节点指向这个节点的左子树。
ii)如果只有右子树,就让这个节点的父节点指向这个节点的右子树。如下图,删除节点3。
c)要删除的目标节点有两个子树。
i)方法一,找到要删除的节点的前驱,这个节点的前驱肯定是没有右子树的,用这个节点的前驱替换这个节点,并删除这个节点。
ii)方法二,找到要删除的节点的后继,这个节点的后继肯定是没有左子树的,用这个节点的后继替换这个节点,并删除这个节点。
前驱和后继的含义:
节点key的前驱,就是中序遍历时,比key小的所有节点中最大的那个节点。
节点key的后继,就是中序遍历时,比key小的所有节点中最大的那个节点。
无论是用前驱进行替换,还是用后继进行替换,思路都是情况c)转换为情况a)或者情况b)。
使用前驱进行替换:
使用后继进行替换:
删除操作说了,那么时间复杂度呢
因为删除一个节点的时候,首先需要进行查找,之后或者直接删除这个节点, 或者使用前驱或者后继替换后进行删除,首先查找的时间复杂度是O(lgN), 直接删除的时间复杂度是O(1)。 替换删除呢,因为替换删除的时候,查找前驱或者后继的时候, 是在当前节点的基础上进行查找的,所以查找前驱或后继的时间加上查找要删除的节点的时间, 一共是O(lgN)。最坏是O(N)。
所以删除操作的时间复杂度在O(lgN)~O(N)之间。
平均来说会小于O(N),更接近O(lnN)一些。
删除一个节点(采用前驱节点替换) Go语言描述如下:
//根据 key 值移除一个节点 func remove_node(tree * BNode, key int) (n, t *BNode){ if nil == tree { return nil,nil } //找到 key 所在的节点,删除它 if key == tree.key { n, tree = del_node(tree) } else if key > tree.key { n, tree.rt = remove_node(tree.rt, key) } else { n, tree.lt = remove_node(tree.lt, key) } return n, tree } //删除一个节点的操作 func del_node(tree * BNode) (n, t*BNode) { if nil == tree { return nil, nil } //直接删除叶子节点 if nil == tree.lt && nil == tree.rt { return tree, nil } //不是叶子节点,说明有子树存在 //没有左子树,说明只有右子树,直接返回右子树 if nil == tree.lt { return tree, tree.rt } //只有左子树存在,直接返回左子树 if nil == tree.rt { return tree, tree.lt } //左右子树都存在,获取前驱节点 n, t = get_pre_node(tree.lt) n.lt = t n.rt = tree.rt return tree, n } //获取前驱节点 func get_pre_node(node * BNode) (n, t *BNode) { if nil == node { return nil, nil } if nil != node.rt { n, node.rt = get_pre_node(node.rt) return n, node } //删除找到的前驱节点,并删除此节点后返回 return del_node(node) }
可以调用remove_node(tree, key)函数删除key对应的节点,并且返回删除的节点。
本文转自郝峰波博客园博客,原文链接:http://www.cnblogs.com/fengbohello/p/5866592.html,如需转载请自行联系原作者