实验五 构造二叉树和二叉树的层序遍历

一、实验描述

1.  构造二叉树：给出一棵二叉树的先序（或后序）遍历结果，以及中序遍历结果，如何构造这棵树？假定遍历结果以数组方式输入，请写出相应函数，判断是否存在生成同样遍历结果的树，如果存在，构造这棵树。

2.  二叉树的层序遍历：使用队列作为辅助存储，按树的结点的深度，从根开始依次访问所有结点。

 

二、实验分析

（1）构造二叉树：

①根据前序遍历找到树的根节点，在中序遍历中找到根节点，将树分为左右两棵子树，找到前序遍历中两棵子树的位置，对两棵子树进行递归调用

（2）层序遍历:

①将根节点放入队列中

②从队列中取出节点，将左儿子和右儿子放入队列，输出当前节点的关键字

③重复步骤2，直到队列为空

 

三、实验设计

1.构造二叉树

#include<stdio.h>  
#include<stdlib.h>  
#include<time.h>  
#include<string.h>  
  
#define ARRAY_LENGTH(array) sizeof(array)/sizeof(*array)  
#define MY_RAND_MAX 100  
  
typedef struct NODE{  
    int val;  
    struct NODE *left;  
    struct NODE *right;  
}Node;  
  
static Node* newNode(int val,Node *left,Node *right){  
    Node *result = (Node*)malloc(sizeof(Node));  
    if(NULL != result){  
        result->val = val;  
        result->left = left;  
        result->right = right;  
    }  
    return result;  
}  
  
int cur = 1;  
  
Node* RecoverPreTree(int *pre,int *mid,int length){  
    if(0 == length)  
        return NULL;  
  
    int i = 0;  
    for(;mid[i]!=*pre;i++);  
    Node *root = newNode(*pre,NULL,NULL);  
    root->left = RecoverPreTree(pre+1,mid,i);  
    root->right = RecoverPreTree(pre+1+i,mid+1+i,length-1-i);  
    return root;  
}  
  
Node* Generate(int depth){  
    if(-1 == depth)  
        return NULL;  
    srand(rand());  
    return newNode(cur++,Generate(depth-1),Generate(depth-1));  
}  
  
int* PreTravesal(Node *root){  
    if(NULL == root){  
        int *result = (int*)malloc(sizeof(int));  
        *result = 0;  
        return result;  
    }  
  
    int *left = PreTravesal(root->left);  
    int *right = PreTravesal(root->right);  
    int *result = (int*)malloc(sizeof(int)*(*left+*right+2));  
    *result = 1+*left+*right;  
    *(result+1) = root->val;  
    memcpy(result+2,left+1,*left*sizeof(int));  
    memcpy(result+2+*left,right+1,*right*sizeof(int));  
    free(left);  
    free(right);  
    return result;  
}  
  
int* InTravesal(Node *root){  
    if(NULL == root){  
        int *result = (int*)malloc(sizeof(int));  
        *result = 0;  
        return result;  
    }  
  
    int *left = InTravesal(root->left);  
    int *right = InTravesal(root->right);  
  
    int *result = (int*)malloc(sizeof(int)*(*left+*right+2));  
    *result = 1+*left+*right;  
    memcpy(result+1,left+1,*left*sizeof(int));  
    *(result+*left+1) = root->val;  
    memcpy(result+2+*left,right+1,*right*sizeof(int));  
    free(left);  
    free(right);  
    return result;  
}  
  
void PrintPreTree(Node *root){  
    static int indent = 0;  
  
    if(NULL  == root)  
        return;  
  
    printf("\t");  
    printf("%d\n",root->val);  
  
    indent ++;  
    PrintPreTree(root->left);   
    PrintPreTree(root->right);  
    indent --;  
    return;  
}  
  
void PrintArray(int *array,int length){  
    for(int i = 0;i<length;i++)  
        printf("%d ",*(array++));  
}  
  
void DestroyTree(Node *root){  
    if(NULL == root)  
        return;  
      
    DestroyTree(root->left);  
    DestroyTree(root->right);  
    free(root);  
}  
  
int main(){  
  
    Node *tree = Generate(3);  
    PrintPreTree(tree);  
    printf("\n");  
    int *array1 = PreTravesal(tree);  
    PrintArray(array1+1,*array1);  
    printf("\n");  
    int *array2 = InTravesal(tree);  
    PrintArray(array2+1,*array2);  
  
    printf("\n");  
    Node *recover = RecoverPreTree(array1+1,array2+1,*array1);  
    PrintPreTree(recover);  
  
  
    free(array1);  
    free(array2);  
    DestroyTree(tree);  
    DestroyTree(recover);  
    return 0;  
}  

2.层序遍历

#include<stdio.h>  
#include<stdlib.h>  
#include<time.h>  
#include<string.h>  
  
#define ARRAY_LENGTH(array) sizeof(array)/sizeof(*array)  
#define MY_RAND_MAX 100  
  
typedef struct NODE{  
    int val;  
    struct NODE *left;  
    struct NODE *right;  
}Node;  
  
static Node* newNode(int val,Node *left,Node *right){  
    Node *result = (Node*)malloc(sizeof(Node));  
    if(NULL != result){  
        result->val = val;  
        result->left = left;  
        result->right = right;  
    }  
    return result;  
}  
  
typedef struct LIST{  
    Node *root;  
    struct LIST *next;  
}List;  
  
typedef struct QUEUE{  
    List *head;  
    List *tail;  
}Queue;  
  
Queue* newQueue(){  
    Queue *result = (Queue*)malloc(sizeof(Queue));   
    List *tmp = (List*)malloc(sizeof(List));  
    tmp->next = NULL;  
    result->head = tmp;  
    result->tail = result->head;   
    return result;  
}  
  
void Enqueue(Queue *queue,Node *root){  
    List *tmp = (List*)malloc(sizeof(List));  
    tmp->root = root;  
    tmp->next = NULL;  
    queue->tail->next = tmp;  
    queue->tail = queue->tail->next;  
}  
  
Node* Dequeue(Queue *queue){    
    if(NULL == queue->head->next)  
        return NULL;  

    List* tmp = queue->head->next;  
    Node* result = tmp->root;  
    queue->head->next = queue->head->next->next;  
    if(queue->head->next == NULL){  
        queue->tail = queue->head;  
    }  
    free(tmp);  
    return result;  
}  
  
int cur = 1;  
Node* Generate(int depth){  
    if(-1 == depth)  
        return NULL;  
  
    srand(rand());  
    return newNode(rand()%MY_RAND_MAX,Generate(depth-1),Generate(depth-1));  
}  
  
void PrintPreTree(Node *root){  
    static int indent = 0;  
   
    if(NULL  == root)  
        return;  
    for(int i = 0;i<indent;i++)  
        printf("\t");  
    printf("%d\n",root->val);  
  
    indent ++;  
    PrintPreTree(root->left);  
    PrintPreTree(root->right);  
    indent --;  
    return;  
}  
  
void DestroyTree(Node *root){  
    if(NULL == root)  
        return;  
      
    DestroyTree(root->left);  
    DestroyTree(root->right);  
    free(root);  
}  
  
void DestroyList(List *list){  
    while(NULL != list){  
        free(list);  
        list = list->next;  
    }  
}  
  
int main(){  
  
    Node *tree = Generate(3);  
    PrintPreTree(tree);  
    printf("\n");  
    Queue *queue = newQueue();  
    Enqueue(queue,tree);  
    while(queue->head!=queue->tail){  
        Node *tmp = Dequeue(queue);  
        if(NULL == tmp)  
            continue;  
        printf("%d ",tmp->val);  
        if(NULL != tmp->left)  
            Enqueue(queue,tmp->left);  
        if(NULL != tmp->right)  
            Enqueue(queue,tmp->right);  
    }  
  
    DestroyTree(tree);  
    DestroyList(queue->head);  
    free(queue);  
    return 0;  
}  

 

四、实验结论

1.构造二叉树：

如果使用线性扫描查找位置，则每次查找需要 O（N）的时间，如果二叉树平衡的话，则整个算法需要 O（NlgN）的时间。如果二叉树不平衡，则最坏情况需要 O（N^2）时间。为了提高效率，我们可以考虑使用哈希表来存储与查找根结点在中序遍历中的位置，每次查找只需要 O（1）的时间，这样构建整棵树只需要 O（N）的时间。

2.二叉树的层序遍历：

因为每个节点只访问一次，时间复杂度为 O(N)。