如题,好像大学的课后作业。写一个练练手。网上不少,大多都是C或C++的。
一个二叉树前序遍历:GDAFEMHZ
中序遍历:ADEFGHMZ
求其后续遍历。
求解过程
0.这三种遍历不知道是什么意思的请自行搜索。
1.通过前序遍历我们可知此树根节点为G(即前序遍历第一个字符)
2.观测中序遍历可知此树左子树所有节点为:ADEF 右子树所有节点为:HMZ(以根节点划分)
3.得到左子树的前序遍历(DAFE)中序遍历(ADEF) 顺序未变。
4.得到右字数的前序遍历(MHZ)中序遍历(HMZ) 顺序未变。
5.递归此过程,展开所有子树。
代码如下:
定义二叉树的类
public class Tree { String root = "";//根节点 Tree left; //左子树 Tree right; //右子树 String pre = "";//前序遍历字符串 String in = "";//中序遍历字符串 String back = "";//后序遍历字符串 Tree(String s){ this.root = s; } Tree(){} }
实现代码:
public class testTree { public static String post = ""; /** * @param args */ public static void main(String[] args) { String pre = "GDAFEMHZ"; String in = "ADEFGHMZ"; Tree t = new Tree(); t.root = in; t.pre = pre; build(t); System.out.println(post); } /** * 采取后序遍历递归展开所有节点 * @param tree */ public static void build(Tree tree){ if(tree == null){ return; } open(tree); if(tree.left != null){ open(tree.left); build(tree.left); } if(tree.right != null){ open(tree.right); build(tree.right); } post = post + tree.root; } /** * 将节点不是单字符的节点展开 * @param tree */ public static void open(Tree tree){ if(tree.root.length()>1){ String s2 = tree.root; String s1 = tree.pre; tree.root =s1.substring(0, 1); String [] node = s2.split(tree.root); if(node.length>=2){ tree.left = new Tree(node[0]); tree.left.pre = s1.substring(1, node[0].length()+1); tree.right = new Tree(node[1]); tree.right.pre = s1.substring(s1.length()-node[1].length(), s1.length()); } } } }
相关推荐
二叉树已知后序和中序遍历求前序遍历,C++编写已通过编译
已知二叉树的前序和中序遍历,打印后序遍历,采用二叉树的非递归算法,分享给大家~~
根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...
已知中序遍历和后序遍历,求前序遍历。有比较详尽的中文注释。
数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
二叉树已知前序和中序遍历,求后序遍历,C++代码已编译通过,可直接运行
C++数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历.pdf
C语言,数据结构课程,知道中序和后序遍历,画二叉树和写出前序遍历。
数据结构 C/C++ 数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
1、深度优先遍历 2、广度优先遍历 3、求深度 4、已知二叉树前序中序,还原二叉树 5、已知前序和中序,求后序
已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树; (2)证明构造正确(即分别以前序和中序遍历该树,将得到的结果与给出的序列进行比较)。 (3)对该二叉树进行后序遍历,...
已知前序中序 构造二叉树,并求后序遍历 判断是否为平衡二叉树
一棵n个结点的完全二叉树用向量作存储结构,用非递归算法实现对该二叉树进行前序遍历。
二叉搜索树(排序二叉树),树的遍历(前序、中序、后序)【数据结构和算法入门7】
已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树; (2)证明构造正确(即分别以前序和中序遍历该树,将得到的结果与给出的序列进行比较)。 (3)对该二叉树进行后序遍历,...
二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。为啥叫这个名字?是根据根节点的顺序命名的。 比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先...
在完全二叉树中,在层次遍历和先根序遍历中,已知某节点在一种遍历中的编号,求该节点在另一种遍历中的编号。 程序描述: q = 1表示已知某节点在先根序遍历中的编号,求的是它在层次遍历中的编号。 q = 2表示已知的...
1.已知一棵二叉树的中序遍历结点排列为DGBAECHIF,后序遍历结点排列为GDBEIHFCA,(也可以换成已知 中序和先序遍历的内容) (1)试画出该二叉树; (2)试写出先序遍历排列;(写出没有给出的那种遍历序列) (3)...
C++源码,可在VC6.0环境下直接运行,核心代码非常经典,不到10行且易懂。