这是我的页面头部
　　已知二叉树的先/后根序遍历和中根序遍历可唯一确定一棵二叉树，数据结构试题中常有已知先(后)根序遍历要求确定后（先）根序遍历题型。一般的，我们要按照已知的条件把二叉树画出来，再按图写出结果。这样麻烦的事常让我感到混乱而不得不出错。经过研究我找出了一种不用画图，由先（后）根序遍历和中根序遍历迅速确定遍历结果的办法。谨以此文献给智商与我同级而又不得不研究算法的朋友。
抽象思维太差，用例子来说明吧。下面这个是后根遍历的算法。
例1：已知某二叉树的先根序遍历为ABCDEFG,中根序遍历为CDBAFEG，则它的后根序遍历为_________
解法如下：
1、确定树根。由先序遍历知道，树根为A。
2、分离左、右子树。由中根序遍历知，A左面的为CDB左子树结点，右面的FEG为右子树结点。
把先根序遍历也分成左、右子树结点，BCD、EFG。
　　　　　　前根序遍历　BCD&EFG
中根序遍历　CDB&FEG
3、分别把先根序遍历左、右子树结点抄过来，写的时候要从右往左写，本例中，依次写下B、C、D、，E、F、G，结果是DCB GFE。
当然不是简单到这种程序。上面只是个原理。抄的过程应该是这样的：盯着前根序的，瞅着中根序的。如果要抄的先根序中的结点在中根序中是最左/右边，则直接抄过来；如果不是，则把这个结点左边的结点先放记在右根序的最左边，然后继续抄。本题的结果是DCB,FGE,A, 即DCBFGEA。
上面这个例子太短，看不出“猫腻”来。再举个结点多一点儿的。
&　　例2：已知某二叉树的先根序遍历为ABCDEFGHIJK,中根序遍历为CEDFBAHKJIG，则它的后根序遍历为_________
&　　按上面的方法：
　　　　　　前根序遍历　BCDEF& GHIJK
　　　　　　中根序遍历　CEDFB &HKJIG
依次抄得前根序的结点：F、E(E在中根序遍历中不靠边，所以先放在后根遍序历中左子树结点最左边)、D、C
同理，把右子树也抄过来。因此，写下结点的过程依次是：
如果还是不太懂，你可以试着做一下下面的例子：
已知二叉树前序遍历 ABCDEFGHIJK，中序遍历 CEDFBAHGKJI，求后序遍历。
解：(1)以根结点A分左、右子树结点，
&&&&&&&&&&&&&&&& BCDEF GHIJK
&&&&&&&&&&&&&&&& CEDFB HGKJI
(2)　写左子树，盯着前序，从右到左开始写
&&&&&&&&&&&&&&&&&&&&&&DCB　（在中序中，B靠右边，C靠左边，D不靠边。写一个，从中序中抹一个。）
因为D在中序遍历中不靠边，所以下一个结点E先搁到最左边（注意，是“搁”，也就是说，不能把E从中序抹去。
因为B已经抹了，F靠右边。于是F仍然按照从右到左的规则，写在D的的左边。
最后把E加上，左子树OK。
右子树仍然从右到写
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& G
因为G不靠边，所以下一个结点H先搁在最左边
H&&&&&&&&& G
&&&&&&&&&&&&&&&&&&&&&&&&&&& H&&&&&&&&& KJIG
于是，结果是
EFDCBHKJIGA　
前根序遍历类似。
以上的方法只适用于三层以内的二叉树（含三层）。在选择题中，三层以上二叉树也可用以上方法初步判断正确答案。&
阅读(...) 评论()博客分类：
1.二叉树，一种递归的数据结构，一棵非空的二叉树由根节点以及左右子树组成。
在任一给定结点上，可以按某种次序执行三个操作：
1）访问结点本身（N）
2）遍历该结点的左子树（L）
3）遍历该结点的右子树（R）
因此根据这三种操作的先后次序，可分为：
a）NLR 前序遍历
(PreorderTraversal亦称（先序遍历））——访问根结点的操作发生在遍历其左右子树之前。
b）LNR 中序遍历
(InorderTraversal）——访问根结点的操作发生在遍历其左右子树之中。
c）LRN 后序遍历
(PostorderTraversal）——访问根结点的操作发生在遍历其左右子树之后。
什么先根，中根，后根是同一东西。注意，无论哪种次序，每个节点只被访问一次。
以下是示例，基于下图实验：
1.TreeNode.java
public class TreeNode {
public TreeNode leftN
public TreeNode rightN
public TreeNode(int key, TreeNode leftNode, TreeNode rightNode) {
this.key =
this.leftNode= leftN
this.rightNode = rightN
2.BrinaryTree.java
—— 构造上图的二叉树
TreeNode leftLeaf1 = new TreeNode(4, null, null);
TreeNode rightLeaf1 = new TreeNode(5, null, null);
TreeNode rightLeaf2 = new TreeNode(6, null, null);
TreeNode leftTree = new TreeNode(2, leftLeaf1, rightLeaf1);
TreeNode rightTree = new TreeNode(3, null, rightLeaf2);
TreeNode root = new TreeNode(1, leftTree, rightTree);
前序算法实现（递归）
* 递归前序排列
public void recursePostOrder(TreeNode root) {
if(root == null)
root.accessMe();
if(root.leftNode != null) {
recursePostOrder(root.leftNode);
if(root.rightNode != null) {
recursePostOrder(root.rightNode);
前序算法实现（非递归）
* 非递归的前序遍历
public void stackPreOrder(TreeNode root) {
if(root == null)
Stack&TreeNode& stack = new Stack&TreeNode&();
stack.push(root);
root.accessMe();
TreeNode tmp = root.leftN
while(tmp != null) {
stack.push(tmp);
tmp.accessMe();
tmp = tmp.leftN
tmp = stack.pop();
while(tmp != null) {
tmp = tmp.rightN
while(tmp != null) {
stack.push(tmp);
tmp.accessMe();
tmp = tmp.leftN
if(stack.isEmpty()) {
tmp = stack.pop();
前序结果：1 2 4 5 3 6
中序算法实现（递归）
public void recurseInOrder(TreeNode root) {
if(root == null)
if(root.leftNode != null) {
recurseInOrder(root.leftNode);
root.accessMe();
if(root.rightNode != null) {
recurseInOrder(root.rightNode);
中序算法实现（非递归）
* 非递归的中序遍历
public void stackInOrder(TreeNode root) {
if(root == null)
Stack&TreeNode& stack = new Stack&TreeNode&();
stack.push(root);
TreeNode tmp = root.leftN
while(tmp != null) {
stack.push(tmp);
tmp = tmp.leftN
tmp = stack.pop();
while(tmp != null) {
tmp.accessMe();
tmp = tmp.rightN
while(tmp != null) {
stack.push(tmp);
tmp = tmp.leftN
if(stack.isEmpty()) {
tmp = stack.pop();
中序结果：4 2 5 1 3 6
后序算法实现（递归）
* 递归后序排列
public void recursePostOrder(TreeNode root) {
if(root == null)
if(root.leftNode != null) {
recursePostOrder(root.leftNode);
if(root.rightNode != null) {
recursePostOrder(root.rightNode);
root.accessMe();
后序算法实现（非递归）
* 非递归的后序遍历
public void stackPostOrder(TreeNode root) {
if(root == null)
Stack&TreeNode& stack = new Stack&TreeNode&();
TreeNode tmp =
while(root!=null){
while(root.leftNode != null) {
stack.push(root);
root = root.leftN
while(root != null && (root.rightNode == null || root.rightNode == tmp )) {
root.accessMe();
if(stack.isEmpty())
root = stack.pop();
stack.push(root);
root = root.rightN
后序结果：4 5 2 6 3 1
指定的元素插入二叉排序树中
* 指定的元素插入二叉排序树中
public void insertTree(TreeNode root, int key){
if(root != null) {
int value = root.
if(key & value) {
if(root.leftNode == null) {
TreeNode node = new TreeNode(key, null, null);
root.leftNode =
insertTree(root.leftNode, key);
}else if(key & value) {
if(root.rightNode == null) {
TreeNode node = new TreeNode(key, null, null);
node.rightNode =
insertTree(root.rightNode, key);
root = new TreeNode(key, null, null);
根据key查找某一元素
* 根据key查找
public TreeNode searchTree(TreeNode root, int key) {
if(root == null) {
if(key == root.key) {
}else if(key & root.key) {
return searchTree(root.leftNode, key);
return searchTree(root.rightNode, key);
oham_一1一
浏览: 25524 次
来自: 广州
这图画的挺详细的啊，学习下
我在实践的过程过程汇总出现了一个问题，求指导！！！In ...
Hi bryan, 我来你这溜达一下
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'数据结构（1）
给定二叉树的2个遍历序列（如先根+中根，先根+后根，中根+后根等），是否能够根据这2个遍历序列唯一确定二叉树？
这三种组合并不是都能唯一确定二叉树的，其中先根+后根就不能唯一确定一棵二叉树，中根+先根/后跟可以唯一确定一棵二叉树。因为先根/后根可以确定二叉树根节点是哪个，而中根可以将二叉树分为根节点和其左子树和其右子树，进而可以将先根/后根分成&根+左子树先根+右子树先根“ 或 “左子树后根+右子树后根+根”。然后就可以利用递归解决问题啦。
下面是关于该问题的证明与结论。
①给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。
证明：因为先序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（假设有L个元素）表示左子树，若左边无元素，则说明左子树为空；右边（假设有R个元素）是右子树，若为空，则右子树为空。根据前序遍历中&根-左子树-右子树&的顺序，则由从先序序列的第二元素开始的L个结点序列和中序序列根左边的L个结点序列构造左子树，由先序序列最后R个元素序列与中序序列根右边的R个元素序列构造右子树。
②由中序序列和先序序列能唯一确定一棵二叉树，但是由先序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。
反例：任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。
如： 2&&&&&&&&&& 2
&&& /&&&&&&&&&&& \
&& 1&&&&&&&&&&&&& 1&
& /&&&&&&&&&&&&&&& \
&3&&&&&&&&&&&&&&&&& 3
这两棵二叉树的先序遍历序列都为2-1-3，后序遍历序列都为3-1-2。但是显然它们是不同的二叉树，所以根据先序序列和后序序列并不能唯一确定二叉树。
③已经说明由二叉树的先序序列和中序序列可以确定一棵二叉树，现在来证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立，即结点数目为m-1时，中序序列和后序序列可以唯一确定二叉树。现证明当n=m时结论成立。
设中序序列为S1,S2,…,Sm,后序序列是P1,P2,…,Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1,S2,…,Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2,S3,…,Sm}和{P1,P2,…,Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m，则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1,S2,…,Sm-1}和{P1,P2,…,Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1&i&m时，Si把中序序列分成{S1,S2,…,Si-1}和{Si+1,Si+2,…,Sm}。由于后序遍历是&左子树-右子树-根结点&，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1,S2,…,Si-1}和{P1,P2,…,Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,…,Sm}和{Pi,Pi+1,…,Pm-1}可唯一确定二叉树的右子树。
前序遍历的第一个元素为根节点，在中序遍历中找到这个根节点，从而可以将中序遍历分为左右两个部分，左边部分为左子树的中序遍历，右边部分为右子树的中序遍历，进而也可以将前序遍历除第一个元素以外的剩余部分分为两个部分，第一个部分为左子树的前序遍历，第二个部分为右子树的前序遍历。&
由上述分析结果，可以递归调用构建函数，根据左子树、右子树的前序、中序遍历的结果输出后序遍历的结果。&
运行结果：&
D& G& J& H& E& B& I& F& C& A&
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1499次
排名：千里之外
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'> 问题详情
一棵二叉树的前根遍历、后根遍历和中根遍历所产生的序列中，所有叶结点的先后顺序是 （)。A．不相同B．
悬赏：0&答案豆
提问人：匿名网友
发布时间：
一棵二叉树的前根遍历、后根遍历和中根遍历所产生的序列中，所有叶结点的先后顺序是 () 。A．不相同B．完全相同C．前根遍历与后根遍历相同D．后根遍历与中根遍历相同请帮忙给出正确答案和分析，谢谢！
为您推荐的考试题库
您可能感兴趣的试题
1以下关于广义表的叙述中，正确的是(&&)。A．广义表是0个或多个单元素或子表组成的有限序列B．广义表至少有一个元素是子表C．广义表不可以是自身的子表D．广义表不能为空表2可以将一个堆序列看成是一棵完全二叉树结点的层次序列，下面关键序列(&&)就是一个堆。A．5，72，23，16，68，94B．68，94，23，72，5，16C．5，94，16，68，23，72D．5，23，16，68，94，723二叉树(&&)个根结点，按一定的规则，任意一棵树均可转换成惟一对应的二叉树。A．有且只有1B．有1或多于1C．有0或1D．有至少24若对一个已经排好了序的序列进行排序，在下列四种排序方法中；哪种方法比较好?(&&)A．冒泡法B．直接选择法C．直接插入法D．归并法
我有更好的答案
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
常用邮箱：
用于找回密码
确认密码：java构建二叉树及先根&中根&后根遍历
把数组中存储的数据构建成二叉树。
根节点循环 for (int parentIndex = 0; parentIndex & array.length / 2 - 1; parentIndex++)
最有一个根节点即parentIndex =array.length / 2 - 1，最后单独处理，因为最后一个根节点可能没有有孩子，如果总数为奇数才有有孩子
java代码如下：
public void createBinTree() {
nodeList = new LinkedList&Node&();
// 将一个数组的值依次转换为Node节点
for (int nodeIndex = 0; nodeIndex & array. nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
// 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树,最后一个根节点可能没有有孩子，如果
//parentIndex&= array.length / 2 - 1， 数组可能越界，只有奇数个节点才不会越界
for (int parentIndex = 0; parentIndex & array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList
.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList
.get(parentIndex * 2 + 2);
// 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理
int lastParentIndex = array.length / 2 - 1;
nodeList.get(lastParentIndex).leftChild = nodeList
.get(lastParentIndex * 2 + 1);
// 右孩子,如果数组的长度为奇数才建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList
.get(lastParentIndex * 2 + 2);
* 先序遍历
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
* @param node
遍历的节点
public static void preOrderTraverse(Node node) {
if (node == null)
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
* 中序遍历
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
* @param node
遍历的节点
public static void inOrderTraverse(Node node) {
if (node == null)
inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
* 后序遍历
* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
* @param node
遍历的节点
public static void postOrderTraverse(Node node) {
if (node == null)
postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
public static void main(String[] args) {
BinTreeTraverse2 binTree = new BinTreeTraverse2();
binTree.createBinTree();
// nodeList中第0个索引处的值即为根节点
Node root = nodeList.get(0);
System.out.println("先序遍历：");
preOrderTraverse(root);
System.out.println();
System.out.println("中序遍历：");
inOrderTraverse(root);
System.out.println();
System.out.println("后序遍历：");
postOrderTraverse(root);
非递归遍历方法
先根遍历：压栈， 出栈，保证顺序，循环栈直到为空
* 非递归先根遍历
* @param p
public static void iterativePreorder(Node p) {
Stack&Node& stack = new Stack&Node&();
if (p != null) {
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
if (p.getRightChild()!= null)
stack.push(p.getRightChild());
if (p.getLeftChild() != null)
stack.push(p.getLeftChild());
/** 非递归实现中序遍历 */
protected static void iterativeInorder(Node p) {
Stack&Node& stack = new Stack&Node&();
Node node =
while (node != null || stack.size() & 0) {
while (node != null) {
stack.push(node);
node = node.getLeftChild();
if (stack.size() & 0) {
node = stack.pop();
visit(node);
node = node.getRightChild();
/** 非递归实现后序遍历 单栈法*/
protected static void iterativePostorder3(Node p) {
Stack&Node& stack = new Stack&Node&();
Node node = p, prev =
while (node != null || stack.size() & 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
if (stack.size() & 0) {
Node temp = stack.peek().getRight();
if (temp == null || temp == prev) {
node = stack.pop();
visit(node);
/blog/808526
Copyright (C) , All Rights Reserved.
版权所有 闽ICP备号
processed in 0.045 (s). 12 q(s)