面试题6

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);
    }
}