树的存储与遍历—顺序存储
顺序存储使用数组来存储二叉树节点，通过数组下标表示节点间的父子关系，一般适用于完全二叉树。
1.存储规则
根节点存储在索引 0 位置
对于索引为 i 的节点：
左子节点索引：
2*i + 1右子节点索引：
2*i + 2父节点索引：
(i-1)/2
2.特点
内存连续，访问速度快
适合完全二叉树，否则会浪费存储空间
不需要存储指针，节省空间
插入删除操作效率较低
3.示例
1 / \ 2 3 / \ \ 4 5 6
对应的数组存储：
索引: 0 1 2 3 4 5 数值: 1 2 3 4 5 6
节点1(索引0)：左子=索引1(2)，右子=索引2(3)
节点2(索引1)：左子=索引3(4)，右子=索引4(5)
节点3(索引2)：左子=无，右子=索引5(6)
4.常见操作
获取根节点
获取某个节点的左子节点
获取某个节点的右子节点
获取某个节点的父节点
获取某个节点的索引值
获取树的高度
5.基础代码参考
方式一：根据位置（索引）插入
（1）直接使用一维数组输入即可。
#include<iostream>
using namespace std;
int m,x,tree[101];
int main(){
cin>>m;//边数
for(int i=0;i<m;i++){
cin>>x;
tree[i]=x; //按照顺序存储
}
return 0;
}上述方式缺点比较大，如果遇到非完全二叉树，中间的空值不好存储（可以使用NULL或者EMPTY表示）。
（2）对上述代码进行简单修改，我们可以使用结构体（非指针）来描述，比如下面的过程
#include <iostream>
#include <queue>
#include <stack>
#define MAX_SIZE 100
#define EMPTY -1
using namespace std;
// 二叉树节点结构体
struct TreeNode {
int data;
int left; // 左子节点在数组中的索引
int right; // 右子节点在数组中的索引
};
// 全局数组存储二叉树
struct TreeNode tree[MAX_SIZE];
int treeSize = 0;
// 初始化树
void initTree() {
for (int i = 0; i < MAX_SIZE; i++) {
tree[i].data = EMPTY;
tree[i].left = EMPTY;
tree[i].right = EMPTY;
}
treeSize = 0;
}
// 添加根节点
int addRoot(int value) {
if (treeSize >= MAX_SIZE) return EMPTY;
tree[0].data = value;
tree[0].left = EMPTY;
tree[0].right = EMPTY;
treeSize = 1;
return 0; // 返回根节点索引
}
// 添加左子节点
int addLeftChild(int parentIndex, int value) {
if (treeSize >= MAX_SIZE) return EMPTY;
int leftIndex = 2 * parentIndex + 1;
if (leftIndex >= MAX_SIZE) return EMPTY;
tree[leftIndex].data = value;
tree[leftIndex].left = EMPTY;
tree[leftIndex].right = EMPTY;
tree[parentIndex].left = leftIndex;
if (leftIndex >= treeSize) {
treeSize = leftIndex + 1;
}
return leftIndex;
}
// 添加右子节点
int addRightChild(int parentIndex, int value) {
if (treeSize >= MAX_SIZE) return EMPTY;
int rightIndex = 2 * parentIndex + 2;
if (rightIndex >= MAX_SIZE) return EMPTY;
tree[rightIndex].data = value;
tree[rightIndex].left = EMPTY;
tree[rightIndex].right = EMPTY;
tree[parentIndex].right = rightIndex;
if (rightIndex >= treeSize) {
treeSize = rightIndex + 1;
}
return rightIndex;
}
// 打印树结构信息
void printTreeInfo() {
cout << "\n树结构信息:" << endl;
cout << "树节点数量: " << treeSize << endl;
cout << "节点索引分布:" << endl;
for (int i = 0; i < treeSize; i++) {
if (tree[i].data != EMPTY) {
cout << "索引" << i << ": 数据=" << tree[i].data
<< ", 左子=" << tree[i].left
<< ", 右子=" << tree[i].right << endl;
}
}
cout << endl;
}
// 测试函数
int main() {
// 初始化树
initTree();
// 构建示例二叉树
// 5
// / \
// 1 3
// / \ \
// 2 4 6
int rootIndex = addRoot(5);
int node2 = addLeftChild(rootIndex, 1);
int node3 = addRightChild(rootIndex, 3);
int node4 = addLeftChild(node2, 2);
int node5 = addRightChild(node2, 4);
int node6 = addRightChild(node3, 6);
// 打印树信息
printTreeInfo();
return 0;
}上述程序运行结果如下：
树结构信息: 树节点数量: 7 节点索引分布: 索引0: 数据=5, 左子=1, 右子=2 索引1: 数据=1, 左子=3, 右子=4 索引2: 数据=3, 左子=-1, 右子=6 索引3: 数据=2, 左子=-1, 右子=-1 索引4: 数据=4, 左子=-1, 右子=-1 索引6: 数据=6, 左子=-1, 右子=-1
（3）如果使用vector，则可以从参考下面的代码
注意：使用vector和链表等操作 才是主流（代码量少，表示更简单）
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 定义空节点标记值（使用INT_MIN表示空位）
const int EMPTY = INT_MIN;
/**
* 向顺序存储的二叉树插入节点
* @param tree 存储数组的引用
* @param pos 要插入的位置（数组索引）
* @param val 要插入的节点值
*/
void insertNode(vector<int>& tree, int pos, int val) {
// 检查位置是否在数组范围内
if (pos < tree.size()) {
tree[pos] = val; // 在指定位置存储节点值
}
// 如果位置超出范围，静默失败（实际应用可添加错误处理）
}
/**
* 计算父节点位置
* @param pos 当前节点位置
* @return 父节点的数组索引
*/
int getParent(int pos) {
// 完全二叉树父节点计算公式：(i-1)/2
return (pos - 1) / 2;
}
/**
* 计算左子节点位置
* @param pos 当前节点位置
* @return 左子节点的数组索引
*/
int getLeftChild(int pos) {
// 完全二叉树左子计算公式：2*i+1
return 2 * pos + 1;
}
/**
* 计算右子节点位置
* @param pos 当前节点位置
* @return 右子节点的数组索引
*/
int getRightChild(int pos) {
// 完全二叉树右子计算公式：2*i+2
return 2 * pos + 2;
}
/**
* 打印顺序存储的二叉树结构
* @param tree 存储数组的常量引用
*/
void printTree(const vector<int>& tree) {
// 遍历数组所有元素
for (size_t i = 0; i < tree.size(); ++i) {
int val = tree[i];
if (val != EMPTY)
cout << val << " "; // 打印有效节点值
else
cout << "NULL "; // 打印空位标记
}
cout << endl; // 换行结束输出
}
/**
* 程序主入口
*/
int main() {
// 初始化3层完全二叉树存储空间（深度为3的树最多7个节点）
int depth = 3;
vector<int> tree(pow(2, depth) - 1, EMPTY); // 创建大小为7的数组并初始化为EMPTY
// 构建示例二叉树：
// 1
// / \
// 2 3
// / \ /
// 4 5 6
insertNode(tree, 0, 1); // 根节点（位置0）
insertNode(tree, 1, 2); // 左子节点（位置1）
insertNode(tree, 2, 3); // 右子节点（位置2）
insertNode(tree, 3, 4); // 节点2的左子（位置3）
insertNode(tree, 4, 5); // 节点2的右子（位置4）
insertNode(tree, 5, 6); // 节点3的左子（位置5）
// 位置6保持EMPTY（节点3没有右子）
// 输出存储结构
cout << "顺序存储结构: ";
printTree(tree);
// 验证父子关系计算
cout << "\n节点关系验证:" << endl;
cout << "节点2的父节点位置: " << getParent(1)
<< " (值=" << tree[getParent(1)] << ")" << endl;
cout << "节点1的左子节点位置: " << getLeftChild(0)
<< " (值=" << tree[getLeftChild(0)] << ")" << endl;
return 0;
}方式二：通过父子关系，比如输入的数据表示父子关系
假设输入x和y，表示x是y的父亲
4 1 4 2 1 3 1 5 2 6 2 7 2 8
表示成二叉树就是
// 构建的二叉树： // 4 // / \ // 1 2 // / \ / | \ // 3 5 6 7 8
（1）这种情况下，如果是一维数组，表示比较简单，找数根进行遍历即可。
#include<iostream>
using namespace std;
int n,m,x,y,root,tree[101];
int main(){
cin>>n>>m;//读入结点数和边数
for(int i=0;i<m;i++){
cin>>x>>y;
tree[y]=x; //x是y的父节点
}
for(int i=0;i<n;i++){
if(tree[i]==0){
root=i; //找到数根
break;
}
}
cout<<root;
return 0;
}后续再扩展相对麻烦，需要使用递归一层层求解（参考使用一维数组实现BFS）
(2)如果使用结构体（无指针和链表）
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#define MAX_SIZE 100
#define EMPTY -1
using namespace std;
// 二叉树节点结构体
struct TreeNode {
int data;
int left; // 左子节点在数组中的索引
int right; // 右子节点在数组中的索引
};
// 父子关系结构体
struct ParentChildRelation {
int parentValue;
int childValue;
bool isLeftChild; //是否左子树
};
// 全局数组存储二叉树
struct TreeNode tree[MAX_SIZE];
int treeSize = 0;
// 初始化树
void initTree() {
for (int i = 0; i < MAX_SIZE; i++) {
tree[i].data = EMPTY;
tree[i].left = EMPTY;
tree[i].right = EMPTY;
}
treeSize = 0;
}
// 根据值查找节点索引
int findNodeByValue(int value) {
for (int i = 0; i < treeSize; i++) {
if (tree[i].data == value) {
return i;
}
}
return EMPTY;
}
// 创建新节点
int createNode(int value) {
if (treeSize >= MAX_SIZE) return EMPTY;
int index = treeSize;
tree[index].data = value;
tree[index].left = EMPTY;
tree[index].right = EMPTY;
treeSize++;
return index;
}
// 根据值查找节点索引，如果不存在则创建新节点
int findOrCreateNode(int value) {
int index = findNodeByValue(value);
if (index != EMPTY) {
return index;
}
return createNode(value);
}
// 添加父子关系
bool addParentChild(int parentValue, int childValue, bool isLeftChild) {
int parentIndex = findOrCreateNode(parentValue);
int childIndex = findOrCreateNode(childValue);
if (parentIndex == EMPTY || childIndex == EMPTY) {
return false;
}
if (isLeftChild) {
// 检查左子节点是否已被占用
if (tree[parentIndex].left != EMPTY) {
cout << "错误: 节点 " << parentValue << " 的左子节点已被占用!" << endl;
return false;
}
tree[parentIndex].left = childIndex;
} else {
// 检查右子节点是否已被占用
if (tree[parentIndex].right != EMPTY) {
cout << "错误: 节点 " << parentValue << " 的右子节点已被占用!" << endl;
return false;
}
tree[parentIndex].right = childIndex;
}
return true;
}
// 从父子关系构建树
void buildTreeFromRelations(ParentChildRelation relations[], int relationCount) {
initTree();
for (int i = 0; i < relationCount; i++) {
int parentValue = relations[i].parentValue;
int childValue = relations[i].childValue;
bool isLeftChild = relations[i].isLeftChild;
if (!addParentChild(parentValue, childValue, isLeftChild)) {
cout << "添加关系失败: " << parentValue << " -> " << childValue
<< (isLeftChild ? " (左子)" : " (右子)") << endl;
}
}
}
// 查找根节点（没有父节点的节点）
int findRoot() {
// 标记所有有父节点的节点
bool hasParent[MAX_SIZE] = {false};
for (int i = 0; i < treeSize; i++) {
if (tree[i].left != EMPTY) {
hasParent[tree[i].left] = true;
}
if (tree[i].right != EMPTY) {
hasParent[tree[i].right] = true;
}
}
// 找到没有父节点的节点（根节点）
for (int i = 0; i < treeSize; i++) {
if (!hasParent[i] && tree[i].data != EMPTY) {
return i;
}
}
return EMPTY;
}
// 层次遍历
void levelOrderTraversal() {
int rootIndex = findRoot();
if (rootIndex == EMPTY) {
cout << "树为空!" << endl;
return;
}
cout << "层次遍历: ";
queue<int> q;
q.push(rootIndex);
while (!q.empty()) {
int current = q.front();
q.pop();
cout << tree[current].data << " ";
if (tree[current].left != EMPTY) {
q.push(tree[current].left);
}
if (tree[current].right != EMPTY) {
q.push(tree[current].right);
}
}
cout << endl;
}
// 打印树结构信息
void printTreeInfo() {
cout << "\n树结构信息:" << endl;
cout << "树节点数量: " << treeSize << endl;
int rootIndex = findRoot();
if (rootIndex != EMPTY) {
cout << "根节点: " << tree[rootIndex].data << " (索引" << rootIndex << ")" << endl;
}
cout << "节点详细信息:" << endl;
for (int i = 0; i < treeSize; i++) {
if (tree[i].data != EMPTY) {
cout << "索引" << i << ": 数据=" << tree[i].data
<< ", 左子=";
if (tree[i].left != EMPTY) {
cout << tree[tree[i].left].data;
} else {
cout << "空";
}
cout << ", 右子=";
if (tree[i].right != EMPTY) {
cout << tree[tree[i].right].data;
} else {
cout << "空";
}
cout << endl;
}
}
cout << endl;
}
// 测试函数
int main() {
// 构建示例二叉树
// 5
// / \
// 1 3
// / \ \
// 2 4 6
ParentChildRelation relations[] = {
{5, 1, true}, // 5是1的父节点，1是左子节点
{5, 3, false}, // 5是3的父节点，3是右子节点
{1, 2, true}, // 1是2的父节点，2是左子节点
{1, 4, false}, // 1是4的父节点，4是右子节点
{3, 6, false} // 3是6的父节点，6是右子节点
};
int relationCount = 5;
// 从父子关系构建树
buildTreeFromRelations(relations, relationCount);
// 打印树信息
printTreeInfo();
return 0;
}上述代码运行结果如下：
树结构信息: 树节点数量: 7 节点索引分布: 索引0: 数据=5, 左子=1, 右子=2 索引1: 数据=1, 左子=3, 右子=4 索引2: 数据=3, 左子=-1, 右子=6 索引3: 数据=2, 左子=-1, 右子=-1 索引4: 数据=4, 左子=-1, 右子=-1 索引6: 数据=6, 左子=-1, 右子=-1
(3)如果使用vector数组，相对复杂一些，需要检查节点
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int EMPTY = INT_MIN;
const int MAX_NODES = 100;
struct NodeInfo {
int value; //值
int index; //索引
};
vector<NodeInfo> nodeInfoArray;
int getParent(int pos) { return (pos - 1) / 2; }
int getLeftChild(int pos) { return 2 * pos + 1; }
int getRightChild(int pos) { return 2 * pos + 2; }
int findNodeIndex(int value) {
for (size_t i = 0; i < nodeInfoArray.size(); ++i) {
if (nodeInfoArray[i].value == value) {
// 验证该节点在树中确实存在且值匹配
return nodeInfoArray[i].index;
}
}
return -1;
}
//保证数组容量够
void ensureCapacity(vector<int>& tree, int requiredSize) {
while (tree.size() <= requiredSize) {
tree.push_back(EMPTY);
}
}
void insertByRelation(vector<int>& tree, int parentVal, int childVal) {
// 如果是空树，先创建根节点
if (tree.empty()) {
tree.push_back(parentVal);
nodeInfoArray.push_back({parentVal, 0});
// 现在插入子节点
int parentPos = 0;
int childPos = getLeftChild(parentPos);
ensureCapacity(tree, childPos);
tree[childPos] = childVal;
nodeInfoArray.push_back({childVal, childPos});
return;
}
int parentPos = findNodeIndex(parentVal);
if (parentPos == -1) {
cout << "错误: 父节点 " << parentVal << " 不存在!" << endl;
return;
}
// 检查子节点是否已存在
if (findNodeIndex(childVal) != -1) {
cout << "错误: 子节点 " << childVal << " 已经存在!" << endl;
return;
}
int childPos = -1;
int leftPos = getLeftChild(parentPos);
int rightPos = getRightChild(parentPos);
// 优先选择左子节点位置
if (leftPos >= tree.size() || tree[leftPos] == EMPTY) {
childPos = leftPos;
} else if (rightPos >= tree.size() || tree[rightPos] == EMPTY) {
childPos = rightPos;
} else {
cout << "错误: 父节点 " << parentVal << " 子节点位置已满!" << endl;
return;
}
ensureCapacity(tree, childPos);
tree[childPos] = childVal;
nodeInfoArray.push_back({childVal, childPos});
}
void printTree(const vector<int>& tree) {
cout << "树的数组: [";
for (size_t i = 0; i < tree.size(); ++i) {
if (tree[i] != EMPTY)
cout << tree[i];
else
cout << "NULL";
if (i < tree.size() - 1) cout << ", ";
}
cout << "]" << endl;
// 可视化树结构
cout << "树结构如下:" << endl;
for (size_t i = 0; i < tree.size(); ++i) {
if (tree[i] != EMPTY) {
cout << "节点 " << tree[i] << ": ";
int left = getLeftChild(i);
int right = getRightChild(i);
if (left < tree.size() && tree[left] != EMPTY)
cout << "左=" << tree[left] << " ";
else
cout << "左=NULL ";
if (right < tree.size() && tree[right] != EMPTY)
cout << "右=" << tree[right];
else
cout << "右=NULL";
cout << endl;
}
}
}
int main() {
vector<int> tree;
cout << "插入 (1,2):" << endl;
insertByRelation(tree, 1, 2);
printTree(tree);
cout << endl;
cout << "插入 (1,3):" << endl;
insertByRelation(tree, 1, 3);
printTree(tree);
cout << endl;
cout << "插入 (2,4):" << endl;
insertByRelation(tree, 2, 4);
printTree(tree);
cout << endl;
cout << "插入 (2,5):" << endl;
insertByRelation(tree, 2, 5);
printTree(tree);
cout << endl;
cout << "插入 (3,6):" << endl;
insertByRelation(tree, 3, 6);
printTree(tree);
return 0;
}上述代码中二叉树可以表示为：
// 1 // / \ // 2 3 // / \ / // 4 5 6
上述程序执行结果如下：
插入 (1,2): 树的数组: [1, 2] 树结构如下: 节点 1: 左=2 右=NULL 节点 2: 左=NULL 右=NULL 插入 (1,3): 树的数组: [1, 2, 3] 树结构如下: 节点 1: 左=2 右=3 节点 2: 左=NULL 右=NULL 节点 3: 左=NULL 右=NULL 插入 (2,4): 树的数组: [1, 2, 3, 4] 树结构如下: 节点 1: 左=2 右=3 节点 2: 左=4 右=NULL 节点 3: 左=NULL 右=NULL 节点 4: 左=NULL 右=NULL 插入 (2,5): 树的数组: [1, 2, 3, 4, 5] 树结构如下: 节点 1: 左=2 右=3 节点 2: 左=4 右=5 节点 3: 左=NULL 右=NULL 节点 4: 左=NULL 右=NULL 节点 5: 左=NULL 右=NULL 插入 (3,6): 树的数组: [1, 2, 3, 4, 5, 6] 树结构如下: 节点 1: 左=2 右=3 节点 2: 左=4 右=5 节点 3: 左=6 右=NULL 节点 4: 左=NULL 右=NULL 节点 5: 左=NULL 右=NULL 节点 6: 左=NULL 右=NULL
6.二叉树的遍历
不论二叉树如何存储，也需要进行遍历，二叉树分为层次遍历、前序遍历、中序遍历、后续遍历。
（1）层次遍历
层次遍历就是一层一层的遍历。比如一棵二叉树长下面这样：
// 4 // / \ // 1 3 // / \ \ // 2 6 5
那么它的层次遍历就是4 1 3 2 6 5
如果我们使用上述结构体（没有指针和链表）方式进行层次遍历，参考如下：
#include <iostream>
#include <queue>
#include <stack>
#define MAX_SIZE 100
#define EMPTY -1
using namespace std;
// 二叉树节点结构体
struct TreeNode {
int data;
int left; // 左子节点在数组中的索引
int right; // 右子节点在数组中的索引
};
// 全局数组存储二叉树
struct TreeNode tree[MAX_SIZE];
int treeSize = 0;
// 初始化树
void initTree() {
for (int i = 0; i < MAX_SIZE; i++) {
tree[i].data = EMPTY;
tree[i].left = EMPTY;
tree[i].right = EMPTY;
}
treeSize = 0;
}
// 添加根节点
int addRoot(int value) {
if (treeSize >= MAX_SIZE) return EMPTY;
tree[0].data = value;
tree[0].left = EMPTY;
tree[0].right = EMPTY;
treeSize = 1;
return 0; // 返回根节点索引
}
// 添加左子节点
int addLeftChild(int parentIndex, int value) {
if (treeSize >= MAX_SIZE) return EMPTY;
int leftIndex = 2 * parentIndex + 1;
if (leftIndex >= MAX_SIZE) return EMPTY;
tree[leftIndex].data = value;
tree[leftIndex].left = EMPTY;
tree[leftIndex].right = EMPTY;
tree[parentIndex].left = leftIndex;
if (leftIndex >= treeSize) {
treeSize = leftIndex + 1;
}
return leftIndex;
}
// 添加右子节点
int addRightChild(int parentIndex, int value) {
if (treeSize >= MAX_SIZE) return EMPTY;
int rightIndex = 2 * parentIndex + 2;
if (rightIndex >= MAX_SIZE) return EMPTY;
tree[rightIndex].data = value;
tree[rightIndex].left = EMPTY;
tree[rightIndex].right = EMPTY;
tree[parentIndex].right = rightIndex;
if (rightIndex >= treeSize) {
treeSize = rightIndex + 1;
}
return rightIndex;
}
// 层次遍历（使用queue）
void levelOrderTraversal() {
cout << "层次遍历: ";
if (treeSize == 0 || tree[0].data == EMPTY) {
cout << "空树" << endl;
return;
}
// 使用queue作为队列
queue<int> q;
// 根节点入队
q.push(0);
while (!q.empty()) {
int currentIndex = q.front();
q.pop();
// 访问当前节点
if (tree[currentIndex].data != EMPTY) {
cout << tree[currentIndex].data << " ";
}
// 左子节点入队
if (tree[currentIndex].left != EMPTY) {
q.push(tree[currentIndex].left);
}
// 右子节点入队
if (tree[currentIndex].right != EMPTY) {
q.push(tree[currentIndex].right);
}
}
cout << endl;
}
// 打印树结构信息
void printTreeInfo() {
cout << "\n树结构信息:" << endl;
cout << "树节点数量: " << treeSize << endl;
cout << "节点索引分布:" << endl;
for (int i = 0; i < treeSize; i++) {
if (tree[i].data != EMPTY) {
cout << "索引" << i << ": 数据=" << tree[i].data
<< ", 左子=" << tree[i].left
<< ", 右子=" << tree[i].right << endl;
}
}
cout << endl;
}
int main() {
// 初始化树
initTree();
// 构建示例二叉树
// 5
// / \
// 1 3
// / \ \
// 2 4 6
int rootIndex = addRoot(5);
int node2 = addLeftChild(rootIndex, 1);
int node3 = addRightChild(rootIndex, 3);
int node4 = addLeftChild(node2, 2);
int node5 = addRightChild(node2, 4);
int node6 = addRightChild(node3, 6);
// 打印树信息
printTreeInfo();
// 层次遍历
levelOrderTraversal();
return 0;
}上述代码执行结果如下：
树结构信息: 树节点数量: 7 节点索引分布: 索引0: 数据=5, 左子=1, 右子=2 索引1: 数据=1, 左子=3, 右子=4 索引2: 数据=3, 左子=-1, 右子=6 索引3: 数据=2, 左子=-1, 右子=-1 索引4: 数据=4, 左子=-1, 右子=-1 索引6: 数据=6, 左子=-1, 右子=-1 层次遍历: 5 1 3 2 4 6
如果使用 vector，那么层次遍历方式如下：
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int EMPTY = INT_MIN;
void insertNode(vector<int>& tree, int pos, int val) {
if (pos < tree.size()) {
tree[pos] = val;
}
}
int getParent(int pos) {
return (pos - 1) / 2;
}
int getLeftChild(int pos) {
return 2 * pos + 1;
}
int getRightChild(int pos) {
return 2 * pos + 2;
}
void printTree(const vector<int>& tree) {
for (size_t i = 0; i < tree.size(); ++i) {
int val = tree[i];
if (val != EMPTY)
cout << val << " ";
else
cout << "NULL ";
}
cout << endl;
}
/**
* 修正后的层次遍历
*/
void levelOrderTraversal(const vector<int>& tree) {
if (tree.empty()) return;
cout << "层次遍历结果: ";
queue<int> q;
q.push(0); // 从根节点开始
while (!q.empty()) {
int current = q.front();
q.pop();
// 输出当前节点值
if (tree[current] != EMPTY) {
cout << tree[current] << " ";
// 修正：使用 current 而不是 right
int left = getLeftChild(current);
int right = getRightChild(current); // 这里修正了
// 将有效的左右子节点加入队列
if (left < tree.size() && tree[left] != EMPTY) {
q.push(left);
}
if (right < tree.size() && tree[right] != EMPTY) {
q.push(right);
}
}
}
cout << endl;
}
/**
* 按层级分行显示的层次遍历
*/
void levelOrderWithLevels(const vector<int>& tree) {
if (tree.empty()) return;
cout << "分层显示层次遍历:" << endl;
queue<int> q;
q.push(0);
int level = 0;
while (!q.empty()) {
int levelSize = q.size();
cout << "第 " << level << " 层: ";
for (int i = 0; i < levelSize; ++i) {
int current = q.front();
q.pop();
if (tree[current] != EMPTY) {
cout << tree[current] << " ";
int left = getLeftChild(current);
int right = getRightChild(current);
if (left < tree.size() && tree[left] != EMPTY) {
q.push(left);
}
if (right < tree.size() && tree[right] != EMPTY) {
q.push(right);
}
}
}
cout << endl;
level++;
}
}
/**
* 层次遍历（简化版本 - 直接遍历有效节点）
*/
void levelOrderSimple(const vector<int>& tree) {
cout << "简化层次遍历: ";
for (size_t i = 0; i < tree.size(); ++i) {
if (tree[i] != EMPTY) {
cout << tree[i] << " ";
}
}
cout << endl;
}
int main() {
// 构建示例二叉树
int depth = 3;
vector<int> tree(pow(2, depth) - 1, EMPTY);
// 构建树结构：
// 1
// / \
// 2 3
// / \ /
// 4 5 6
insertNode(tree, 0, 1); // 根节点
insertNode(tree, 1, 2); // 左子节点
insertNode(tree, 2, 3); // 右子节点
insertNode(tree, 3, 4); // 节点2的左子
insertNode(tree, 4, 5); // 节点2的右子
insertNode(tree, 5, 6); // 节点3的左子
cout << "顺序存储结构: ";
printTree(tree);
cout << "数组索引: ";
for (size_t i = 0; i < tree.size(); ++i) {
if (tree[i] != EMPTY) cout << i << " ";
else cout << "X ";
}
cout << endl << endl;
// 进行层次遍历
levelOrderTraversal(tree);
cout << endl;
levelOrderWithLevels(tree);
levelOrderSimple(tree);
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
