我在我的博客上发布了以下教程：
a) - 中序遍历 - 后序遍历
或者
b) - 中序遍历 - 先序遍历
通常我们会遇到以下问题：
从以下树遍历中创建二叉树
1)
Inorder: E A C K F H D B G Preorder: F A E K C D H G B
在这里，始终要记住的最重要的事情是：
在先序遍历中，第一个元素是树的根
在后序遍历中，最后一个元素是树的根
希望你明白了 :P
即考虑以下问题:
1）中序遍历：E A C K F H D B G 先序遍历：F A E K C D H G B
F是根节点
E A C K将进入左子树
H D B G将进入右子树
Step 1)
F
/ \
( E A C K) (H D B G)
Step 2)
Inorder E A C K
Preorder A E K C
现在又找到了 A 作为根节点，因此现在的树是
F
/ \
A (H D B G)
/ \
E (C K)
Step 3)
现在的信件是
Inorder C K
Preorder K C
F
/ \
A (H D B G)
/ \
E K
/
C
同样的步骤可以在根节点F的右子树上完成。
对于后序遍历，我们需要找到遍历中的最后一个元素作为根节点....
彩色版本可以在这里查看：http://bloggerplugnplay.blogspot.in/2012/11/construction-of-binary-tree-from.html :P
虽然不确定具体的证明方式，但计算该过程的算法大致如下：
f(inorder, levelorder):
if length(levelorder) == 0:
return None
root = levelorder[0]#set root to first element in levelorder
subIn1, subIn2 = partition(inorder, levelorder[0]) #partition inorder based on root
subLevel1 = extract(levelOrder, subIn1)#remove elements in level order not in subIn1
subLevel2 = extract(levelOrder, subIn2)#remove elements in level order not in subIn2
root->left = f(subIn1, subLevel1)
root->right = f(subIn2, subLevel2)
return root
extract 函数是做什么的吗？ - SexyBeast我认为下面的代码应该可以工作 -
/*
//construct a bst using inorder & levelorder traversals.
//inorder - 5, 10, 20, 50, 51, 55, 60, 65, 70, 80
//levelorder - 50, 10, 60, 5, 20, 55, 70, 51, 65, 80
50
/ \
10 60
/ \ / \
5 20 55 70
/ / \
51 65 80
*/
struct node *construct_bst3(int inorder[], int levelorder[], int in_start, int in_end)
{
static int levelindex = 0;
struct node *nnode = create_node(levelorder[levelindex++]);
if (in_start == in_end)
return nnode;
//else find the index of this node in inorder array. left of it is left subtree, right of this index is right.
int in_index = search_arr(inorder, in_start, in_end, nnode->data);
//using in_index from inorder array, constructing left & right subtrees.
nnode->left = construct_bst3(inorder, levelorder, in_start, in_index-1);
nnode->right = construct_bst3(inorder, levelorder, in_index+1, in_end);
return nnode;
}
#include <fstream>
#include <iostream>
#include <deque>
#include <iomanip>
#include <sstream>
#include <string>
#include <math.h>
#include <string.h>
using namespace std;
struct BinaryTree {
BinaryTree *left, *right;
char data;
BinaryTree(int val) : left(NULL), right(NULL), data(val) { }
~BinaryTree(){ this->left = NULL; this->right = NULL ; }
};
BinaryTree *createNode(char d)
{
return new BinaryTree(d);
}
#define MAX 256
int indexOf[MAX];
void inorderIndex(char *IN,int n)
{
int i=0;
for (i = 0; i < n; i++)
{
indexOf[ (int)IN[i] ] = i;
}
return;
}
int searchIndex(char arr[], int strt, int end, char value)
{
int i;
for(i = strt; i <= end; i++)
if(arr[i] == value)
return i;
return -1;
}
BinaryTree *INLEVEL(char *in,char *level,int in_st,int in_end,int lev_st,int lev_end)
{
int idx=-1,i,left_lev_idx=-1,right_lev_idx=-1;
if(level[lev_st] == '\0' )
return NULL;
idx = searchIndex(in,in_st,in_end,level[lev_st] );
if(idx == -1)
return NULL;
BinaryTree*root=createNode( level[lev_st] );
// root->data = level[st];
root->left = root->right = NULL;
for ( i = lev_st+1; i <= lev_end ; i++)
{
if ( (indexOf[ (int) level[i] ] > idx) && (indexOf[ (int) level[i] ] <= in_end ) )
if(right_lev_idx == -1)
right_lev_idx = i;
if ( (indexOf[ (int) level[i] ] < idx) && (indexOf[ (int) level[i] ] >= in_st ) )
if(left_lev_idx == -1)
left_lev_idx = i;
}
if(left_lev_idx != -1)
root->left = INLEVEL(in,level,in_st,idx-1,left_lev_idx,lev_end);
if(right_lev_idx != -1)
root->right = INLEVEL(in,level,idx+1,in_end,right_lev_idx,lev_end);
return root;
}
int main()
{
char IN[100] ="DBFEAGCLJHK"
,LEVEL[100]="ABCDEGHFJKL";
BinaryTree *root =(BinaryTree *) NULL;
inorderIndex(IN,strlen(IN) );
root=INLEVEL(IN,LEVEL,0,strlen(IN)-1,0,strlen(IN)-1 );
// printPretty(root, 2, 0, cout);
return 0;
}
static tree MakeTreeFromInorderAndLevelOrder(int[] inorder,int[] lorder,int s,int n,int cnt1) {
if(s>n || s>=inorder.length || n>=inorder.length || cnt1>=inorder.length) {
return null;
}
int mIndex = Search(lorder[cnt1],inorder,s,n);
tree t = new tree(lorder[cnt1]);
cnt1 = 2*cnt1 + 1;
t.left = MakeTreeFromInorderAndLevelOrder(inorder,lorder,s,mIndex-1,cnt1);
//Boundary case
if(cnt1<inorder.length && t.left==null) {
t.right = MakeTreeFromInorderAndLevelOrder(inorder,lorder,mIndex+1,n,cnt1);
}
else {
cnt1 -=1;
cnt1 /=2;
cnt1 = 2*cnt1 + 2;
t.right = MakeTreeFromInorderAndLevelOrder(inorder,lorder,mIndex+1,n,cnt1);
//Boundary case
if(t.right ==null && cnt1<inorder.length) {
t.left = MakeTreeFromInorderAndLevelOrder(inorder,lorder,s,mIndex-1,cnt1);
}
}
return t;
}
import java.util.HashMap;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;
public class InorderLevelorder {
private static int[] levelArray;
public static void main(String[] args) {
//in order traversal of binary tree
int[] in = {4,10,3,1,7,11,8,2};
//level order traversal of binary tree
int[] lev = {7,10,2,4,3,8,1,11};
//Builds a Binary Tree and returns the root node
buildTree(in, lev);
}
private static BinaryTreeNode buildTree(int[] in, int[] lev){
//Hash the values of both the arrays for O(1) time search
HashMap<Integer, Integer> inMap = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> levMap = new HashMap<Integer, Integer>();
levelArray = lev;
for(int i=0;i<in.length;i++)
inMap.put(in[i], i);
for(int j=0;j<lev.length;j++)
levMap.put(lev[j], j);
return buildTree(in, lev, 0, in.length - 1, inMap, levMap);
}
//recursive method that constructs the binary tree
private static BinaryTreeNode buildTree(int[] in, int[] lev, int inStart, int inEnd, HashMap<Integer, Integer> inMap, HashMap<Integer, Integer> levMap){
if(inStart > inEnd)
return null;
int nodeVal = lev[0];
BinaryTreeNode node = new BinaryTreeNode();
node.setData(nodeVal);
if(inStart == inEnd)
return node;
int inIndex = inMap.get(nodeVal);
int[] leftSubTree = subArray(in, levelArray, inStart, inIndex-1, inMap, levMap);
int[] rightSubTree = subArray(in, levelArray, inIndex+1, inEnd, inMap, levMap);
node.setLeftNode(buildTree(in, leftSubTree, inStart, inIndex-1, inMap, levMap));
node.setRightNode(buildTree(in, rightSubTree, inIndex+1, inEnd, inMap, levMap));
return node;
}
private static int[] subArray(int[] in, int[] lev, int inStart, int inEnd, HashMap<Integer, Integer> inMap, HashMap<Integer, Integer> levMap){
int[] newSubArray = new int[inEnd - inStart + 1];
SortedSet<Integer> set = new TreeSet<Integer>();
for(int i=inStart;i<=inEnd;i++){
int levIndex = levMap.get(in[i]);
set.add(levIndex);
}
int j=0;
Iterator<Integer> iter = set.iterator();
while(iter.hasNext()){
int levIndex = iter.next();
int levValue = lev[levIndex];
newSubArray[j] = levValue;
j++;
}
return newSubArray;
}
}
class BinaryTreeNode {
private int data;
private BinaryTreeNode leftNode;
private BinaryTreeNode rightNode;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinaryTreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(BinaryTreeNode leftNode) {
this.leftNode = leftNode;
}
public BinaryTreeNode getRightNode() {
return rightNode;
}
public void setRightNode(BinaryTreeNode rightNode) {
this.rightNode = rightNode;
}
}