编写程序,对二叉树进行先序遍历,并打印层号。
时间: 2024-01-23 17:15:16 浏览: 72
好的,下面是一个C++的示例程序,实现了对二叉树进行先序遍历,并打印层号:
```c++
#include <iostream>
#include <stack>
using namespace std;
// 二叉树节点的定义
struct BinaryTreeNode {
int val;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历并打印层号
void preOrder(BinaryTreeNode* root) {
if (root == NULL) return;
stack<pair<BinaryTreeNode*, int>> stk;
stk.push(make_pair(root, 1));
while (!stk.empty()) {
BinaryTreeNode* node = stk.top().first;
int level = stk.top().second;
stk.pop();
cout << "Level " << level << ": " << node->val << endl;
if (node->right != NULL) {
stk.push(make_pair(node->right, level + 1));
}
if (node->left != NULL) {
stk.push(make_pair(node->left, level + 1));
}
}
}
// 测试程序
int main() {
// 构造一个二叉树
BinaryTreeNode* root = new BinaryTreeNode(1);
root->left = new BinaryTreeNode(2);
root->right = new BinaryTreeNode(3);
root->left->left = new BinaryTreeNode(4);
root->left->right = new BinaryTreeNode(5);
root->right->left = new BinaryTreeNode(6);
root->right->right = new BinaryTreeNode(7);
// 先序遍历并打印层号
preOrder(root);
return 0;
}
```
该程序使用了一个栈来实现先序遍历,同时记录了每个节点的层号。在遍历过程中,每次取出栈顶节点时,都会打印该节点的值和层号,并将其子节点按照先右后左的顺序入栈,同时将层号加1。这样就可以按照先序遍历的顺序遍历整个二叉树,并打印每个节点的层号。
阅读全文