关于碰到的一次二叉树的优化
关于碰到的一次二叉树的优化……
Breadth first search and depth first search
转载自ICS161,学英语,自娱自乐
Traversal of graphs and digraphs
To traverse(遍历) means to visit the vertices in some systematic order. You should be familiar with various traversal methods for trees:
preorder: visit each node before its children.
postorder: visit each node after its children.
inorder (for binary trees only): visit left subtree, node, right subtree.
We also saw another kind of traversal, topological ordering(拓扑排序), when I talked about shortest paths.
Today, we'll see two other traversals: breadth first search (BFS) and depth first search (DFS). Both of these construct spanning trees with certain properties useful in other graph algorithms. We'll start by describing them in undirected graphs, but they are both also very useful for directed graphs.
Git 小结
这两天看了廖雪峰老师的 Git 教程，受益匪浅。
以下为常用基本命令总结：
- 创建本地版本库：
git init - 添加文件到库：
git add <file>，git commit -m "messages" - 查看工作区状态：
git status - 查看修改内容：
git diff - 查看提交历史：
git log - 返回历史版本：
git reset --hard commit_id - 查看返回历史：
git relog - 丢弃工作区修改：
git check -- file - 丢弃暂存区修改：
git reset HEAD file - 删除一个文件：
git rm - 关联一个远程库：
git remote add origin git@server:path/repo.git - 关联后第一次推送：
git push -u origin master - 之后进行推送：
git push origin master - 克隆远程库：
git clone ssh://user@domain.com/repo.git - 查看分支：
git branch - 创建分支：
git branch <name> - 切换分支：
git checkout <name> - 创建+切换分支：
git checkout -b <name> - 合并某分支到当前分支：
git merge <name> - 删除分支：
git branch -d <name> - 新建标签：
git tag <name>默认为HEAD - 指定标签信息：
git tag -a <tagname> -m "balabala……" - 查看所有标签：
git tag - 推送全部未推送过的本地标签：
git push origin --tags - 删除本地标签：
git tag -d <tagname> - 删除远程标签：
git push origin :refs/tags/<tagname>
在博客中引用 Gist 代码块
Huffman 树
概念
哈夫曼树是带权路径长度 WPL（Weighted Path Length）最小的二叉树，也称为最优二叉树。
如下图：
它们的带权路径长度分别为：
图a： WPL = 5*2 + 7*2 + 2*2 + 13*2 = 54
图b： WPL = 5*3 + 2*3 + 7*2 + 13*1 = 48
可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)