西安网站建设huanxi,现在不流行做网站了么,wordpress国内博客主题,网站设计策划书案例题目链接#xff1a;
二叉树遍历_牛客题霸_牛客网二叉树的前序、中序、后序遍历的定义#xff1a; 前序遍历#xff1a;对任一子树#xff0c;先访问根#xff0c;然后遍历其左子树#xff0c;最。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/43719512169…题目链接
二叉树遍历_牛客题霸_牛客网二叉树的前序、中序、后序遍历的定义 前序遍历对任一子树先访问根然后遍历其左子树最。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/437195121692587727256
描述
二叉树的前序、中序、后序遍历的定义 前序遍历对任一子树先访问根然后遍历其左子树最后遍历其右子树 中序遍历对任一子树先遍历其左子树然后访问根最后遍历其右子树 后序遍历对任一子树先遍历其左子树然后遍历其右子树最后访问根。 给定一棵二叉树的前序遍历和中序遍历求其后序遍历提示给定前序遍历与中序遍历能够唯一确定后序遍历。
输入描述
两个字符串其长度n均小于等于26。 第一行为前序遍历第二行为中序遍历。 二叉树中的结点名称以大写字母表示ABC....最多26个结点。
输出描述
输入样例可能有多组对于每组测试样例 输出一行为后序遍历的字符串。
示例1
输入
ABC
BAC
FDXEAG
XDEFAG
输出
BCA
XEDGAF 思路
先来一个例子
先序遍历序列为FDXEAG
中序遍历序列为XDEFAG
要根据先序序列和中序序列确定这个二叉树通用的步骤为
1.根据先序序列的第一位确定这棵树的根
2.在中序序列中找到根的所在的位置根的左边就是该树的左子树的节点根的右边就是该树的右子树的节点
3.根据树的左子树节点和右子树节点在先序序列中分别找到对应的子串
4.对3中找到的两个子串分别重复1 2 3步左子树节点用于构建左子树右子树节点用于构建右子树直到所有的节点都用于构建这棵树。 示例
根据以上的案例走一遍
1.由先序遍历序列为FDXEAG可知树的根节点为F
2.在中序遍历序列XDEFAG找到F的索引为3左边XDE就是该树的左子树的节点右边AG就是该树的右子树的节点
3.根据树的左子树节点XDE和右子树节点AG在先序序列中分别找到对应的子串分别为DXE和AG
4.对DXE和AG分别重复步骤1 2 3DXE用于构建左子树AG用于构建右子树直到所有的节点都用于构建树。
每执行完第一轮步骤1 2 3所用的根节点已经用于构建树了后续就不用再考虑了。例如执行完第一轮步骤1 2 3根节点F已经用过了后续就不用再考虑了。 分析
相信思路都很明确步骤大概也明白了接下来代码实现中一个非常注重细节的地方就是递归构建左子树和右子树的部分再详细说就是在递归调用构建树的函数中我们要传入的两个参数应该怎么确定。
本次主要介绍利用先序遍历序列和中序遍历构建一个二叉树并输出后序遍历的方法我们在递归调用构建树的函数中我们要传入的两个参数当然就是子树的先序遍历序列和中序遍历序列。创建左子树时就传入左子树的先序遍历序列和中序遍历序列创建右子树时就传入右子树的先序遍历序列和中序遍历序列。
以下根据以上案例详细分析对于
索 引012345
先序遍历序列为FDXEAG中序遍历序列为XDEFAG 将以上两个遍历序列分别命名为字符串s1,s2即s1 FDXEAG s2 XDEFAG。根据s1可知树的根为F在s2中寻找到F的索引定义为pos为3。根据s2可得左子树包括的字符有XDE由s2.substr(0, pos)获得右子树包括的字符有AG由s2.substr(pos1)获得在s1中对应的字符串分别为DXE由s1.substr(1, pos)获得和AG由s1.substr(pos1)获得。根据以上获得的四个参数可以递归创建左子树和右子树。 源代码
//根据先序遍历和中序遍历确定一个二叉树
// 二叉树节点结构定义
struct TreeNode {char data;TreeNode* leftChild;TreeNode* rightChild;TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL){}
};// 根据先序遍历和中序遍历构建二叉树
TreeNode* Build(string str1, string str2) {if (str1.size() 0) {return NULL;}// 取先序遍历的第一个字符作为根节点char c str1[0];// 在中序遍历中找到根节点的位置int pos str2.find(c);// 创建根节点TreeNode* root new TreeNode(c);递归构建左子树root-leftChild Build(str1.substr(1, pos), str2.substr(0, pos));递归构建右子树root-rightChild Build(str1.substr(pos 1), str2.substr(pos 1));return root;
}// 后序遍历输出
void postOrder(TreeNode* root) {if (root NULL) {return;}//先遍历左子树postOrder(root-leftChild);//再遍历右子树postOrder(root-rightChild);//输出当前根节点的值cout root-data;return;
}int main()
{string s1, s2;while (getline(cin, s1)) {getline(cin, s2);TreeNode* root Build(s1, s2);postOrder(root);cout endl;}return 0;
}示例运行结果
