二叉树的层次遍历算法
二叉树的层次遍历算法有如下三种方法：
给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：
对此二叉树遍历的结果应该是：
1，
2 ， 3
4， 5， 6
7， 8
第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：
[cpp] view plaincopy
int print_at_level(Tree T, int level) {
if (!T || level 《 0)
return 0;
if (0 == level) {
cout 《《 T-》data 《《 “ “;
return 1;
}
return print_at_level(T-》lchild, level - 1) + print_at_level(T-》rchild, level - 1);
如果我们成功的打印了给定的层次，那么就返回非0的正值，如果失败返回0。有了这个思路，我们就可以应用一个循环，来打印这颗树的所有层的节点，但是有个问题就是我们不知道这棵二叉树的深度，怎么来控制循环使其结束呢，仔细看一下print_at_level，如果指定的Tree是空的，那么就直接返回0，当返回0的时候，我们就结束循环，说明没有节点可以打印了。-二叉树
[cpp] view plaincopy
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout 《《 endl;
}
以上的方法可以很清楚的看出，存在重复访问的情况，就是第0层访问的次数最多，第1层次之。所以这个递归的方法不是很有效的方法。
第二种方法：我们可以设置两个队列，想象一下队列的特点，就是先进先出，首先把第0层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。-算法
[cpp] view plaincopy
void print_by_level_2(Tree T) {
deque《tree_node_t*》 q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout 《《 temp-》data 《《 “ “;
if (temp-》lchild)
q_second.push_back(temp-》lchild);
if (temp-》rchild)
q_second.push_back(temp-》rchild);
}
cout 《《 endl;
q_first.swap(q_second);
}
}
第三种方法就是设置双指针，一个指向访问当层开始的节点，一个指向访问当层结束节点的下一个位置：
这是第一层访问的情况，当访问第0层之后的结构如下，把第0层的所有子节点加入之后：
访问完第1层之后：
之后大家就可以自己画图了，下面给出程序代码：
[cpp] view plaincopy
void print_by_level_3(Tree T) {
vector《tree_node_t*》 vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur 《 vec.size()) {
end = vec.size();
while (cur 《 end) {
cout 《《 vec[cur]-》data 《《 “ “;
if (vec[cur]-》lchild)
vec.push_back(vec[cur]-》lchild);
if (vec[cur]-》rchild)
vec.push_back(vec[cur]-》rchild);
cur++;
}
cout 《《 endl;
}
}
最后给出完成代码的测试用例：124##57##8##3#6##
[cpp] view plaincopy
#include《iostream》
#include《vector》
#include《deque》
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == ’#’) {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)-》data = c;
create_tree(&(*T)-》lchild);
create_tree(&(*T)-》rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout 《《 T-》data 《《 “ “;
print_tree(T-》lchild);
print_tree(T-》rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level 《 0)
return 0;
if (0 == level) {
cout 《《 T-》data 《《 “ “;
return 1;
}
return print_at_level(T-》lchild, level - 1) + print_at_level(T-》rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout 《《 endl;
}
void print_by_level_2(Tree T) {
deque《tree_node_t*》 q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout 《《 temp-》data 《《 “ “;
if (temp-》lchild)
q_second.push_back(temp-》lchild);
if (temp-》rchild)
q_second.push_back(temp-》rchild);
}
cout 《《 endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector《tree_node_t*》 vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur 《 vec.size()) {
end = vec.size();
while (cur 《 end) {
cout 《《 vec[cur]-》data 《《 “ “;
if (vec[cur]-》lchild)
vec.push_back(vec[cur]-》lchild);
if (vec[cur]-》rchild)
vec.push_back(vec[cur]-》rchild);
cur++;
}
cout 《《 endl;
}
}
int main(int argc, char *argv) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout 《《 endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
迪杰斯特拉算法的定义
Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。-二叉树
非对称加密的主要算法有哪些
非对称加密（公钥加密）：指加密和解密使用不同密钥的加密算法，也称为公私钥加密。假设两个用户要加密交换数据，双方交换公钥，使用时一方用对方的公钥加密，另一方即可用自己的私钥解密。如果企业中有n个用户，企业需要生成n对密钥，并分发n个公钥。假设A用B的公钥加密消息，用A的私钥签名，B接到消息后，首先用A的公钥验证签名，确认后用自己的私钥解密消息。由于公钥是可以公开的，用户只要保管好自己的私钥即可，因此加密密钥的分发将变得 十分简单。同时，由于每个用户的私钥是唯一的，其他用户除了可以通过信息发送者的公钥来验证信息的来源是否真实，还可以通过数字签名确保发送者无法否认曾发送过该信息。
-算法
