二叉查找树的前序遍历,后序遍历和中序遍历互求算法模板

面试的痛



前几天去阿里面试,一时忘记了二叉树的前序遍历中序遍历和后序遍历的概念,已经想死了。

然后最近去腾讯面试,被问到怎么已知前序遍历/后序遍历 + 中序遍历,求后序遍历/前序遍历,看来这种问题很喜欢考。

其实这个问题想清楚了很简单,只要把这三个概念理解透彻就可以做出来了,比如前序遍历的第一个值一定是根节点,然后这个根节点对应到中序遍历里面,在中序遍历的这个值的两边的值,一定在以此节点为根节点的两个子树上,同理,后序遍历也一样。

已知前序遍历和后序遍历是不能求唯一的中序遍历树的。

#include <iostream>
#include <string>

using std::string;

template<typename _Val>
struct TreeNodeBase
{
    TreeNodeBase *left;
    TreeNodeBase *right;
    _Val val;
};

//已知前序遍历和中序遍历,找后序遍历
template<typename _Iter, typename _sizeType, typename _TreeNodeType = TreeNodeBase<char>>
_TreeNodeType *preOrderInfixOrderToSufixOrder(_Iter &pre, _Iter &in, _sizeType length)
{
    if (length == 0)
        return nullptr;

    auto node = new _TreeNodeType;

    _sizeType index = 0;

    for (; index != length; index++)//找到对应的前序遍历的点
        if (*(in + index) == *(pre))
            break;

    node->left = preOrderInfixOrderToSufixOrder(pre + 1, in, index);
    node->right = preOrderInfixOrderToSufixOrder(pre + index + 1, in + index + 1, length - (index + 1));
    node->val = *pre;
    std::cout << node->val << " ";
    return node;
}

//已知后序遍历和中序遍历,找前序遍历
template<typename _Iter, typename _sizeType, typename _TreeNodeType = TreeNodeBase<char>>
_TreeNodeType *sufixOrderInfixOrderToPreOrder(_Iter &sufix, _Iter &in, _sizeType length)
{
    if (length == 0)
        return nullptr;
    auto node = new _TreeNodeType;
    node->val = *(sufix + length - 1);
    std::cout << node->val << " ";

    _sizeType index = 0;
    for (;index != length ;index++)
        if (*(in + index) == *(sufix + length - 1))
            break;
    node->left = sufixOrderInfixOrderToPreOrder(sufix, in, index);
    node->right = sufixOrderInfixOrderToPreOrder(sufix + index, in + index + 1, length - (index + 1));

    return node;
}

/*
//已知前序遍历/后序遍历 + 中序遍历求后序遍历/前序遍历
int main()
{
    string preOrder("GDAFEMHZ");
    string infixOrder("ADEFGHMZ");
    string sufixOrder("AEFDHZMG");

    auto root1 = preOrderInfixOrderToSufixOrder(preOrder.begin(), infixOrder.begin(), preOrder.size());
    std::cout << std::endl;
    auto root2 = sufixOrderInfixOrderToPreOrder(sufixOrder.begin(), infixOrder.begin(), preOrder.size());

    system("pause");
    return 0;
}*/
时间: 03-23

二叉查找树的前序遍历,后序遍历和中序遍历互求算法模板的相关文章

根据前序遍历和中序遍历构建二叉树以及根据中序遍历后序遍历构建二叉树

<pre name="code" class="cpp">/************************************************************************/ /* 算法说明: 由中序遍历序列可知,第一个节点是根节点, 由前序遍历序列可知,第一个节点是根节点的左子树节点,而且前序遍历中,根节点左边是左子树,右边是右子树,因此通过中序遍历的根节点可以确定的是: 根节点在前序遍历中的位置(通过遍历前序遍历序列,

hdu1710-Binary Tree Traversals (由二叉树的先序序列和中序序列求后序序列)

http://acm.hdu.edu.cn/showproblem.php?pid=1710 Binary Tree Traversals Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4210    Accepted Submission(s): 1908 Problem Description A binary tree is a

根据二叉树的先序序列和中序序列还原二叉树并打印后序序列

#include<stdio.h> #include<stdlib.h> #include<iostream> using namespace std; struct Node { int value; Node *left; Node *right; Node(int value) { this->value = value; left = right = NULL; } }; bool bNotTree = false; Node* RebuildTree(i

二叉树先序序列和中序序列求解树

这种题一般有二种形式,共同点是都已知中序序列.如果没有中序序列,是无法唯一确定一棵树的. <1>已知二叉树的前序序列和中序序列,求解树. 1.确定树的根节点.树根是当前树中所有元素在前序遍历中最先出现的元素. 2.求解树的子树.找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树.若根节点左边或右边为空,则该方向子树为空:若根节点 边和右边都为空,则根节点已经为叶子节点. 3.递归求解树.将左子树和右子树分别看成一棵二叉树,重复1.2.3步,直到所有的节点完成定

HDU 1710 二叉树遍历,输入前、中序求后序

1.HDU  1710  Binary Tree Traversals 2.链接:http://acm.hust.edu.cn/vjudge/problem/33792 3.总结:记录下根结点,再拆分左右子树,一直搜下去.感觉像dfs. 题意:二叉树,输入前.中序求后序. (1)建立出一颗二叉树,更直观.但那些指针用法并不是很懂. #include<iostream> #include<cstdio> #include<cstdlib> using namespace

二叉树--已知先序中序求后序--已知中序后序求先序(基本按照网上某大神思路搬过来的)

思路来自(转载自)  http://www.cnblogs.com/fzhe/archive/2013/01/07/2849040.html 题目描述不说了. 前序遍历:  GDAFEMHZ 中序遍历:  ADEFGHMZ 求中序遍历. 1 确定根,确定左子树,确定右子树. 2 在左子树中递归. 3 在右子树中递归. 4 打印当前根. 代码如下: 1 #include <bits/stdc++.h> 2 3 using namespace std; 4 char pr[1000],in[100

图的建立及输出其先序序列,中序序列,后续序列

1 #include<stdio.h> 2 #include<malloc.h> 3 typedef struct node{ 4 char data; 5 struct node *left; 6 struct node *right; 7 }Node; 8 9 int i = 0; 10 char str[100]; 11 12 void create(Node** p){ 13 if(str[i] == '\0') 14 return ; 15 if(str[i++] !=

由先序序列和中序序列生成一棵二叉树

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct BiTNode{ char e; struct BiTNode *lchild,*rchild; }BiTNode; void preOrderTravse(BiTNode *T1){ if(T1){ printf("%c",T1->e); preOrderTravse(T1->lchild); p

java 二叉树的遍历 为什么只给出前序以及后序遍历,不能生成唯一的二叉树

最近在学习java的数据结构与算法知识,看到数据结构 树的遍历的方式.在理解过程中.查看到一篇文章,视野非常有深度,在信息论的角度看待这个问题.在此贴出该文章的链接以及内容. [文章出处]http://www.binarythink.net/2012/12/binary-tree-info-theory/ 我们在学习二叉树的遍历时,都会不可避免的学到二叉树的三种遍历方式,分别是遵循(根-左-右)的前序遍历.遵循(左-根-右)的中序遍历以及遵循(左-右-根)的后序遍历.并且每一个二叉树都可以用这三