C语言的遍历算法？二叉树遍历算法，就是给定两种遍历结果求另一种遍历顺序

本文目录

• C语言的遍历算法
• 二叉树遍历算法，就是给定两种遍历结果求另一种遍历顺序
• 数据结构中“遍历“是什么意思
• C语言二叉树遍历代码
• 二叉树的层次遍历算法

C语言的遍历算法

思路1：
写出所有24种4个数的排列，存到一个数组里，假如数组是P；
那么可以
for
(i
=
0;
i
《
24;
i++)
for
(j
=
0;
j
《
24;
j++)
for
(k
=
0;
k
《
24;
k++)
三层循环，P[i],P[j],P[k]分别是矩阵的三个列
思路2：
利用dfs递归枚举
int
used;/*这个数组存放三个列中0～3这四个数是否已在这一列中出现过，需要提前清零*/
int
mat;/*要枚举的矩阵*/
void
dfs(int
col,
int
row)/*col表示现在已经搜索到哪一列(从0开始编号)，row表示这一列已经填了几行*/
{
int
i;
if
(col
==
2
&&
row
==
4)
{
....../*运行到这里的时候，mat就是枚举到的一个矩阵*/
return;
}
if
(row
==
4)
{row
=
0;
col++;}
for
(i
=
0;
i
《
4;
i++)
if
(!used[col][i])
{
used[col][i]
=
1;
mat[col][row]
=
i;
dfs(col,
row
+
1);
used[col][i]
=
0;
}
return;
}
调用的时候调用dfs(0,0)

二叉树遍历算法，就是给定两种遍历结果求另一种遍历顺序

首先从前序的第一个确定二叉树的根A，回到中序切割，将二叉树分为三部分：

左子树的中序DBGE，根A，右子树的中序CHF

再由左子树的前序可知左子树的根为B，于是左子树的中序被再次切分为三部分：

左子树的左子树中序D，左子树的根B，左子树的右子树的中序GE

类似地，由右子树的前序可知右子树的根为C，于是右子树的中序也被切分为三部分：

右子树的左子树为空，右子树的根C，右子树的左子树的中序HF

继续切分下去：GE的根为E、HF的根为F，直到每棵子树只有一个结点为止，最终得到的完整二叉树如下：

于是后序遍历序列为：DGEBHFCA

数据结构中“遍历“是什么意思

所谓遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

扩展资料：

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次。

在数据结构中三种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。

以下是三种遍历的方法：

1、中序：若二叉树非空，则依次执行如下操作：

⑴遍历左子树；

⑵访问根结点；

⑶遍历右子树。

2、先序遍历：若二叉树非空，则依次执行如下操作：

⑴ 访问根结点；

⑵ 遍历左子树；

⑶ 遍历右子树。

3、后序遍历：若二叉树非空，则依次执行如下操作：

⑴遍历左子树；

⑵遍历右子树；

⑶访问根结点。

以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表、中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。

参考资料：百度百科-遍历

C语言二叉树遍历代码

1.t = malloc(sizeof(tree));
2.t-》rchild =createTree();
3.void qianxu(tree *t)
4.zhongxu(t-》lchild );//再读左子树
printf(“%c“,t-》data);//先读根结点
zhongxu(t-》rchild );//再读右子树
5.houxu(t-》lchild );//再读左子树
houxu(t-》rchild );//再读右子树
printf(“%c“,t-》data);//先读根结点
6.return 0;
7.n=count(t-》lchild)+count(t-》rchild)+1;
8.t1-》data=t-》data;
9.return t1;
10.return m+1;

PS:注意有些语句结尾是没有分号的

二叉树的层次遍历算法

二叉树的层次遍历算法有如下三种方法：

给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：

对此二叉树遍历的结果应该是：

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;  

}