给定一颗二叉树,分别实现按层和 ZigZag 打印二叉树。
ZigZag遍历: 意思是第一层从左到右遍历,第二层从右到左遍历,依次类推。
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
先输出按层打印,再输出按ZigZag打印。
8 1 1 2 3 2 4 0 4 0 0 3 5 6 5 7 8 6 0 0 7 0 0 8 0 0
Level 1 : 1 Level 2 : 2 3 Level 3 : 4 5 6 Level 4 : 7 8 Level 1 from left to right: 1 Level 2 from right to left: 3 2 Level 3 from left to right: 4 5 6 Level 4 from right to left: 8 7
#include <stdio.h> #include <stdlib.h> #define not ! typedef int Id; const int N = 5E5; typedef struct { Id id; Id l_child, r_child; } TreeNodeInfo, *INFO; typedef struct TreeNode { Id id; struct TreeNode* left; struct TreeNode* right; } TreeNode, *PTNode, *BT; void swap(int* a, int* b) { if (a == b) return; *a ^= *b, *b ^= *a, *a ^= *b; } void reverse(int* arr, const int arrSize) { int l = 0, r = arrSize - 1; while (l < r) swap(arr + l++, arr + r--); } BT CreateBT(INFO infos, Id root_id) { // recursion exit condition if (!root_id) return NULL; BT t = (PTNode) malloc(sizeof(TreeNode)); if (!t) return NULL; t->id = root_id; t->left = CreateBT(infos, (*(infos + root_id)).l_child); t->right = CreateBT(infos, (*(infos + root_id)).r_child); return t; } void levelOrder(BT t) { // corner case if (!t) return; PTNode q[N]; int front = 0, rear = 0; *(q + rear++) = t; int level = 1; while (front < rear) { fprintf(stdout, "Level %d :", level); size_t s = rear - front; while (s--) { t = *(q + front++); fprintf(stdout, " %d", t->id); if (t->left) *(q + rear++) = t->left; if (t->right) *(q + rear++) = t->right; } ++level; fputc(10, stdout); } } void levelOrderZigZag(BT t) { // corner case if (!t) return; PTNode q[N]; int front = 0, rear = 0; *(q + rear++) = t; int level = 1; int i, vals[(int)1E4], valsSize; while (front < rear) { printf(level & 1 ? "Level %d from left to right:" : "Level %d from right to left:", level); valsSize = 0; size_t s = rear - front; while (s--) { t = *(q + front++); *(vals + valsSize++) = t->id; if (t->left) *(q + rear++) = t->left; if (t->right) *(q + rear++) = t->right; } if (!(level & 1)) reverse(vals, valsSize); for (i = 0; i < valsSize; ++i) fprintf(stdout, " %d", *(vals + i)); ++level; fputc(10, stdout); } } int main(const int argc, const char* const argv[]) { int n, root_id; fscanf(stdin, "%d %d", &n, &root_id); TreeNodeInfo infos[n + 1]; Id fa, lch, rch; while (n--) { fscanf(stdin, "%d %d %d", &fa, &lch, &rch); (*(infos + fa)).id = fa; (*(infos + fa)).l_child = lch; (*(infos + fa)).r_child = rch; } BT t = CreateBT(infos, root_id); levelOrder(t); levelOrderZigZag(t); return 0; }