1 题目描述
根据先序序列和中序序列构建二叉树
2 算法描述
1 遍历先序序列,获得根节点 R
2 在中序序列中检索 R,确定 R 左子树与右子树的范围
3 递归上述过程
C 语言实现
#include<stdio.h>
typedef int ElemType;
typedef struct node{
ElemType data;
struct node *lchild,*rchild;
}TNode,*Tree;
Tree constructCore(int* sp,int* ep,int* si,int* ei){
//先序遍历的第一个结点为根结点
TNode* node = (TNode*)malloc(sizeof(TNode));
node->data=sp[0];
node->lchild=NULL;
node->rchild=NULL;
//遍历 中序序列确定根结点的位置,并确定左子树和右子树范围,构建
int index=0;
int flag=0;
while(index<=ei-si){
if(si[index++]==sp[0]){
flag=1;
index--;
break;
}
}
if(flag==0) {
printf("前序序列与中序序列无法形成二叉树\n");
return NULL;
}
//index 值为根结点在中序序列中的索引
//大于 0 说明存在左子树
if(index>0){
//递归构建左子树
node->lchild=constructCore(sp+1,sp+index,si,si+index-1);
}
//存在右子树
if(index<ei-si){
node->rchild=constructCore(sp+index+1,ep,si+index+1,ei);
}
return node;
}
Tree constructTree(int preorder[],int inorder[],int length){
return constructCore(preorder,preorder+length-1,inorder,inorder+length-1);
}
//前序遍历二叉树
void preOrder(TNode* node){
if(node==NULL) return;
else{
printf("%d",node->data);
preOrder(node->lchild);
preOrder(node->rchild);
}
}
void main(){
int preorder[]={1,2,4,7,3,5,6,8};
int inorder[]={4,7,2,1,5,3,8,6};
Tree tree=NULL;
tree=constructTree(preorder,inorder,8);
preOrder(tree);
}
Java 语言实现
package _6;
public class ConstructTree {
private static class TreeNode{
int data;
TreeNode lchild;
TreeNode rchild;
}
public static void main(String[] args) {
int[] preorder={1,2,4,7,3,5,6,8};
int[] inorder={4,7,2,1,5,3,8,6};
TreeNode tree=constructTree(preorder,inorder,8);
preOrderTree(tree);
}
public static TreeNode constructTree(int[] preorder,int[] inorder,int length){
if(preorder==null||inorder==null||length<=0){
throw new RuntimeException();
}
return constructCore(preorder,0,length-1,inorder,0,length-1);
}
public static TreeNode constructCore(int[] preorder, int prestart,int preend,
int inorder[],int instart,int inend){
TreeNode node=new TreeNode();
node.data=preorder[prestart];
node.lchild=node.rchild=null;
int index=0;
boolean flag=false;
while(index<=inend-instart){
if(inorder[instart+index]==node.data){
flag=true;
break;
}
index++;
}
if(!flag){
throw new RuntimeException();
}
//index为 根结点 中序序列中的索引
//判断是否存在左子树
if(index>0){
node.lchild=constructCore(preorder,prestart+1,prestart+index,inorder,instart,instart+index-1);
}
if(index<inend-instart){
node.rchild=constructCore(preorder,prestart+index+1,preend,inorder,instart+index+1,inend);
}
return node;
}
public static void preOrderTree(TreeNode node){
if(node==null) return;
System.out.println(node.data);
preOrderTree(node.lchild);
preOrderTree(node.rchild);
}
}