-
判断是否为二叉搜索树&&已知前(后)序遍历和中序遍历求后(前)序遍历
2020-11-26 20:23:40此时已知前(后)序遍历和中序遍历 根据二叉树的性质,已知前(后)序遍历和中序遍历可以唯一的确定一颗二叉树 思路 递归思想,首先找到前序遍历中的根节点(第一个节点),再找出该值对应在中序遍历序列中的位置,...给定前序或后序的序列,判断该序列是否能构成一颗二叉搜索树(或镜像的二叉搜索树)
假设能构成一颗二叉搜索树,那么这棵树的中序遍历必定为有序的序列
此时已知前(后)序遍历和中序遍历
根据二叉树的性质,已知前(后)序遍历和中序遍历可以唯一的确定一颗二叉树思路
递归思想,首先找到前序遍历中的根节点(第一个节点),再找出该值对应在中序遍历序列中的位置,分界后分别对左右子树进行递归。注意:由于可能存在数值相同的节点,根据原树和镜像树的不同需要找到中序遍历中第一次出现或是最后一次出现对应的节点,具体见代码
此算法也可用于已知前(后)序遍历和中序遍历求后(前)序遍历
代码实现
//此算法假定中序遍历为升序且已知前序遍历 #include <iostream> #include <algorithm> using namespace std; const int N = 1010; int n, cnt; int preorder[N], inorder[N], postorder[N]; //分别表示前、中、后序遍历 bool build(int il, int ir, int pl, int pr, int t) //是否能建树 { int root = preorder[pl]; //当前根节点的数值 int k; //中序遍历的根节点的位置 if (t == 0) //表示为原二叉搜索树 { for (k = il; k <= ir; k ++ ) //找出中序遍历中第一次出现的位置 if (root == inorder[k]) break; } else //镜像 { for (k = ir; k >= il; k -- ) //找出中序遍历中最后一次出现的位置 if (root == inorder[k]) break; } if (k > ir || k < il) return false; //不能在中序遍历对应的位置找出根节点的值,说明无法建树 bool f = true; if (il < k && !build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, t)) f = false; //左子树存在 if (k < ir && !build(k + 1, ir, pr - (ir - k - 1), pr, t)) f = false; //右子树存在 postorder[cnt ++ ] = root; //递归后记录的即为后序遍历 //若是记录前序遍历,需在递归前记录 return f; } int main() { cin >> n; for (int i = 0; i < n; i ++ ) { cin >> preorder[i]; inorder[i] = preorder[i]; } sort(inorder, inorder + n); //升序排列 if (build(0, n - 1, 0, n - 1, 0)) { cout << "YES\n"; cout << postorder[0]; for (int i = 1; i < n; i ++ ) cout << ' ' << postorder[i]; } else { //判断镜像能否建树 reverse(inorder, inorder + n); cnt = 0; if (build(0, n - 1, 0, n - 1, 1)) { cout << "YES\n"; cout << postorder[0]; for (int i = 1; i < n; i ++ ) cout << ' ' << postorder[i]; } else cout << "NO"; } return 0; }
题目来源:PAT甲级1043 Is It a Binary Search Tree
-
树和森林的遍历
2016-10-15 17:23:03树的遍历主要有先根遍历和后根遍历。 先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。 后根遍历:若树非空,则按照从左到...树和森林的遍历
@(数据结构)
不要带着二叉树的遍历来限制了对树的遍历的理解。
树的遍历的定义:以某种方式访问树中的每一个结点,且仅访问一次。
树的遍历主要有先根遍历和后根遍历。-
先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。
-
后根遍历:若树非空,则按照从左到右的顺序遍历根结点的每一棵子树,之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。
根据这幅图:
树的先根遍历:A-B-E-F-G-C-H-D-I-J
对应的二叉树的先序遍历:A-B-E-F-G-C-H-D-I-J二者是一致的。
树的后根遍历:E-F-G-B-H-C-I-J-D-A
对应的二叉树的后序遍历:G-F-E-H-J-I-D-C-B-A
对应的二叉树的中序遍历:E-F-G-B-H-C-I-J-D-A(与树的后根遍历相一致)注意到我们并没有定义一般树的中根遍历,因为子结点该怎么分两部分并没有定义,所以只定义先、后根。
以上只是模拟证实。
森林的遍历:需要澄清的是,只有二叉树森林才有中序遍历与完整二叉树中序遍历对应
先序遍历森林。- 若森林非空,访问森林的第一棵树的根结点。
- 先序遍历第一棵树中根结点的子树
- 先序遍历除去掉遍历过的树的森林
中序遍历森林:普通的树构成的森林是不存在中序遍历的,这里的中序遍历必然指代的是化成二叉树的森林。
后序遍历也可以相似定义。
我们看这个森林和二叉树的各种遍历。
森林的先根遍历:A-B-C-D-E-F-G-H-J-I
二叉树森林的先序遍历:A-B-C-D-E-F-G-H-J-I(相同)
完整二叉树的先序遍历:A-B-C-D-E-F-G-H-J-I (相同)森林的后根遍历:B-C-D-A-F-E-J-H-I-G
二叉树森林的后序遍历:D-C-B-A-F-E-J-I-H-G
完整二叉树的后序遍历:D-C-B-F-J-I-H-G-E-A(不同于二叉树森林的后序遍历)
二叉树森林的中序遍历:B-C-D-A-F-E-J-H-I-G(与森林的后根遍历相同)
完整二叉树的中序遍历:B-C-D-A-F-E-J-H-I-G(与森林的后根遍历相同,自然也与二叉树森林的中序遍历相同)2019.10 Update:
END.
-
-
利用后中遍历结果,重构二叉树
2020-03-03 01:13:34对于后中重构中,我们很容易得到右子树的根,却难得到左子树的根,利用上述结论,可以间接求出右子树的长度,进而确定中序遍历中,左子树的位置,进而找到后序中,左子树的根具体在哪 L2-006树的遍历(25分) 给定一...这个题是利用树的基础,来模拟人为通过后中重构树的过程
有个小技巧在于,前中后遍历中,虽然所得结果的排序不同,但是子树所在的区域近乎相同,相差不大于1
对于后中重构中,我们很容易得到右子树的根,却难得到左子树的根,利用上述结论,可以间接求出右子树的长度,进而确定中序遍历中,左子树的位置,进而找到后序中,左子树的根具体在哪
L2-006 树的遍历 (25分)
给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例:
7 2 3 1 5 7 6 4 1 2 3 4 5 6 7
输出样例:
4 1 6 3 5 7 2
#include<iostream> #include<cstdio> #include<queue> using namespace std; #define MAXN 50 int hind[MAXN]; int mid[MAXN]; int n; int index,lnum,rnum; struct node { int value; node *left; node *right; }*T = NULL; void Create(node *&R,int l,int r,int index) { if(l>r) return; int p; R = new node; R->value = hind[index]; R->left = NULL; R->right = NULL; for(int i = l; i <= r; i++) if(mid[i] == hind[index]) {p = i;break;}; Create(R->right,p+1,r,index-1); Create(R->left,l,p-1,index+p-r-1); } void bfs() { queue<node*> q; q.push(T); bool flag = false; while(!q.empty()) { node* temp = q.front(); q.pop(); if(!flag) { flag = true; printf("%d",temp->value); } else printf(" %d",temp->value); if(temp->left) q.push(temp->left); if(temp->right) q.push(temp->right); } } int main() { cin>>n; for(int i = 0; i < n; i++) scanf("%d",&hind[i]); for(int i = 0; i < n; i++) scanf("%d",&mid[i]); Create(T,0,n-1,n-1); bfs(); return 0; }
-
数据结构—树和森林的遍历方法
2020-09-17 21:36:21树的遍历主要有先根遍历和后根遍历。 先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。 后根遍历:若树非空,则按照从左到...树的遍历
树的遍历主要有
先根遍历
和后根遍历
。先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。
后根遍历:若树非空,则按照从左到右的顺序遍历根结点的每一棵子树,之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。
森林的遍历
森林的遍历包括
先序遍历
和中序遍历
。若森林非空:
先序遍历
- 访问森林的第一棵树的根结点
- 先序遍历第一棵树中根结点的子树
- 先序遍历除去掉遍历过的树的森林
中序遍历
- 中序遍历第一棵树中根结点的子树
- 访问第一棵树的根结点
- 中序遍历除去掉遍历过的树的森林
总结
树、森林、二叉树之间的遍历有对应的关系
树 森林 二叉树 先根遍历 先序遍历 先序遍历 后根遍历 中序遍历 中序遍历 参考
王道2021数据结构
-
数据结构——树和森林的遍历方法
2017-10-15 12:22:51树的遍历主要有先根遍历和后根遍历。 2、(1)先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。 (2)后根遍历:若树非空... -
二叉树的随机生成及其遍历.docx
2020-10-24 06:55:01二叉树的随机生成及其遍历 张 zhaohan 10804XXXXX 2010/6/12 问题重述 利用随机函数产生 50个 ( 不大于 100且各不相同的 )随机整数用这些整数来生成一棵二叉 树分别对二叉树进行先根遍历中根遍历和后根遍历并输出树... -
从前序/后序遍历与中序遍历构造二叉树
2020-02-11 20:26:26题目 思路 先知道一个定律:从前序/后序遍历+...所以当我们知道前序遍历和中序遍历后,大体思路如下: 前序遍历的第一个为根节点 接着我们去中序遍历中寻找根节点所在位置,那么根节点前面的就是左子树所有的节... -
数据结构:树、图的遍历
2017-10-17 10:03:15后根遍历:树非空,则按照从左到右的顺序遍历根节点的每一颗子树,之后在访问根节点。其访问顺序和这棵树对应的二叉树的中序遍历顺序相同。 二叉树:先序遍历,后序遍历,中序遍历 图的遍历 ... -
根据二叉树遍历的先序序列和中序序列,建立二叉树的二叉链表
2019-08-08 00:27:17题目描述:设一棵二叉树各结点的值各不相同,其先序遍历序列和中序遍历序列分别存于两个一维数组A[1...n]和B[1..n]中,试编写算法建立该二叉树的二叉链表。 算法思想:根据二叉树的先序遍历序列和中序遍历序列可以... -
二叉树的建立和遍历(递归、非递归)
2015-11-09 21:29:36如果在算法中暂时忽略访问根节点的printf语句,则3种遍历算法完全相同。因此,从递归执行的角度来看,先序、中序和后序遍历是完全相同的。上图中的用带箭头的虚线表示这3种遍历算法执行的过程。其中,向下的箭头表示... -
先序遍历-递归和非递归(java版)
2018-11-20 20:52:56根据先序遍历访问的顺序,优先访问根结点,然后再分别访问左孩子和右孩子。即对于任一结点,其可看做是根结点,因此可以直接访问,访问完之后,若其左孩子不为空,按相同规则访问它的左子树;当访问其左子树时,再... -
剑指offer-二叉搜索树的后序遍历序列(python和c++)
2020-04-22 10:32:58后序遍历的序列中,最后一个数字是树的根节点 ,数组中前面的数字可以分为两部分:第一部分是左子树节点 的值,都比根节点的值小;第二部分 是右子树 节点的值,都比 根 节点 的值大,后面用递归分别判断前... -
UVa 548(二叉树的递归遍历、dfs)
2017-08-09 21:01:33题意:给一颗点带权(权值各不相同,都是小于10000的正整数)的二叉树的...首先我想先改变这几个遍历的名字(前根序遍历,中根序遍历,后根序遍历);前中后本来就是相对于根结点来说的,少一个字会产生很多不必要的误 -
二叉树——不建树遍历
2017-12-04 21:59:42原理和我写过的“二叉树——根据先序(后序)和中序遍历建树”中的原理是相同的,除了一个层序遍历,这里说明一下层序遍历的原理: 加一个变量index,表示当前的根结点在二叉树中所对应的下标(从1开始),所以进行... -
刷题笔记:二叉树的花式遍历(未完成)
2018-06-10 17:05:40最常规的遍历是三序遍历:先、中、后。区别在于打印节点的顺序。 先序遍历是“根-左-右”,中序遍历是“左-根-右”,后序遍历是“左-右-根”。 遍历方法有两种:递归和迭代。绝大多数二叉树题目都涉及递归,递归也... -
Leetcode练习:从中序与后序遍历序列构造二叉树,递归与迭代,python实现。
2019-09-06 15:21:20二:同一个树中序遍历和后序遍历包含元素相同(顺序不同),通过中序遍历的分隔点返回后序遍历,找到左右子树的后序遍历。 两点注意事项:一个是小心笔误;第二个是找到根节点后,到中序遍历中找到分隔点,这个分隔... -
求后序遍历序列的第k个结点值_剑指Offer(二十三):二叉搜索树的后序遍历序列...
2020-12-06 13:24:051、思路举例说明:以{5,7,6,9,11,10,8}为例,后序遍历结果的最后一个数字8就是根结点的值。在这个数组中,前3个数字5、7和6都比8小,是值为8的结点的左子树结点;后3个数字9、11和10都比8大,是值为8的结点的右子树... -
二叉树应用_二叉搜索树的后续遍历序列
2018-06-13 16:03:45分析:在二叉搜索树的后序遍历中,根节点在最后面。前面的序列可以分为两个部分:一个为左子树,小于根节点的值;一个为右子树,大于根节点的值。左子树序列和右子树序列同样应该为后序遍历序列,则可以通过递归判断... -
剑指offer刷题 二叉搜索树的后序遍历序列
2019-04-30 15:31:06题意 输入一个整数数组,判断该数组是不是某二叉...思路注意这里是二叉搜索树的后序遍历所以根结点一定在后面最后一个元素,思路和二叉树的重建是一样的 在后序遍历的数组中找到左子树的区间和右子树的区间 class So... -
牛客网剑指Offer(二叉搜索树的后序遍历序列)
2020-06-25 12:08:11由于二叉搜索树中左子树的值都比根节点小,右子树都比根节点大,使用后序遍历时最后一个值为根节点的值,所以确定根节点后,遍历序列寻找第一个比根节点值大的数,则该数的左边都比根节点小,为左子树;右边为右子树... -
剑指offer刷题————二叉搜索树的后序遍历序列
2020-05-29 17:43:08首先这个数组是搜索二叉树的后序遍历,因为搜索二叉树满足左小右大的规则,并且后序遍历中最后一个遍历的是根节点,因此,我们能根据最后一个数字将数组分为两部分,前面的一部分都比最后一个节点小,后面的一部分都... -
23. 二叉搜索树的后序遍历序列(剑指offer)
2021-01-03 21:06:28以{5,7,6,9,11,10,8}为例,后序遍历结果的最后一个数字8就是根结点的值。在这个数组中,前3个数字5、7和6都比8小,是值为8的结点的左子树结点;后3个数字9、11和10都比8大,是值为8的结点的右子树结点。 ... -
剑指offer-----二叉搜索树的后序遍历序列
2018-02-05 15:11:21在后序遍历序列中,最后一个值是树的根节点,前面一部分结点是根的左子树;左子树后面,根节点前面是根的右子树。依次递归判断左子树和右子树是不是二叉搜索树。 3、代码如下 import java.util.Arrays; -
Leetcode 106. 从中序与后序遍历序列构造二叉树 解题思路及C++实现
2019-06-15 20:26:29区别在于,在这一题中,后序遍历的最后一个值为根节点。 然后仍然是找到根节点后,划分左右子树,递归构建。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left;... -
剑指Offer(二十三):二叉搜索树的后序遍历序列
2020-04-09 15:15:26以{5,7,6,9,11,10,8}为例,后序遍历结果的最后一个数字8就是根结点的值。在这个数组中,前3个数字5、7和6都比8小,是值为8的结点的左子树结点;后3个数字9、11和10都比8大,是值为8的结点的右子树结点。 我们接下... -
[二叉树]leetcode106:从中序与后序遍历构造二叉树(medium)
2019-08-19 17:35:001)后序数组的最后一个元素为根节点,根据根节点可将中序数组划分为左子树中序列表和右子树中序数组 2)又因为一棵树的中序数组长度与后序数组长度大小相同,所以可以根据长度划分后序数组为左右子树后序数组 3)... -
C++Builder画二叉树
2018-07-13 16:18:50二、若二叉树各结点的值均不相同,则由二叉树的前根遍历序列和中根遍历序列,由其中根遍历序列和后根遍历序列均能唯一确定一颗二叉树。根据输入的中根遍历序列和前(后)根遍历序列,以动画方式画出对应的二叉树 -
数据结构:第五章树和二叉树
2021-01-04 20:24:22数据结构:第五章树和...一颗树的后根遍历和该树的二叉树的中根遍历相同 二叉树的先根和中根相同,则无左子孩子 二叉树的先根和中根相反,则无右孩子 二叉树采用二叉链式存储结构 树采用孩子兄弟链表存储结构 ... -
《大话数据结构》——树、森林、二叉树的转换
2018-08-22 21:22:331.树转换为二叉树 ...当 以二叉链表作树的存储结构时,树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。 森林的遍历方法: 森林的前序遍历和二叉树的前序遍历结果相同,森...