题目描述
给定一棵树，对这棵树进行先序遍历、后序遍历、层次遍历、叶子结点遍历，分别输出对应序列，每个数字也空格隔开。
树的节点编号为1 -n，边数为n-1。
输入
第一行：n（结点数<=100）。 以下n-1行；每行两个结点x和y，表示y是x的“还子”(x,y<=100)。每个结点总是按从左到右的相对次序给出“还子”的信息。
输出
第一行：先序遍历序列 第二行：后序遍历序列 第三行：层次遍历序列 第四行：叶子结点遍历序列
样例
输入 复制
8
4 1
4 2
1 3
1 5
2 6
2 7
2 8
输出 复制
4 1 3 5 2 6 7 8
3 5 1 6 7 8 2 4
4 1 2 3 5 6 7 8
3 5 6 7 8
请问有哪个C++编程的神仙能帮我做一下！谢谢！
使用了队列和栈两种数据结构来完成不同的遍历方式：
from collections import deque
# 定义节点类
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 先序遍历
def preorder(root):
if root is None:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return res
# 后序遍历
def postorder(root):
if root is None:
return []
stack1, stack2, res = [root], [], []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left is not None:
stack1.append(node.left)
if node.right is not None:
stack1.append(node.right)
while stack2:
node = stack2.pop()
res.append(node.val)
return res
# 层次遍历
def levelorder(root):
if root is None:
return []
queue, res = deque([root]), []
while queue:
node = queue.popleft()
res.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return res
# 叶子节点遍历
def leaforder(root):
if root is None:
return []
stack, res = [root], []
while stack:
node = stack.pop()
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
if node.left is None and node.right is None:
res.append(node.val)
return res
# 主函数
if __name__ == '__main__':
n = int(input())
nodes = [Node(i) for i in range(n)]
for _ in range(n - 1):
x, y = map(int, input().split())
if nodes[x - 1].left is None:
nodes[x - 1].left = nodes[y - 1]
else:
nodes[x - 1].right = nodes[y - 1]
print(' '.join(map(str, preorder(nodes[0]))))
print(' '.join(map(str, postorder(nodes[0]))))
print(' '.join(map(str, levelorder(nodes[0]))))
print(' '.join(map(str, leaforder(nodes[0]))))
首先读入节点数n和边的关系，然后创建了一个长度为n的节点数组。接着，对于每一条边(x,y)，如果x节点还没有左儿子，则把y节点作为x的左儿子，否则作为右儿子。最后调用4个不同的遍历函数，分别输出先序、后序、层次、叶子节点遍历序列
为了实现树的先序、后序、层次和叶子结点遍历算法，可以通过递归或者迭代的方式来遍历树的节点。以下是一些具体的解决方案和代码示例：
下面是具体的代码实现：
// 先序遍历函数
void preorder(Node* root) {
if (root == nullptr) {
return;
}
// 输出当前节点的值
cout << root->value << " ";
// 遍历左子树
preorder(root->left);
// 遍历右子树
preorder(root->right);
}
// 后序遍历函数
void postorder(Node* root) {
if (root == nullptr) {
return;
}
// 遍历左子树
postorder(root->left);
// 遍历右子树
postorder(root->right);
// 输出当前节点的值
cout << root->value << " ";
}
// 层次遍历函数
void levelorder(Node* root) {
if (root == nullptr) {
return;
}
queue<Node*> q;
// 将根节点加入队列
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
// 输出当前节点的值
cout << current->value << " ";
// 将左右子节点加入队列
if (current->left != nullptr) {
q.push(current->left);
}
if (current->right != nullptr) {
q.push(current->right);
}
}
}
// 叶子节点遍历函数
void leafNodes(Node* root) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
// 当前节点为叶子结点，输出其值
cout << root->value << " ";
}
// 遍历左子树
leafNodes(root->left);
// 遍历右子树
leafNodes(root->right);
}
这样，你就可以使用这些函数来进行树的先序、后序、层次和叶子结点遍历了。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100;
vector<int> adj[MAXN+1]; // 邻接表存储树
void preorder(int u, vector<bool>& visited, vector<int>& ans){
visited[u] = true;
ans.push_back(u);
for(int v: adj[u]){
if(!visited[v]){
preorder(v, visited, ans);
}
}
}
void postorder(int u, vector<bool>& visited, vector<int>& ans){
visited[u] = true;
for(int v: adj[u]){
if(!visited[v]){
postorder(v, visited, ans);
}
}
ans.push_back(u);
}
void levelorder(int root, vector<int>& ans){
queue<int> q;
q.push(root);
while(!q.empty()){
int u = q.front();
q.pop();
ans.push_back(u);
for(int v: adj[u]){
q.push(v);
}
}
}
void leaforder(int u, vector<bool>& visited, vector<int>& ans){
visited[u] = true;
bool isLeaf = true;
for(int v: adj[u]){
if(!visited[v]){
isLeaf = false;
leaforder(v, visited, ans);
}
}
if(isLeaf){
ans.push_back(u);
}
}
int main() {
int n;
cin >> n;
for(int i = 0; i < n-1; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
vector<int> preorderAns, postorderAns, levelorderAns, leaforderAns;
vector<bool> visited(n+1);
preorder(1, visited, preorderAns);
fill(visited.begin(), visited.end(), false);
postorder(1, visited, postorderAns);
fill(visited.begin(), visited.end(), false);
levelorder(1, levelorderAns);
fill(visited.begin(), visited.end(), false);
leaforder(1, visited, leaforderAns);
for(int x: preorderAns) cout << x << " ";
cout << endl;
for(int x: postorderAns) cout << x << " ";
cout << endl;
for(int x: levelorderAns) cout << x << " ";
cout << endl;
for(int x: leaforderAns) cout << x << " ";
cout << endl;
return 0;
}