树的存储与遍历—顺序存储
顺序存储使用数组来存储二叉树节点，通过数组下标表示节点间的父子关系，一般适用于完全二叉树。
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] << " ";
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;
}(2) 先序遍历
数组+stack版本
#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 preOrderRecursive(int index) {
// 若索引无效或节点为空，直接返回
if (index == EMPTY || index >= MAX_SIZE || tree[index].data == EMPTY) {
return;
}
// 访问当前节点（根）
cout << tree[index].data << " ";
// 遍历左子树
preOrderRecursive(tree[index].left);
// 遍历右子树
preOrderRecursive(tree[index].right);
}
// 非递归先序遍历（使用栈）
void preOrderIterative() {
if (treeSize == 0 || tree[0].data == EMPTY) {
cout << "空树";
return;
}
stack<int> s;
// 根节点入栈
s.push(0);
while (!s.empty()) {
int currentIndex = s.top();
s.pop();
// 访问当前节点（根）
cout << tree[currentIndex].data << " ";
// 右子节点先入栈（栈是后进先出，确保左子树先被访问）
if (tree[currentIndex].right != EMPTY && tree[currentIndex].right < MAX_SIZE) {
s.push(tree[currentIndex].right);
}
// 左子节点后入栈
if (tree[currentIndex].left != EMPTY && tree[currentIndex].left < MAX_SIZE) {
s.push(tree[currentIndex].left);
}
}
}
// 打印树结构信息
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); // 5的左子（索引1，值1）
int node3 = addRightChild(rootIndex, 3); // 5的右子（索引2，值3）
int node4 = addLeftChild(node2, 2); // 1的左子（索引3，值2）
int node5 = addRightChild(node2, 4); // 1的右子（索引4，值4）
int node6 = addRightChild(node3, 6); // 3的右子（索引6，值6）
// 打印树信息
printTreeInfo();
// 先序遍历（递归）
cout << "递归先序遍历: ";
preOrderRecursive(rootIndex);
cout << endl;
// 先序遍历（非递归）
cout << "非递归先序遍历: ";
preOrderIterative();
cout << endl;
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 递归先序遍历: 5 1 2 4 3 6 非递归先序遍历: 5 1 2 4 3 6
（3）中序遍历
#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 inOrderRecursive(int index) {
if (index == EMPTY || index >= MAX_SIZE || tree[index].data == EMPTY) {
return;
}
inOrderRecursive(tree[index].left); // 遍历左
cout << tree[index].data << " "; // 访问根
inOrderRecursive(tree[index].right); // 遍历右
}
// 非递归中序遍历
void inOrderIterative() {
if (treeSize == 0 || tree[0].data == EMPTY) {
cout << "空树";
return;
}
stack<int> s;
int currentIndex = 0; // 从根开始
while (!s.empty() || currentIndex != EMPTY) {
// 所有左子入栈
while (currentIndex != EMPTY && currentIndex < MAX_SIZE && tree[currentIndex].data != EMPTY) {
s.push(currentIndex);
currentIndex = tree[currentIndex].left;
}
// 弹出最左节点（访问根）
currentIndex = s.top();
s.pop();
cout << tree[currentIndex].data << " ";
// 处理右子树
currentIndex = tree[currentIndex].right;
}
}
// 打印树结构信息
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 node1 = addLeftChild(rootIndex, 1); // 5的左子（索引1，值1）
int node3 = addRightChild(rootIndex, 3); // 5的右子（索引2，值3）
int node2 = addLeftChild(node1, 2); // 1的左子（索引3，值2）
int node4 = addRightChild(node1, 4); // 1的右子（索引4，值4）
int node6 = addRightChild(node3, 6); // 3的右子（索引6，值6）
// 打印树结构
printTreeInfo();
// 中序遍历测试
cout << "中序遍历（递归）: ";
inOrderRecursive(rootIndex);
cout << endl;
cout << "中序遍历（非递归）: ";
inOrderIterative();
cout << endl << endl;
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 中序遍历（递归）: 2 1 4 5 3 6 中序遍历（非递归）: 2 1 4 5 3 6
（4）后续遍历
#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 postOrderRecursive(int index) {
if (index == EMPTY || index >= MAX_SIZE || tree[index].data == EMPTY) {
return;
}
postOrderRecursive(tree[index].left); // 遍历左
postOrderRecursive(tree[index].right); // 遍历右
cout << tree[index].data << " "; // 访问根
}
// 非递归后序遍历
void postOrderIterative() {
if (treeSize == 0 || tree[0].data == EMPTY) {
cout << "空树";
return;
}
stack<int> s;
int currentIndex = 0; // 从根节点开始
int lastVisitedIndex = EMPTY; // 记录上一次访问的节点索引
while (!s.empty() || currentIndex != EMPTY) {
// 1. 先将所有左子节点入栈
while (currentIndex != EMPTY && currentIndex < MAX_SIZE && tree[currentIndex].data != EMPTY) {
s.push(currentIndex);
currentIndex = tree[currentIndex].left;
}
// 2. 获取栈顶节点（不弹出）
int topIndex = s.top();
// 3. 判断右子树是否已遍历：
// - 若右子树为空，或右子树已访问（上一次访问的是右子节点），则可以访问当前节点
if (tree[topIndex].right == EMPTY || tree[topIndex].right == lastVisitedIndex) {
// 访问当前节点
cout << tree[topIndex].data << " ";
s.pop(); // 弹出节点
lastVisitedIndex = topIndex; // 更新上一次访问节点
currentIndex = EMPTY; // 当前节点处理完毕，无需继续入栈
} else {
// 右子树未遍历，先处理右子树
currentIndex = tree[topIndex].right;
}
}
}
// 打印树结构信息
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 node1 = addLeftChild(rootIndex, 1); // 5的左子（索引1，值1）
int node3 = addRightChild(rootIndex, 3); // 5的右子（索引2，值3）
int node2 = addLeftChild(node1, 2); // 1的左子（索引3，值2）
int node4 = addRightChild(node1, 4); // 1的右子（索引4，值4）
int node6 = addRightChild(node3, 6); // 3的右子（索引6，值6）
// 打印树结构
printTreeInfo();
// 后序遍历测试
cout << "后序遍历（递归）: ";
postOrderRecursive(rootIndex);
cout << endl;
cout << "后序遍历（非递归）: ";
postOrderIterative();
cout << endl;
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 后序遍历（递归）: 2 4 1 6 3 5 后序遍历（非递归）: 2 4 1 6 3 5
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
