1. 已知一个二叉树的中序遍历序列和后序遍历序列，求这棵树的前序遍历序列
【问题描述】
已知一个二叉树的中序遍历序列和后序遍历序列，求这棵树的前序遍历序列。
【输入形式】
一个树的中序遍历序列 该树后序遍历序列，中间用空格分开。输入序列中仅含有小写字母,且没有重复的字母
【输出形式】
一个树的前序遍历序列
【样例输入】
dbeafcg debfgca
【样例输出】
abdecfg
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
};
int search(char in[], int start, int end, char value) {
for (int i = start; i <= end; i++) {
if (in[i] == value) {
return i;
}
}
return -1;
}
struct TreeNode* buildTree(char in[], char post[], int inStart, int inEnd, int* postIndex) {
if (inStart > inEnd) {
return NULL;
}
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = post[(*postIndex)--];
node->left = NULL;
node->right = NULL;
if (inStart == inEnd) {
return node;
}
int rootIndex = search(in, inStart, inEnd, node->data);
node->right = buildTree(in, post, rootIndex + 1, inEnd, postIndex);
node->left = buildTree(in, post, inStart, rootIndex - 1, postIndex);
return node;
}
void printPreorder(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c", root->data);
printPreorder(root->left);
printPreorder(root->right);
}
int main() {
char inorder[100], postorder[100];
scanf("%s %s", inorder, postorder);
int len = strlen(inorder);
int postIndex = len - 1;
struct TreeNode* root = buildTree(inorder, postorder, 0, len - 1, &postIndex);
printPreorder(root);
printf("\n");
return 0;
}2. 非递归的中序遍历
【问题描述】
给定二叉树，返回它的中序遍历。
要求：使用栈实现，不可使用递归。
【输入形式】
一行，包含用空格分开的n个元素，每个元素为整数或者None（None表示空结点），依次表示按自顶向下层次遍历的二叉树结点。空结点对应的“孩子”（实际上不存在）不再用None表示。
【输出形式】
一行，二叉树的中序遍历，每个值间用空格隔开。
【样例输入】
1 2 3 4 5 6
【样例输出】
4 2 5 1 6 3
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct Stack {
struct TreeNode **array;
int top;
int capacity;
};
struct Stack *createStack(int capacity) {
struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (struct TreeNode **)malloc(stack->capacity * sizeof(struct TreeNode *));
return stack;
}
int isEmpty(struct Stack *stack) {
return stack->top == -1;
}
int isFull(struct Stack *stack) {
return stack->top == stack->capacity - 1;
}
void push(struct Stack *stack, struct TreeNode *item) {
if (isFull(stack)) return;
stack->array[++stack->top] = item;
}
struct TreeNode *pop(struct Stack *stack) {
if (isEmpty(stack)) return NULL;
return stack->array[stack->top--];
}
void inorderTraversal(struct TreeNode *root) {
if (root == NULL) return;
struct Stack *stack = createStack(100);
struct TreeNode *current = root;
while (current != NULL || !isEmpty(stack)) {
while (current != NULL) {
push(stack, current);
current = current->left;
}
current = pop(stack);
printf("%d ", current->val);
current = current->right;
}
free(stack->array);
free(stack);
}
struct TreeNode *createTree(char input[][10], int n) {
if (n == 0) return NULL;
struct TreeNode **nodes = (struct TreeNode **)malloc(n * sizeof(struct TreeNode *));
for (int i = 0; i < n; i++) {
if (strcmp(input[i], "None") == 0) {
nodes[i] = NULL;
} else {
nodes[i] = (struct TreeNode *)malloc(sizeof(struct TreeNode));
nodes[i]->val = atoi(input[i]);
nodes[i]->left = nodes[i]->right = NULL;
}
}
for (int i = 0; i < n; i++) {
if (nodes[i] != NULL) {
int leftIndex = 2 * i + 1;
int rightIndex = 2 * i + 2;
if (leftIndex < n) nodes[i]->left = nodes[leftIndex];
if (rightIndex < n) nodes[i]->right = nodes[rightIndex];
}
}
struct TreeNode *root = nodes[0];
free(nodes);
return root;
}
void freeTree(struct TreeNode *root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
char input[100][10];
int n = 0;
while (scanf("%s", input[n]) != EOF) {
n++;
}
struct TreeNode *root = createTree(input, n);
inorderTraversal(root);
freeTree(root);
return 0;
}3. 判断完全二叉树
【问题描述】
给定一棵树的前序遍历和中序遍历，判断该树是否为完全二叉树
【输入形式】
一棵树的前序遍历和中序遍历
【输出形式】
True or False
【样例输入】
2 4 8 10 6 11 8 4 10 2 11 6
【样例输出】
True
【样例说明】
【评分标准】
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* newNode(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
Node* buildTree(int pre[], int in[], int inStrt, int inEnd) {
static int preIndex = 0;
if (inStrt > inEnd) return NULL;
Node* tNode = newNode(pre[preIndex++]);
if (inStrt == inEnd) return tNode;
int inIndex;
for (inIndex = inStrt; inIndex <= inEnd; inIndex++) {
if (in[inIndex] == tNode->data) break;
}
tNode->left = buildTree(pre, in, inStrt, inIndex - 1);
tNode->right = buildTree(pre, in, inIndex + 1, inEnd);
return tNode;
}
bool isCompleteBT(Node* root) {
if (root == NULL) return true;
bool end = false;
Node* temp;
Node* queue[1000]; // Changed to a regular array instead of dynamic allocation
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
temp = queue[front++];
if (temp->left) {
if (end) return false;
queue[rear++] = temp->left;
} else {
end = true;
}
if (temp->right) {
if (end) return false;
queue[rear++] = temp->right;
} else {
end = true;
}
}
return true;
}
int main() {
int preorder[100], inorder[100];
int n = 0;
char temp;
while (scanf("%d", &preorder[n])) {
temp = getchar();
n++;
if (temp == '\n') {
break;
}
}
for (int i = 0; i < n; i++) {
scanf("%d", &inorder[i]);
}
Node* root = buildTree(preorder, inorder, 0, n - 1);
if (isCompleteBT(root))
printf("True\n");
else
printf("False\n");
return 0;
}4. 二叉树遍历
【问题描述】
给定一棵N个节点的二叉树，输出其前序遍历，中序遍历，后序遍历，层次遍历。
【输入形式】
输入共N+1行。
第1行为一个整数N，描述节点个数。
其余N行按顺序描述第1，2，……，N个结点的左右子节点编号，0表示没有相应子节点。
【输出形式】
输出共4行，分别为前序遍历，中序遍历，后序遍历，层次遍历。
【样例输入】
10
8 0
4 1
0 0
6 9
0 0
3 7
0 0
0 0
5 10
0 0
【样例输出】
2 4 6 3 7 9 5 10 1 8
3 6 7 4 5 9 10 2 8 1
3 7 6 5 10 9 4 8 1 2
2 4 1 6 9 8 3 7 5 10
【数据范围】
保证输入的是合法的二叉树。
1<= N <= 10000.
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* build_tree(const std::vector<std::pair<int, int>>& nodes) {
std::vector<TreeNode*> tree_nodes(nodes.size() + 1);
std::vector<bool> is_root(nodes.size() + 1, true);
for (int i = 1; i <= nodes.size(); ++i) {
tree_nodes[i] = new TreeNode(i);
}
for (int i = 1; i <= nodes.size(); ++i) {
tree_nodes[i]->left = nodes[i - 1].first ? tree_nodes[nodes[i - 1].first] : nullptr;
tree_nodes[i]->right = nodes[i - 1].second ? tree_nodes[nodes[i - 1].second] : nullptr;
if (nodes[i - 1].first) is_root[nodes[i - 1].first] = false;
if (nodes[i - 1].second) is_root[nodes[i - 1].second] = false;
}
for (int i = 1; i <= nodes.size(); ++i) {
if (is_root[i]) return tree_nodes[i];
}
return nullptr;
}
void preorder_traversal(TreeNode* root, std::vector<int>& result) {
if (!root) return;
result.push_back(root->val);
preorder_traversal(root->left, result);
preorder_traversal(root->right, result);
}
void inorder_traversal(TreeNode* root, std::vector<int>& result) {
if (!root) return;
inorder_traversal(root->left, result);
result.push_back(root->val);
inorder_traversal(root->right, result);
}
void postorder_traversal(TreeNode* root, std::vector<int>& result) {
if (!root) return;
postorder_traversal(root->left, result);
postorder_traversal(root->right, result);
result.push_back(root->val);
}
std::vector<int> level_order_traversal(TreeNode* root) {
std::vector<int> result;
std::queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
result.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return result;
}
int main() {
int N;
std::cin >> N;
std::vector<std::pair<int, int>> nodes(N);
for (int i = 0; i < N; ++i) {
std::cin >> nodes[i].first >> nodes[i].second;
}
TreeNode* root = build_tree(nodes);
std::vector<int> preorder, inorder, postorder, level_order;
preorder_traversal(root, preorder);
inorder_traversal(root, inorder);
postorder_traversal(root, postorder);
level_order = level_order_traversal(root);
for (int val : preorder) std::cout << val << ' ';
std::cout << '\n';
for (int val : inorder) std::cout << val << ' ';
std::cout << '\n';
for (int val : postorder) std::cout << val << ' ';
std::cout << '\n';
for (int val : level_order) std::cout << val << ' ';
std::cout << '\n';
return 0;
}
