本文目录
- 什么叫遍历算法(最好有例子)
- C语言的遍历算法
- 二叉树遍历算法，就是给定两种遍历结果求另一种遍历顺序
- 二叉树的层次遍历算法
- 图遍历的算法
- 数据结构中“遍历“是什么意思
- 怎么用c语言实现二叉树的遍历
- 急求C语言写二叉树的遍历
- 如何用C语言实现层次遍历二叉树
- C语言 二叉树 遍历问题
什么叫遍历算法(最好有例子)
遍历算法：所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。当然遍历的概念也适合于多元素集合的情况，如数组。
遍历算法概念延伸：
图遍历：图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。
举例：
遍历二叉树搜索路线：
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：⑴访问结点本身（N），⑵遍历该结点的左子树（L），⑶遍历该结点的右子树（R）。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三种次序与后三种次序对称。
遍历二叉树的执行踪迹三种递归遍历算法的搜索路线相同（如下图虚线所示）。具体线路为：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。
C语言的遍历算法
思路1：写出所有24种4个数的排列，存到一个数组里，假如数组是P；那么可以for(i=0;i《24;i++)for(j=0;j《24;j++)for(k=0;k《24;k++)三层循环，P=0;}return;}调用的时候调用dfs(0,0)
二叉树遍历算法，就是给定两种遍历结果求另一种遍历顺序
首先从前序的第一个确定二叉树的根A，回到中序切割，将二叉树分为三部分：
左子树的中序DBGE，根A，右子树的中序CHF
再由左子树的前序可知左子树的根为B，于是左子树的中序被再次切分为三部分：
左子树的左子树中序D，左子树的根B，左子树的右子树的中序GE
类似地，由右子树的前序可知右子树的根为C，于是右子树的中序也被切分为三部分：
右子树的左子树为空，右子树的根C，右子树的左子树的中序HF
继续切分下去：GE的根为E、HF的根为F，直到每棵子树只有一个结点为止，最终得到的完整二叉树如下：
于是后序遍历序列为：DGEBHFCA
二叉树的层次遍历算法
二叉树的层次遍历算法有如下三种方法：
给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：
对此二叉树遍历的结果应该是：
1，
2 ， 3
4， 5， 6
7， 8
第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：
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的时候，我们就结束循环，说明没有节点可以打印了。
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层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。
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层之后：
之后大家就可以自己画图了，下面给出程序代码：
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-》data 《《 “ “;
if (vec-》lchild)
vec.push_back(vec-》lchild);
if (vec-》rchild)
vec.push_back(vec-》rchild);
cur++;
}
cout 《《 endl;
}
}
最后给出完成代码的测试用例：124##57##8##3#6##
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-》data 《《 “ “;
if (vec-》lchild)
vec.push_back(vec-》lchild);
if (vec-》rchild)
vec.push_back(vec-》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;
}
图遍历的算法
图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。 深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：Boolean visited=TRUE; VisitFunc(w);EnQueue(Q, w);}}}}
数据结构中“遍历“是什么意思
所谓遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
扩展资料：
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次。
在数据结构中三种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。
以下是三种遍历的方法：
1、中序：若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵访问根结点；
⑶遍历右子树。
2、先序遍历：若二叉树非空，则依次执行如下操作：
⑴ 访问根结点；
⑵ 遍历左子树；
⑶ 遍历右子树。
3、后序遍历：若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵遍历右子树；
⑶访问根结点。
以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表、中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。
参考资料：百度百科-遍历
怎么用c语言实现二叉树的遍历
这是用广义表建立二叉树并先序和中序遍历二叉树#include 《stdio.h》 #include 《stdlib.h》 #define MaxSize 100 typedef struct node { char data; struct node *lchild; struct node *rchild; }BTNode,*BiTree; void creategeneralizelist(BiTree *b,char *str) { BTNode *St;/*用于保存用户输入的字符*/ printf(“please input a string end with #:\n“); scanf(“%s“,str); creategeneralize_list(&T,str); printf(“the result ofInOrder BiTree is:\n“); /* PreOrder(T);*/ InOrder(T); getch(); return 1; }
急求C语言写二叉树的遍历
下面是一个用递归方法编的二叉树遍历程序，供lz参考。#include《stdio.h》//头文件#include《stdlib.h》#include《malloc.h》typedefstructbitnode{chardata;structbitnode*lchild,*rchild;}bitnode,*bitree;//定义结点类型bitreecreatebitree()//创建树{charp;bitreet;scanf(“%c“,&p);if(p==’’)t=null;else{t=(bitnode*)malloc(sizeof(bitnode));//为结点开辟空间t-》data=p;t-》lchild=createbitree();t-》rchild=createbitree();}return(t);}voidpreorder(bitreet)//先序{if(t!=null){printf(“%c“,t-》data);preorder(t-》lchild);preorder(t-》rchild);}}voidinorder(bitreet)//中序{if(t!=null){inorder(t-》lchild);printf(“%c“,t-》data);inorder(t-》rchild);}}voidpostorder(bitreet)//后序{if(t!=null){postorder(t-》lchild);postorder(t-》rchild);printf(“%c“,t-》data);}}voidmain()//主函数{bitreeta;ta=createbitree();printf(“先序遍历:“);printf(“\n“);preorder(ta);printf(“\n“);printf(“中序遍历:“);printf(“\n“);inorder(ta);printf(“\n“);printf(“后序遍历:“);printf(“\n“);postorder(ta);}
如何用C语言实现层次遍历二叉树
下面是c语言的前序遍历二叉树的算法，在这里假设的节点元素值假设的为字符型，说明：算法中用到了结构体，也用到了递归的方法，你看看怎么样，祝你好运！#include“stdio.h“typedefcharelemtype;typedefstructnode//定义链表结构{elemtypedata;//定义节点值structnote*lchild;//定义左子节点值structnote*rchild;//定义右节点值}btree;preorder(btree*root)//前序遍历{if(roof!=null)//如果不是空节点{printf(“%c\n“,root-》data);//输出当前节点preorder(root-》lchild);//递归前序遍历左子节点preorder(root-》rchild);//递归前序遍历右子节点}return;//结束}
C语言 二叉树 遍历问题
并不是你所说的那样。首先我们要知道遍历是为了让二叉树的所有结点都扫描一遍，而前中后，三个遍历方式，说的是他的显示顺序。 前序的特点：我们注意研究一下前序遍历的结果，你会发现，对于每个二叉树（只有根结点，左结点，右结点。一棵树，是一个个小的二叉树组成）在结果中，你都会发现，根结点必定在左结点前。你可以认真看看，就算，是子树中也是根结点在左结点前。（比如，左结点成了另一个子树的根结点，这个左结点对应的上一级根结点，也会显示在这个左结点之前） 中序的特点：经过前序遍历的分析 ，我们可以直接得出，中序遍历结果中，每个根结点都会放在左结点和右结点中间。当然发生如，A的左结点是B，B的右结点是C，时中序遍历结果会是BCA，虽然A未在中间，但我们要分析，对于A是根结点，左结点B在其前面，对于B是根结点，右结点C在其后面。这符合根结点在左右结点中间的特点。 后序的特点：是先遍历左右结点，才返回来遍历根结点。参照前序和中序，就能明白 最后要注意的，可能 你也发现了，左结点的遍历一定在右结点前。 下面附上遍历的递归算法/*1 、前序遍历二叉树的递归算法 */ void preorder(bintree t) { if (t) { printf(“%c“,t-》data); preorder(t-》lchild); preorder(t-》rchild); } } /*2 、中序遍历二叉树的递归算法 */ void inorder(bintree t) { if (t) { inorder(t-》lchild); printf(“%c“,t-》data); inorder(t-》rchild); } } /*3 、后序遍历二叉树的递归算法 */ void postorder(bintree t) { if (t) { postorder(t-》lchild); postorder(t-》rchild); printf(“%c“,t-》data); } } 说那么多，我自己也复习下，哈哈
