树的存储与遍历—顺序存储
顺序存储使用数组来存储二叉树节点，通过数组下标表示节点间的父子关系，一般适用于完全二叉树。
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; }