-
二叉树先序遍历中序遍历建立二叉树然后后序遍历
2018-01-23 21:43:53题目描述 二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历 其左子树,最后遍历其右子树; 中序遍历:对任一子树,...前序遍历与中序遍历能够唯一确定后序遍历)。 输入 两个- 题目描述
二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历 其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问 根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子 树,最后访问根。 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定 前序遍历与中序遍历能够唯一确定后序遍历)。
- 输入
两个字符串,其长度n均小于等于26。 第一行为前序遍历,第二行为中序遍历。 二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。
- 输出
输入样例可能有多组,对于每组测试样例, 输出一行,为后序遍历的字符串。
- 样例输入
ABC BAC FDXEAG XDEFAG
- 样例输出
BCA XEDGAF
- 代码
#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct Bitree{ char data; struct Bitree * lchild; struct Bitree * rchild; } * BiTree,BiNode; void CreateBiTree(BiTree T,char * preOrder,char * inOrder,int preLow,int preHigh,int inLow,int inHigh){ T->lchild = NULL; T->rchild = NULL; T->data = preOrder[preLow]; if(preLow == preHigh) return; int i = inLow; while(inOrder[i] != preOrder[preLow]) i ++; if(i - 1 >= inLow){ T->lchild = (BiTree)malloc(sizeof(BiNode)); CreateBiTree(T->lchild, preOrder, inOrder, preLow + 1, preLow + i - inLow, inLow, i - 1); } if(inHigh >= i + 1){ T->rchild = (BiTree)malloc(sizeof(BiNode)); CreateBiTree(T->rchild, preOrder, inOrder, preLow + i - inLow + 1, preHigh, i + 1, inHigh); } } void PreOrder(BiTree T){ if(T != NULL){ printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T){ if(T != NULL){ InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); } } void PostOrder(BiTree T){ if(T != NULL){ PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); } } int main(int argc, const char * argv[]) { char preOrder[26],inOrder[26]; while(scanf("%s", preOrder) != EOF){ scanf("%s", inOrder); int n = strlen(preOrder); BiTree T = (BiTree)malloc(sizeof(BiNode)); T->lchild = NULL; T->rchild = NULL; CreateBiTree(T, preOrder, inOrder, 0, n - 1, 0, n - 1); PostOrder(T); printf("\n"); } return 0; }
- 总结
注意递归跳出条件 注意树的分配空间的时候,一定要防止断链 注意递归的使用条件
-
中序遍历 前序遍历 后序遍历 编程题_二叉树之由前序遍历和中序遍历求后序遍历——九度OJ题目1078:二叉树...
2021-01-12 07:04:21题目1078:二叉树遍历题目描述:二叉树的前序、中序、后序遍历的定义:前序...给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。输入:两个字符串,其长度...题目1078:二叉树遍历
题目描述:
二叉树的前序、中序、后序遍历的定义:
前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树;
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。
输入:
两个字符串,其长度n均小于等于26。
第一行为前序遍历,第二行为中序遍历。
二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。
输出:
输入样例可能有多组,对于每组测试样例,
输出一行,为后序遍历的字符串。
样例
输入:
ABC
BAC
FDXEAG
XDEFAG
样例输出:
BCA
XEDGAF
来源:
2006年清华大学计算机研究生机试真题
--------------------------------------------------------
解析
由前序遍历和中序遍历求后序遍历,这要求考生对三种遍历方式都有掌握。这里要用到前序遍历的根结点第一个被取出,而中序遍历的左子树在根结点之前取出、右子树在根结点之后取出,这两个性质。
C++实现如下
#include
#include
//1078:二叉树遍历
using namespace std;
//结点类
struct Node
{
Node * lchild;
Node * rchild;
char c;
};
//重建后续排序二叉树
Node * rebuild(string s1, string s2)
{
//建立根结点
Node * t=NULL;//一定要初始化为NULL,不然报错
if(s1.size()>0){
t=new Node;
t->c=s1[0];
t->lchild=NULL;
t->rchild=NULL;
}
if(s1.size()>1){
//寻找根结点在中序遍历中的位置
int root;
for(int i=0; i
if(s2[i]==t->c){
root=i;
break;
}
}
//左子树重建
string qianxu_left=s1.substr(1, root); //注意substr的用法,第二个参数是子字符串长度
string zhongxu_left=s2.substr(0, root);
t->lchild=rebuild(qianxu_left, zhongxu_left);
//右子树重建
string qianxu_right=s1.substr(root+1, s1.size()-root-1);
string zhongxu_right=s2.substr(root+1, s2.size()-root-1);
t->rchild=rebuild(qianxu_right, zhongxu_right);
}
return t;
}
//后序遍历:左右根
void houxu(Node * t)
{
//左子树非空,遍历左子树
if(t->lchild!=NULL)
houxu(t->lchild);
//右子树非空,遍历右子树
if(t->rchild!=NULL)
houxu(t->rchild);
//取出该结点的值
cout<c;
}
int main()
{
string s1, s2;
while(cin>>s1>>s2){
Node * t=rebuild(s1, s2);
houxu(t);
cout<
}
return 0;
}运行结果
Accepted 内存:1520KB 代码长度:1465B 耗时:10MS
-
先序遍历中序遍历后序遍历确定一棵二叉树(递归、非递归)
2016-09-16 14:04:46先序遍历和中序遍历确定二叉树 后序遍历和中序遍历确定二叉树先序遍历&中序遍历
递归做法:
递归做法比较容易理解,先在先序遍历中确定第一个点,这个点一定是根节点,然后在中序遍历中找到这个点的位置,那么这个位置之前的都是左子树,后边的都是右子树,然后分别递归。class Solution { public: int start = 0; TreeNode* build(vector<int>& pre,vector<int>& in, int ps,int pe, int is, int ie){ if (ps>=pe) return NULL; int val = pre[ps]; TreeNode* root = new TreeNode(val); int pos; for (int i=is;i<ie;i++){ if (in[i]==val) { pos=i; break; } } root->left = build(pre,in,ps+1,ps+pos-is+1,is,pos); root->right= build(pre,in,pe-ie+pos+1,pe,pos+1,ie); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return build(preorder,inorder,0,preorder.size(),0,inorder.size()); } };
非递归:
非递归的做法有些不好理解,核心思想有两点:
1 从先序遍历序列的头部开始从左向右访问,用一个栈保存访问过的节点,每次都要判断栈顶元素是否等于中序遍历的当前节点。2 如果相等,说明栈顶节点左子树遍历完毕,那么接下来的节点应该是前驱节点的右节点,标志位置1。如果不相等,那么先序遍历的下一个节点依然是前驱节点的左节点或右节点,需要根据标志位确定。
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { stack<TreeNode*> st; int n = int(preorder.size()); if (n == 0) return NULL; int i = 1, j = 0; TreeNode* root = new TreeNode(preorder[0]); bool flag = 0; TreeNode* pre = root; st.push(root); while (i < n){ if (!st.empty() && st.top() -> val == inorder[j]){ pre = st.top(); st.pop(); flag = 1; j++; } else if (flag){ pre -> right = new TreeNode(preorder[i++]); pre = pre -> right; st.push(pre); flag = 0; } else{ pre -> left = new TreeNode(preorder[i++]); pre = pre -> left; st.push(pre); } } return root; }
中序遍历&后序遍历
基本类似,区别是从后向前遍历后序序列
递归:class Solution { public: int find(vector<int> inorder, int v){ for (int i = 0; i < inorder.size(); ++i){ if (inorder[i] == v) return i; } return -1; } TreeNode* build(vector<int>& inorder, vector<int>& postorder, int s1, int e1, int s2, int e2){ if (s1 > e1) return NULL; else{ int v = postorder[e2]; int index = find(inorder, v); TreeNode* root = new TreeNode(v); root -> left = build(inorder,postorder,s1,index-1,s2,s2+index-1-s1); root -> right = build(inorder,postorder,index+1,e1,s2+index-s1,e2-1); return root; } } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int n = inorder.size(); if (n == 0) return NULL; return build(inorder,postorder,0,n-1,0,n-1); } };
非递归
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int n = inorder.size(); if (n == 0) return NULL; int i = n-1, j = n-2; TreeNode* root = new TreeNode(postorder[n-1]); TreeNode* pre = root; stack<TreeNode*> st; st.push(root); bool flag = 0; while (i >= 0){ if (!st.empty() && st.top() -> val == inorder[i]){ pre = st.top(); st.pop(); i--; flag = true; }else if (flag){ pre -> left = new TreeNode(postorder[j--]); pre = pre -> left; st.push(pre); flag = 0; }else{ pre -> right = new TreeNode(postorder[j--]); pre = pre -> right; st.push(pre); } } return root; }
-
已知二叉树的后序遍历和中序遍历重建二叉树(二叉树)
2017-01-28 10:20:11由中序遍历和后序遍历重建二叉树 中序遍历中,根节点总是位于左右子树中间,将左右子树分开。 后序遍历中,根节点总是在左右子树之后。 重建算法: 现在说一下重建根节点的过程,其他节点可以递归建立。 由后序遍历...由中序遍历和后序遍历重建二叉树
中序遍历中,根节点总是位于左右子树中间,将左右子树分开。
后序遍历中,根节点总是在左右子树之后。
重建算法:
现在说一下重建根节点的过程,其他节点可以递归建立。
由后序遍历定义可知,后序遍历序列的最后一个元素必定是整个树的根节点,这样就确定了根节点。
由中序遍历定义可知,在中序遍历中查找根节点,可以确定根节点在中序遍历序列中位置,这样就可以将中序遍历序列分为左右子树,一旦确定左右子树,左右子树的长度也就确定了,根据左右子树的长度,在后序遍历序列中,可以确定左右子树的根节点,这样递归下去既可以确定整个树。# -*- coding:utf-8 -*- class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, post, tin): # write code here if len(post) == 0 or len(tin) == 0: return None root = TreeNode(post[-1]) # 获取根节点在中序遍历中的位置 i = tin.index(post[-1]) """ 注意下面四个参数,可以根据测试样例推导出来 i为根节点 post[0 : i] i结点前面的是左子树的结点所以参数如上 tin[0 : i] 同上,i结点前面的为左子树,可以观察测试数据 post[i : -1] 根节点在最后一位,右子树的结点为从i开始到-1,不包括最后一个结点 tin[i + 1 : ] 中序遍历中i结点为根节点,i结点后面的为右子树的结点 """ # 遍历左子树 root.left = self.reConstructBinaryTree(post[0 : i], tin[0 : i]) # 遍历右子树 root.right = self.reConstructBinaryTree(post[i : -1], tin[i + 1 : ]) return root if __name__ == "__main__": a = Solution() post_order = [7, 4, 2, 5, 8, 6, 3, 1] # 后序遍历 mid_order = [4, 7, 2, 1, 5, 3, 8, 6] # 中序遍历 root = a.reConstructBinaryTree(post_order, mid_order) print root.val print root.left.val print root.right.val print root.left.left.val print root.left.left.right.val print root.right.right.left.val print root.right.left.val
-
给定二叉树的后序遍历和中序遍历如何确定一棵树
2019-08-12 17:22:46根据上面的特性,我们可以从后序遍历的最后一个数来确定这棵树的根节点,由这个数将中序遍历分割开来,分成 6 2 1 为左子树,3 9为右子树,然后后序遍历也可以由此分成 2 1 6 为左子树,9 3 为右子树,然后2 1 6,6 ... -
二叉树利用前序遍历和中序遍历求二叉树及二叉树的后序遍历
2020-10-28 11:01:18前序遍历和后序遍历确定的是根的位置,而中序遍历是二叉树的左右子树,所以如果同时有二叉树的前序遍历和后序遍历是不能求出二叉树的。下面给出已知前序遍历和中序遍历求二叉树及二叉树的方法 前序遍历:a b d e g c -
二叉树后序遍历_LeetCode106 从中序与后序遍历序列构造二叉树
2020-11-24 10:57:11通过递归,根据左子树的后序和中序遍历,以及右子树的后序和中序遍历,不断构造二叉树。这题比较关键的地方是,根据根节点,确定左子树和右子树在原来数组中的下标范围。我们可以画张图看看。代码如下public ... -
已知二叉树先序遍历中序遍历求其后序遍历、重建二叉树
2015-10-03 06:03:20(注:已知中序遍历序列和剩下两种遍历序列中的一种都可以确定二叉树,即可得到另一种遍历序列, 但是已知前序遍历和后序遍历序列并不能唯一确定二叉树,例如:preorder:ABpostorder:BA,我们不能确定B是A的左子... -
从前序/后序遍历与中序遍历构造二叉树
2020-02-11 20:26:26先知道一个定律:从前序/后序遍历+中序遍历可以确定一棵不存在相同节点的二叉树 我们先复习一下深度优先的三个遍历: 前序遍历:根节点——左子树——右子树 中序遍历:左子树——根节点——右子树 后序遍历:左... -
【数据结构】【二叉树】二叉树的前序中序和后序遍历技巧,已知二叉树前序和中序还原二叉树、已知二叉树后序...
2019-08-18 17:40:13中序遍历:先遍历二叉树的左孩子再遍历根再遍历右孩子。 后序遍历:先遍历二叉树的左孩子再遍历右孩子再遍历根。 从种遍历方式上可以分析出的规律有 a、前序遍历的根一定是第一个。 b、后序遍历的根一定是最后一... -
给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)
2018-05-19 23:11:53二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树; 后序遍历:对任一... -
由先序遍历/后序遍历以及中序遍历重构二叉树
2014-11-27 16:18:10我们知道在二叉树的遍历中,如果知道了二叉树的先序遍历顺序和中序遍历顺序,或者后序遍历顺序和中序遍历顺序,都可以唯一确定一棵二叉树,而不知道中序遍历顺序,只知道前序遍历的和后序遍历的顺序,是不能唯一确定... -
根据前序遍历与中序遍历,中序遍历与后序遍历构造二叉树
2021-02-04 21:56:33思路:用前序或者后序遍历找根,用中序遍历确定左右树。1.找到根2:在中序遍历当中找到根的位置,此时根的左边是作数右边是右树。 1.根据一棵树的前序遍历与中序遍历构造二叉树。 class Solution { public int ... -
已知二叉树后序遍历和中序遍历,求前序遍历
2013-08-16 09:14:58已知二叉树后序遍历序列是DBCEFGHA,中序遍历序列EDCBAHFG,它的前序遍历的序列是?麻烦再画下这二叉树. 后续遍历的顺序是左右根,中序遍历的顺序是左根右 这点应该懂吧 由后续访问序列可以看出最后一个被访问... -
刷题笔记:根据中序遍历与前序遍历确定二叉树&根据后序遍历与前序遍历确定二叉树
2020-11-20 22:57:20根据中序遍历与前序遍历确定二叉树 对于一棵树而言,前序遍历的形式为: [根节点,[左子树的前序遍历],[右子树的前序遍历]]。 中序遍历形式为: [[左子树的中序遍历],根节点,[右子树的中序遍历]] 因此,只要我们... -
给定二叉树的后序遍历和中序遍历,求其前序遍历(后中定序)
2018-08-15 11:34:37题目描述 二叉树的前序、中序、后序遍历的定义: ...给定一棵二叉树的后序遍历和中序遍历,求其前序遍历(提示:给定后序遍历与中序遍历能够唯一确定前序遍历)。 输入 两个字符串,其长度n均小于... -
一道二叉树的题目--后序遍历+中序遍历确定二叉树
2019-04-28 13:07:00这样的题目比较少, 但是据说计算机里就是使用后序遍历的..(忘记哪里说的了), 多做几次. 后序: KBFDCAE, 中序:BKEFACD ------------------------------------------------------------------ 第一轮: 出E---&... -
已知一棵二叉树的后序遍历和中序遍历,写出可以确定这棵二叉树的算法
2019-09-11 19:23:02CSDN已知一棵二叉树的后序遍历和中序遍历,写出可以确定这棵二叉树的算法 #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 105 typedef struct b... -
先序/后序遍历+中序遍历真的能唯一确定一个二叉树吗?
2020-10-27 00:04:09这是三个节点的二叉树的类型 树类型 先序遍历 中序遍历 ...也就是说先序ABC,中序CAB与...所以,这个结论应该是先序/后序遍历+中序遍历能确定一个二叉树,一个二叉树确定遍历,但是这树和这遍历没有一一对应的关系。 -
通过前序遍历和中序遍历确定二叉树,并输出后序遍历序列
2017-03-02 16:26:00我们知道,中序遍历和前序或者后序能够唯一确定一颗二叉树,因此,给定前序遍历以及中序遍历序列能够确定建立这颗二叉树,然后后序遍历便能够得到相应的序列 代码如下(内含二叉树的建立,求二叉树的高度) #... -
前序遍历 中序遍历 后序遍历
2015-01-23 14:04:37前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。 若二叉树为空则结束返回,否则: ...已知后序遍历和中序遍历,就能确定前序遍历。 -
中序和后序遍历确定二叉树 + 前序和中序遍历确定二叉树
2020-03-05 21:01:32105前序和中序遍历确定二叉树 根据一棵树的中序遍历与后序遍历构造二叉树 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder =[9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的... -
二叉树 根据前序遍历 中序遍历 写出后序遍历
2019-01-09 15:49:52中序遍历:左——中——右 先确定前序遍历的第一个节点为根节点,然后在中序遍历中找到该根节点,以根节点为基点,前一部分为左子树,后一部分为右子树。然后按照递归分部分操作。 伪代码 主方法{ 根节点 = 创建... -
已知二叉树的前序遍历、中序遍历或者中序遍历、后序遍历求二叉树结构的算法
2016-01-01 23:40:54算法思路是先根据前序遍历的第一个结点或者后序遍历的最后一个结点,查找对应在中序遍历中的位置,就可以确定左子树包含的元素和右子树包含的元素,最后通过递归来实现就可以了。 二叉树的表示形式为 //二叉树的... -
利用二叉树中序及后序遍历确定该二叉树的先序序列
2019-05-16 18:04:22利用二叉树中序及后序遍历确定该二叉树的先序序列 1000(ms) 10000(kb) 3046 / 6121 已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能... -
由后序遍历和中序遍历构建二叉树(C++语言)
2020-11-27 22:01:34不要自卑,去提升实力 互联网行业谁技术牛谁是爹 如果文章可以带给你能量...注意:要想构建二叉树,必须知道中序遍历,这样才可以知道根节点,进而确定左右子树 有前序和后序不能够构建二叉树 代码: /** *作者:魏..