基于非链式(数组)结点结构的二叉树的层序输入创建以及遍历

点击链接返回标题->基于非链式(数组)结点结构的二叉树的层序、先序、中序、后序输入创建以及层序、先序、中序、后序输出-CSDN博客

---

层序可谓是最简单的二叉树遍历了。。。。

代码很浅显易懂，相信你能明白的！

#include<iostream>
using namespace std;
typedef int datatype;
const int MAX = 8;
struct binTree {datatype tree[2 * MAX + 7];//该数组的最大容量必须超过最大结点数的两倍，用以存放空结点！int size;//当前有效结点个数
};void create_tree_seq(binTree* tree) {//按层序创建二叉树int x, i = 1;while (cin >> x) {//处理到无输入为止（返回-1，按Ctrl + z）//层序输入结点，并主观规定->输入-1代表该结点为空tree->tree[i++] = x;if (x != -1) tree->size++;}
}void travse_seq(binTree* tree) {//二叉树的层序遍历int len = tree->size, i = 1;while (len) {if (tree->tree[i] != -1) {//访问到的不是空结点就输出，并让len自减，len为0时所有有效结点均被输出printf("%d	", tree->tree[i++]);len--;}}
}

完整测试代码如下：

样例输入：

1 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1

样例输出：

层序遍历结果——1       2       3       4       5       6       7
先序遍历结果——1       2       4       5       3       6       7
中序遍历结果——4       2       5       1       6       3       7
后序遍历结果——4       5       2       6       7       3       1

#include<iostream>
using namespace std;
typedef int datatype;
const int MAX = 8;
struct binTree {datatype tree[2 * MAX + 7];//该数组的最大容量必须超过最大结点数的两倍，用以存放空结点！int size;//当前有效结点个数
};void create_tree_seq(binTree* tree) {//按层序创建二叉树int x, i = 1;while (cin >> x) {//处理到无输入为止（返回-1，按Ctrl + z）//层序输入结点，并主观规定->输入-1代表该结点为空tree->tree[i++] = x;if (x != -1) tree->size++;}
}void travse_seq(binTree* tree) {//二叉树的层序遍历int len = tree->size, i = 1;while (len) {if (tree->tree[i] != -1) {//访问到的不是空结点就输出，并让len自减，len为0时所有有效结点均被输出printf("%d	", tree->tree[i++]);len--;}}
}
void travse_pre(binTree* tree, int i = 1) {//二叉树的先序遍历if (tree->tree[i] == -1) return;//访问到空结点，该递归路线需要返回//根，左，右printf("%d	", tree->tree[i]);travse_pre(tree, i * 2);travse_pre(tree, i * 2 + 1);
}
void travse_mid(binTree* tree, int i = 1) {//二叉树的中序遍历if (tree->tree[i] == -1) return;//左，根，右travse_mid(tree, i * 2);printf("%d	", tree->tree[i]);travse_mid(tree, i * 2 + 1);
}
void travse_nex(binTree* tree, int i = 1) {//二叉树的后序遍历if (tree->tree[i] == -1) return;//左，右，根travse_nex(tree, i * 2);travse_nex(tree, i * 2 + 1);printf("%d	", tree->tree[i]);
}
void test(binTree* tree) {create_tree_seq(tree);cout << "层序遍历结果——";travse_seq(tree);cout << endl;cout << "先序遍历结果——";travse_pre(tree);cout << endl;cout << "中序遍历结果——";travse_mid(tree);cout << endl;cout << "后序遍历结果——";travse_nex(tree);cout << endl;
}
int main() {binTree tree;tree.size = 0;memset(tree.tree, -1, sizeof(tree.tree));//初始化树的相关信息test(&tree);
}