浅谈二叉树
前言
(初级数据结构鲨我)
之前寒假集训的时候基础数据结构就学的不太好,很多还是眼高手低,这几天正好开始准备PTA天梯赛的题,L2的题都是这种基础数据结构模拟题,欠账出来都是要还的,今天正好趁着刚学的热乎劲写一下理解,供日后参考
二叉树的三种遍历
四种主要的遍历思想为:
前序遍历:根结点 —> 左子树 —> 右子树
中序遍历:左子树—> 根结点 —> 右子树
后序遍历:左子树 —> 右子树 —> 根结点
层次遍历:只需按层次遍历即可
对于这个树来说
前序遍历:
124753689
1 2 3 4 5 6 7 8 9
| void pre_read(node *tree) { if (tree != NULL) { cout << tree->num << " "; pre_read(tree->lchild); pre_read(tree->rchild); } }
|
中序遍历:
742513869
1 2 3 4 5 6 7 8 9 10
| void in_read(node *tree) { if (tree != NULL) { pre_read(tree->lchild); cout << tree->num << " "; pre_read(tree->rchild); } }
|
后序遍历:
745289631
1 2 3 4 5 6 7 8 9 10
| void post_read(node *tree) { if (tree != NULL) { post_read(tree->lchild); post_read(tree->rchild); cout << tree->num << " "; } }
|
层序遍历:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| void floor_read(node *tree) { queue<node *> q; q.push(tree); while (!q.empty()) { node *remp; remp = q.front(); q.pop(); cout << remp->num << " "; if (remp->lchild != NULL) { q.push(remp->lchild); } if (remp->rchild != NULL) { q.push(remp->rchild); } } }
|
那么这三种遍历有什么特点呢?*
三种遍历构建二叉树
已知前序和中序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| int inorder[maxn]; int preorder[maxn]; int postorder[maxn]; struct node { int num; node *lchild; node *rchild; };
node *build(int pre[], int in[], int len) { if (len == 0) return NULL; int rootnode = 0; for (rootnode = 0; in[rootnode] != pre[0]; rootnode++) ; node *tree = new node; tree->num = pre[0]; tree->lchild = build(pre + 1, in, rootnode); tree->rchild = build(pre + rootnode + 1, in + rootnode + 1, len - rootnode - 1); return tree; } main函数: main() { node *head = new node; head = build(preorder, inorder, N); }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| int inorder[maxn]; int preorder[maxn]; int postorder[maxn]; struct node { int num; node *lchild; node *rchild; };
node *create(int post[], int in[], int len) { if (len == 0) return NULL; int rootnode = 0; for (rootnode = 0; in[rootnode] != post[len - 1]; rootnode++) ; node *tree = new node; tree->num = post[len - 1]; tree->lchild = create(post, in, rootnode); tree->rchild = create(post + rootnode, in + 1 + rootnode, len - rootnode - 1); return tree; } main() { node *head = new node; head = create(postorder, inorder, N); }
|
已知前序后序
- 无解!!!
仅仅知道前序和后序无法构造唯一二叉树!*三种遍历构建完全二叉树
- 知后序构建完全二叉树且求其层序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include <bits/stdc++.h> using namespace std; #define maxn 100000
int post[maxn]; int tree[maxn]; int node = 1; int n; void build(int tree[], int cnt) { if (cnt > n) return; build(tree, cnt * 2); build(tree, cnt * 2 + 1); tree[cnt] = post[node++]; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> post[i]; } int cnt = 0; build(tree, 1); cout << tree[1]; for (int i = 2; i <= n; i++) cout << " " << tree[i]; return 0; }
|
- 知前序构造完全二叉树且求其层序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include <bits/stdc++.h> using namespace std; #define maxn 100000
int pre[maxn]; int tree[maxn]; int node = 1; int n; void build(int tree[], int cnt) { if (cnt > n) return; tree[cnt] = pre[node++]; build(tree, cnt * 2); build(tree, cnt * 2 + 1); } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> pre[i]; } int cnt = 0; build(tree, 1); cout << tree[1]; for (int i = 2; i <= n; i++) cout << " " << tree[i]; return 0; }
|
大杂烩
读前序后序中序数组一定要从下标0开始读!(别问我怎么知道的)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
| #include <bits/stdc++.h> using namespace std;
#define maxn 50 int N; int inorder[maxn]; int preorder[maxn]; int postorder[maxn]; struct node { int num; node *lchild; node *rchild; }; node *build(int pre[], int in[], int len) { if (len == 0) return NULL; int rootnode = 0; for (rootnode = 0; in[rootnode] != pre[0]; rootnode++) ; node *tree = new node; tree->num = pre[0]; tree->lchild = build(pre + 1, in, rootnode); tree->rchild = build(pre + rootnode + 1, in + rootnode + 1, len - rootnode - 1); return tree; } node *create(int post[], int in[], int len) { if (len == 0) return NULL; int rootnode = 0; for (rootnode = 0; in[rootnode] != post[len - 1]; rootnode++) ; node *tree = new node; tree->num = post[len - 1]; tree->lchild = create(post, in, rootnode); tree->rchild = create(post + rootnode, in + 1 + rootnode, len - rootnode - 1); return tree; } void floor_read(node *tree) { queue<node *> q; q.push(tree); while (!q.empty()) { node *remp; remp = q.front(); q.pop(); cout << remp->num << " "; if (remp->lchild != NULL) { q.push(remp->lchild); } if (remp->rchild != NULL) { q.push(remp->rchild); } } } void pre_read(node *tree) { if (tree != NULL) { cout << tree->num << " "; pre_read(tree->lchild); pre_read(tree->rchild); } } void in_read(node *tree) { if (tree != NULL) { pre_read(tree->lchild); cout << tree->num << " "; pre_read(tree->rchild); } } void post_read(node *tree) { if (tree != NULL) { post_read(tree->lchild); post_read(tree->rchild); cout << tree->num << " "; } } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> N; for (int i = 0; i < N; i++) { cin >> inorder[i]; } for (int i = 0; i < N; i++) { cin >> preorder[i]; } for (int i = 0; i < N; i++) { cin >> postorder[i]; } node *head = new node; head = create(postorder, inorder, N); floor_read(head); cout << endl; pre_read(head); cout << endl; in_read(head); cout << endl; post_read(head); cout << endl; return 0; }
|
我自己造的输入样例:
1 2 3 4
| 7 1 2 3 4 5 6 7 4 1 3 2 6 5 7 2 3 1 5 7 6 4
|
输出样例:
1 2 3 4
| 4 1 6 3 5 7 2 4 1 3 2 6 5 7 1 3 2 4 6 5 7 2 3 1 5 7 6 4
|
自勉
醍醐灌顶!以此自勉!