Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4795849
  • 博文数量: 890
  • 博客积分: 17977
  • 博客等级: 上将
  • 技术积分: 8621
  • 用 户 组: 普通用户
  • 注册时间: 2005-08-26 09:59
个人简介

一个好老好老的老程序员了。

文章分类

全部博文(890)

文章存档

2020年(7)

2019年(40)

2018年(88)

2017年(130)

2015年(5)

2014年(12)

2013年(41)

2012年(36)

2011年(272)

2010年(1)

2009年(53)

2008年(65)

2007年(47)

2006年(81)

2005年(12)

分类: C/C++

2012-09-03 10:24:33

周六面试,关于二叉树的题,题目是:
在一棵二叉树总,前序遍历结果为:ABDGCEFH,中序遍历结果为:DGBAECHF,求后序遍历结果。
 
今天再CSDN上居然发现了原题,记录下来:
 

在面试的过程中,发现有几家公司都喜欢考这样的一道题,就是在一棵二叉树中,已知这棵二叉树的前序和中序遍历结果,要求写出后序遍历结果。

例如:在一棵二叉树总,前序遍历结果为:ABDGCEFH,中序遍历结果为:DGBAECHF,求后序遍历结果。

我们知道:

前序遍历方式为:根节点->左子树->右子树

中序遍历方式为:左子树->根节点->右子树

后序遍历方式为:左子树->右子树->根节点

从这里可以看出,前序遍历的第一个值就是根节点,然后再中序遍历中找到这个值,那么这个值的左边部分即为当前二叉树的左子树部分前序遍历结果,这个值的右边部分即为当前二叉树的右子树部分前序遍历结果。因此,通过这个分析,可以恢复这棵二叉树,得到这样的一段伪码:

 

节点 getRoot(前序,中序)

c=前序第一个字符

pos=c在中序中的位置

len1=中序pos左半部分长度

len2=中序pos右半部分长度

新建节点r,令r的元素等于c

r的左儿子=getRoot(前序位置1开始的len1长度部分,中序pos位置的左半部分)

r的右儿子=getRoot(前序位置len1开始右半部分,中序pos位置的右半部分)

return r

 

如图1示:

图1

输入前序ABDGCEFH,中序DGBAECHF,可以得出

A为该二叉树的根节点

1: BDG为该二叉树左子树的前序

2: DGB为该二叉树左子树的中序

根据1和2可以构建一棵左子树

 

3: CEFH为该二叉树右子树的前序

4: ECHF为该二叉树右子树的中序

根据3和4可以构建一个右子树

 

执行至该步骤的时候就得到了该二叉树的云结构,如图2所示,A为根节点,BDG在它的左子树上,CEFG在它的右子树上。

如此递归即可以构建一棵完整的二叉树

图2

 

 

下面是c语言的实现方法(该代码的变量p1,p2,i1,i2,tmp请参考图1):

/*
 * main.cpp
 *
 *  Created on: 2011-4-11
 *      Author: boyce
 *      Email:  boyce.ywr@gmail.com
 */
#include
#include
struct BTreeNode {
 char e;
 BTreeNode *left;
 BTreeNode *right;
};
typedef BTreeNode* BTree;
BTreeNode *createBTreeNode(char e) {
 BTreeNode *nd = new BTreeNode;
 nd->e = e;
 nd->left = NULL;
 nd->right = NULL;
 return nd;
}
int findChar(const char *str, int s1, int s2, char c) {
 if (!str || s2 < s1 || s1 < 0 || s2 >= strlen(str))
  return -1;
 for (int i = s1; i <= s2; i++) {
  if (str[i] == c)
   return i;
 }
 return -1;
}
BTreeNode *getRoot(char *pre, int p1, int p2, char *in, int i1, int i2) {
 char rootCh = pre[p1];
 if (!pre || p2 < p1 || p1 < 0 || p2 >= strlen(pre) || !in || i2 < i1 || i1
   < 0 || i2 >= strlen(in)) {
  return NULL;
 }
 int tmp = findChar(in, i1, i2, rootCh);
 if (tmp < 0) {
  return NULL;
 }
 BTreeNode *nd = createBTreeNode(rootCh);
 nd->left = getRoot(pre, p1 + 1, p1 + tmp - i1, in, i1, tmp - 1);
 nd->right = getRoot(pre, p1 + tmp - i1 + 1, p2, in, tmp + 1, i2);
 return nd;
}
BTree createBTree(char *pre, char *in) {
 if (!pre || !in)
  return NULL;
 return getRoot(pre, 0, strlen(pre) - 1, in, 0, strlen(in) - 1);
}
void printPostOrder(BTree t) {
 if (!t)
  return;
 printPostOrder(t->left);
 printPostOrder(t->right);
 printf("%c", t->e);
}
void printBTreeNode(BTreeNode *nd, int depth) {
 for (int i = 0; i < depth - 1; i++)
  printf("  ");
 if (depth > 0)
  printf("--");
 if (!nd) {
  printf("*/n");
  return;
 }
 printf("%c/n", nd->e);
 printBTreeNode(nd->left, depth + 1);
 printBTreeNode(nd->right, depth + 1);
}
void printBTree(BTree t) {
 printBTreeNode(t, 0);
}
int countBTree(BTree t) {
 if (!t)
  return 0;
 return countBTree(t->left) + countBTree(t->right) + 1;
}
int main() {
 char pre[] = "ABDGCEFH";
 char in[] = "DGBAECHF";
 BTree t = createBTree(pre, in);
 printf("Preorder: %s/n", pre);
 printf("Inorder: %s/n", in);
 if (countBTree(t) != strlen(pre)) {
  printf("No such a binary tree!/n");
  return 0;
 }
 printf("Postorder: ");
 printPostOrder(t);
 printf("/n");
 printf("The BTree is (* means no such node):/n");
 printBTree(t);
 return 0;

 下面是输出结果显示:

阅读(2522) | 评论(0) | 转发(0) |
0

上一篇:二叉树面试

下一篇:二叉树的Java版实现

给主人留下些什么吧!~~